题目大意
给定$n(n \le 10^9),k(k \le 4)$,定义$p_i$为排列中第$i$个数
询问长度为$n$且$|p_i-i| \le k$的排列的个数$\pmod {1e9+7}$
解题报告
不难发现$k$很小,于是我们可以状压DP
进一步观察,有用的状态只有70个
于是我们可以$O(70^3 \log n)$的复杂度用矩阵快速幂解决
不过这题还可以用线性$K$阶递推式的那个解法
用特征多项式做到一个比较优的复杂度
GEOTCBRL就是用这个A的,太强大了_(:з」∠)_
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int MOD = 1000000007; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int n,K,t,tot,itr[1000],num[1000]; struct Matrix{ int a[70][70]; inline Matrix() {memset(a,0,sizeof(a));} inline Matrix(Matrix *tmp) {memcpy(a,tmp->a,sizeof(a));} inline Matrix(int v) {memset(a,0,sizeof(a));for(int i=0;i<tot;i++)a[i][i]=v;} inline void reset() {memset(a,0,sizeof(a));} inline Matrix operator * (const Matrix &B) { Matrix ret; for (int i=0;i<tot;i++) for (int j=0;j<tot;j++) for (int k=0;k<tot;k++) ret.a[i][j] = (ret.a[i][j] + (LL)a[k][j] * B.a[i][k]) % MOD; return ret; } inline Matrix operator ^ (int t) { Matrix ret(1),w(this); for (;t;t>>=1,w=w*w) if (t&1) ret=ret*w; return ret; } }ans,tra; int main() { for (;~scanf("%d%d",&n,&t);tot=0) { t <<= 1; K = 1 << t; ans.reset(); tra.reset(); for (int i=0;i<K;i++) { if (__builtin_popcount(i) != t/2) continue; else itr[i] = tot, num[tot++] = i; } for (int h=0,cur,i;i=num[h],h<tot;h++) { for (int j=0;j<=t;j++) { if (i&(1<<j)) continue; cur = i | (1 << j); if (!(cur&1)) continue; tra.a[h][itr[cur>>1]] = 1; } } t = itr[(1<<(t/2))-1]; ans.a[t][0] = 1; tra = tra ^ n; ans = ans * tra; printf("%d\n",ans.a[t][0]); } return 0; }
I want examining and I believe this website got some really utilitarian stuff on it! .
Appreciate it for helping out, fantastic information.