[洛谷P3321][SDOI2015]序列统计

日期：2023-10-08 20:55

-->

标题摘要：给你一套$n,m,x,S(S_i\in(0,m],m\leqslant 8000,m\in \rm{prime},n\leqslant10^9 )$，求长度为$n$的序列$Q$，满足$Q_i\in S$，且$\prod\limits _{i=1}^nQ_i=x$，求序列数

问题解决：乘法比较麻烦。你可以找到每个数字的$\ln$，并且可以找到$m$的原始根。求原根，可以用$O(m^2)$求原根，然后每个求数$\ln$，求生成函数$F(x)$，计算$F^ n(x)$。发现如果$n$较大，多项式可以快速升幂。

卡点：无

C++代码：

#包括
#包括
#包括
#定义最大n 16384 | 3
#定义最大8010
const int mod = 1004535809，G = 3；
int n、m、x、S、g；
int vis[maxm];
int get(int m) {
bool find = false;
for (int i = 2; i < m; i++) {
memset(vis, -1, vis 的大小);
int t = 1;
vis[1] = 0;
for (int j = 1; j < m - 1; j++) {
t = t * i % m;
if (~vis[t]) 中断;
否则 vis[t] = j;
if (j == m - 2) find = true;
}
如果（查找）返回 i；
}
返回20040826;
}
int lim, ilim, s, rev[maxn];
int base[maxn], ans[maxn], Wn[maxn + 1];
内联 int pw(int base, int p) {
整数分辨率 = 1;
for (; p; p >>= 1, 基数 = 1ll * 基数 * 基数 % mod) if (p & 1) res = 1ll * res * 基数 % mod;
返回分辨率；
}
内联 int Inv(int x) {return pw(x, mod - 2);}
内联 void init(int n) {
lim = 1，s = -1； while (lim < n) lim <<= 1, s++; ilim = Inv(lim);
for (int i = 0; i < lim; i++) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
int t = pw(G, (mod - 1) / lim);
Wn[0] = 1； for (int i = 1; i <= lim; i++) Wn[i] = 1ll * Wn[i - 1] * t % mod;
}
inline void up(int &a, int b) {if ((a += b) >= mod) a -= mod;}
内联 void NTT(int *A, int op) {
for (int i = 0; i < lim; i++) if (i < rev[i]) std::swap(A[i], A[rev[i]]);
for (int mid = 1; mid < lim; mid <<= 1) {
int t = lim / mid >> 1;
for (int i = 0; i < lim; i += mid << 1) {
for (int j = 0; j < mid; j++) {
int W = 操作？ Wn[j * t] : Wn[lim - j * t];
int X = A[i + j], Y = 1ll * A[i + j + mid] * W % mod;
向上(A[i + j], Y), 向上(A[i + j + mid] = X, mod - Y);
}
}
}
if (!op) for (int i = 0; i < lim; i++) A[i] = 1ll * A[i] * ilim % mod;
}
int C[maxn], D[maxn];
内联 void MUL(int *A, int *B) {
for (int i = 0; i < lim; i++) C[i] = A[i], D[i] = B[i];
NTT(C, 1), NTT(D, 1);
for (int i = 0; i < lim; i++) C[i] = 1ll * C[i] * D[i] % mod;
NTT(C, 0);
for (int i = 0; i < lim; i++) A[i] = C[i];
for (int i = m - 1; i < lim; i++) (A[i % (m - 1)] += A[i]) %= mod, A[i] = 0;
}
int main() {
scanf("%d%d%d%d", &n, &m, &x, &S);
g = get(m);
for (int i = 0, tmp; i < S; i++) {
scanf("%d", &tmp);
if (tmp) 基[vis[tmp]] = 1;
}
初始化(m << 1);
ans[0] = 1;
for (; n; n >>= 1, MUL(基数, 基数)) if (n & 1) MUL(ans, 基数);
printf("%d\n", ans[vis[x]]);
返回0;
}

-->

最近发表

猜你喜欢

关灯

[洛谷P3321][SDOI2015]序列统计

相关文章