[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\)(求这个的话,可以利用原根)带入,对结果取平均值即可。
代码:
/************************************************************** 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; }
[BZOJ 3992][SDOI2015]序列统计
终于调过去了……(然而不就是道NTT+生成函数水题吗至于调半天)
首先积非常的恶心,考虑转成和。这个事需要求指标的……求指标的话枚举原根的若干次幂即可(恰好$m$是素数一定有原根……),判断原根用比较大力的手段即可(我搞了一个$O(n\sqrt{n}logn)$的……求轻喷)。
然后这题还算比较简单吧……用生成函数表示原来的集合,然后$n$次幂就可以了。
注意那事个循环卷积……所以要开两倍然后每次乘完了再把右半部分搞过去。
代码:
/************************************************************** Problem: 3992 User: danihao123 Language: C++ Result: Accepted Time:6652 ms Memory:1864 kb ****************************************************************/ #include <cstdio> #include <cstring> #include <cstdlib> #include <cctype> #include <algorithm> #include <queue> #include <utility> #include <vector> #include <cmath> typedef long long ll; const int maxn = 32005; const ll ha = 1004535809LL; const ll bs = 3LL; ll n, m, gl; int sz; ll pow_mod(ll a, ll b, ll p) { if(!b) return 1LL; ll ans = pow_mod(a, b >> 1, p); ans = (ans * ans) % p; if(b & 1LL) ans = (ans * a) % p; return ans; } ll inv(ll x, ll p) { return pow_mod(x, p - 2LL, p); } void break_up(ll x, std::vector<ll> &V) { int bd = sqrt(x + 0.5); for(ll i = 2; i <= bd; i ++) { if(x % i == 0) { V.push_back(i); while(x % i == 0) x /= i; } if(x == 1LL) break; } if(x > 1LL) V.push_back(x); } ll get_phi() { if(m == 2LL) return 1LL; ll mi = m - 1LL; std::vector<ll> V; break_up(mi, V); for(ll i = 2; i <= mi; i ++) { bool ok = true; for(int j = 0; j < V.size(); j ++) { ll b = mi / V[j]; if(pow_mod(i, b, m) == 1LL) { ok = false; #ifdef LOCAL printf("%lld not passed!\n", i); #endif break; } } if(ok) { return i; } } } int bi, len; int flip(int x) { int ans = 0; for(int i = 0; i < bi; i ++) { if((1 << i) & x) { ans += (1 << (bi - i - 1)); } } return ans; } void ntt(ll *A, bool flag = false) { for(int i = 0; i < len; i ++) { int v = flip(i); if(v < i) std::swap(A[i], A[v]); } for(int L = 1; L < len; L <<= 1) { ll xi_n = pow_mod(3LL, (ha - 1LL) / (ll(L << 1)), ha); if(flag) xi_n = inv(xi_n, ha); for(int i = 0; i < len; i += (L << 1)) { ll w = 1; for(int j = i; j < i + L; j ++) { ll p1 = A[j], p2 = A[j + L]; A[j] = (p1 + (p2 * w) % ha) % ha; A[j + L] = (p1 - (p2 * w) % ha + ha) % ha; w = (w * xi_n) % ha; } } } } void poly_mul(ll *A, ll *B) { static ll C[maxn]; memset(C, 0, sizeof(C)); #ifdef LOCAL printf("A :"); for(int i = 0; i < len; i ++) printf(" %lld", A[i]); puts(""); printf("B :"); for(int i = 0; i < len; i ++) printf(" %lld", B[i]); puts(""); #endif ntt(A); ntt(B); for(int i = 0; i < len; i ++) C[i] = (A[i] * B[i]) % ha; ntt(C, true); ll inv_n = inv(len, ha); for(int i = 0; i < len; i ++) { C[i] = (C[i] * inv_n) % ha; } #ifdef LOCAL printf("C (not processed) :"); for(int i = 0; i < len; i ++) printf(" %lld", C[i]); puts(""); #endif for(int i = 0; i < len; i ++) { int v = i % (m - 1LL); if(v != i) { C[v] = (C[v] + C[i]) % ha; C[i] = 0LL; } } #ifdef LOCAL printf("C :"); for(int i = 0; i < len; i ++) printf(" %lld", C[i]); puts(""); #endif std::copy(C, C + len, A); } void poly_pow(ll *A, ll b) { static ll B[maxn]; static ll res[maxn]; std::copy(A, A + len, res); std::fill(A, A + len, 0); A[0] = 1LL; #ifdef LOCAL printf("A :"); for(int i = 0; i < len; i ++) printf(" %lld", A[i]); puts(""); printf("res : "); for(int i = 0; i < len; i ++) printf("%lld ", res[i]); puts(""); #endif while(b) { if(1LL & b) { std::copy(res, res + len, B); poly_mul(A, B); std::fill(B, B + len, 0); } std::copy(res, res + len, B); poly_mul(res, B); std::fill(B, B + len, 0); b >>= 1LL; } } int main() { static bool vis[maxn]; static ll A[maxn]; scanf("%lld%lld%lld%d", &n, &m, &gl, &sz); ll phi = get_phi(); for(int i = 1; i <= sz; i ++) { int v; scanf("%d", &v); if(v == 0) continue; vis[v] = true; } int logx = 0; bi = 0; len = 1; while(len <= (2 * m - 2)) { bi ++; len <<= 1; } for(int i = 0; i < (m - 1); i ++) { int v = pow_mod(phi, i, m); if(vis[v]) { A[i] ++; #ifdef LOCAL printf("log(%d) : %d\n", v, i); #endif } if(v == gl) { logx = i; } } poly_pow(A, n); printf("%lld\n", A[logx]); return 0; }