【日常小测】排列

题目大意

给定$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;
}