[BZOJ 3328]PYXFIB
转载请注明出处:http://danihao123.is-programmer.com/
又学了个新套路呢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\)(求这个的话,可以利用原根)带入,对结果取平均值即可。
代码:
/************************************************************** 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; }