[BZOJ 3328]PYXFIB
又学了个新套路呢qwq
题面要求的其实是：
\sum_{i = 0}^n [k|i]\binom{n}{i} F_i
不考虑那个[k|i]，式子是非常像一个二项式展开的……
考虑构造矩阵的二项式展开，可以发现（其中A是斐波那契数列的二项式展开）：
(I + A)^n = \sum_{i = 0}^n \binom{n}{i} A^i
然后k=1的情况我们就会做辣！接下来的问题是，如何取出一个生成函数中次数为k倍数的项求和？
然后我们发现单位根有个非常优良的性质：
\frac{1}{k} \sum_{i=1}^{k} \xi_k^{ni} = [k|n]
这里的n是一个常数，但是其实可以对应到原式里的某一项的次数。至于证明……满足k|n的情况左边显然是一堆1取平均值，其他情况可以通过等比数列求和证明左边为0。
于是可以构造多项式(I+xA)^n，把所有k次单位根做为x（求这个的话，可以利用原根）带入，对结果取平均值即可。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | /************************************************************** Problem: 3328 User: danihao123 Language: C++ Result: Accepted Time:9080 ms Memory:832 kb****************************************************************/ #include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <utility>#include <cmath>#include <vector>typedef long long ll;typedef ll Mat[2][2];ll p; int k;ll pow_mod(ll a, ll b) { ll ans = 1LL, res = a % p; while(b) { if(1LL & b) ans = (ans * res) % p; res = (res * res) % p; b /= 2LL; } return ans;}ll inv(ll x) { return pow_mod(x, p - 2LL);} void factor(int x, std::vector<int> &V) { int bd = sqrt(x + 0.5); for(int i = 2; i <= bd; i ++) { if(x % i == 0) { V.push_back(i); while(x % i == 0) x /= i; } } if(x > 1) V.push_back(x);}int get_phi() { if(p == 2LL) return 1LL; std::vector<int> V; factor(p - 1LL, V); for(int i = 2; i <= (p - 1); i ++) { bool flag = true; for(int j = 0; j < V.size(); j ++) { int up = (p - 1) / V[j]; if(pow_mod(i, up) == 1LL) { flag = false; break; } }#ifdef LOCAL if(flag) printf("xi : %d\n", i);#endif if(flag) return i; }} void mat_mul(const Mat &A, const Mat &B, int n, int m, int t, Mat &C) { Mat D; memset(D, 0, sizeof(D)); for(int i = 0; i < n; i ++) { for(int j = 0; j < t; j ++) { for(int k = 0; k < m; k ++) { D[i][j] = (D[i][j] + (A[i][k] * B[k][j]) % p) % p; } } } memcpy(C, D, sizeof(D));}void mat_pow(const Mat &A, int n, ll b, Mat &ret) { Mat C, res; memset(C, 0, sizeof(C)); for(int i = 0; i < n; i ++) C[i][i] = 1LL; memset(res, 0, sizeof(res)); memcpy(res, A, sizeof(res)); while(b) { if(1LL & b) mat_mul(C, res, n, n, n, C); mat_mul(res, res, n, n, n, res); b /= 2LL; } memcpy(ret, C, sizeof(C));} int main() { int T; scanf("%d", &T); while(T --) { ll n; scanf("%lld%d%lld", &n, &k, &p); ll xi = pow_mod(get_phi(), (p - 1) / k); ll w = 1LL; ll ans = 0; for(int i = 0; i < k; i ++) { Mat X; memset(X, 0, sizeof(X)); X[0][0] = X[1][0] = X[0][1] = w; X[0][0] = (X[0][0] + 1LL) % p; X[1][1] = (X[1][1] + 1LL) % p; mat_pow(X, 2, n, X);#ifdef LOCAL puts("X : "); for(int i = 0; i < 2; i ++) { for(int j = 0; j < 2; j ++) { printf("%lld ", X[i][j]); } puts(""); }#endif ans = (ans + X[0][0]) % p; w = (w * xi) % p; } ans = (ans * inv(k)) % p; printf("%lld\n", ans); } return 0;} |
