题目4 : K-偏差排列
N 很大，肯定得快速幂，关键是怎么构造转移方程
因为 |Pi - i| <= K，所以当你填完P1Pi这i个空时，1(i-K) 肯定都用掉了，(i+K+1)~N肯定都还没用。
你只需要考虑(i-K+1) ~ (i+K)一共2K个数用掉哪几个，一共有2^(2K)种情况。
所以可以用f[i][k]表示确定了前i个数，同时(i-K+1) ~ (i+K)还剩下哪几个数没用(状态压缩用k表示)，一共有多少种方案。
转移就是从(i-K+1) ~ (i+K)中剩下的数里选一个填在第i+1个位置上。这里要注意如果(i-K+1)没用的话，i+1只能填(i-K+1)。
由于从f[i] 转移到 f[i+1] 和 f[i+1] 转移到 f[i+2] 的方程是一样的，所以可以直接拿这个转移方程来快速幂。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
// Matrix
const int maxn = 122;
struct Matrix {
LL m[maxn][maxn];
Matrix() { memset(m, 0, sizeof(m)); }
void E() { for (int i = 0; i < maxn; i++) m[i][i] = 1; }
} A;
Matrix M_mul(Matrix a, Matrix b) {
Matrix ret;
for (int i = 0; i < maxn; i++)
for (int k = 0; k < maxn; k++) {
if (a.m[i][k] == 0) continue;
for (int j = 0; j < maxn; j++)
ret.m[i][j] = (ret.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
}
return ret;
}
Matrix M_qpow(Matrix P, LL n) {
Matrix ret;
ret.E();
while (n) {
if (n & 1LL) ret = M_mul(ret, P);
n >>= 1LL;
P = M_mul(P, P);
}
return ret;
}
int main() {
int N, K;
scanf("%d %d", &N, &K);
assert(1 <= N <= 1000000000 && 1 <= K && K <= 3);
for(int i = 0; i < (1 << 7); ++i){
int j = (i << 1) & ((1 << 7) - 1);
for(int k = -K; k <= K; ++k){
if(j & (1 << (3 - k))) continue;
A.m[j ^ (1 << (3 - k))][i]++;
}
}
A = M_qpow(A, N);
printf("%lld\n", A.m[120][120]);
return 0;
}
