\(\color{#0066ff}{ 题目描述 }\)
一个\(n\)位数,每位可以是给出的\(k\)个数码中的一个数,可以有前导\(0\),输出前\(n/2\)位之和与后\(n/2\)位之和相等的方案数,保证\(n\)是偶数。
\(\color{#0066ff}{输入格式}\)
输入的第一行是两个整数\(n,k\)
接下来的一行有\(k\)个数\(d_1,d_2,\cdots,d_k(0\leq d_i\leq 9)\)
\(\color{#0066ff}{输出格式}\)
输出一个数,为方案数模\(998244353\)的值
\(\color{#0066ff}{输入样例}\)
4 21 820 1610 56 1 4 0 31000 75 4 0 1 8 3 2
\(\color{#0066ff}{输出样例}\)
61 569725460571165
\(\color{#0066ff}{数据范围与提示}\)
\(2\leq n\leq 2*10^5,1\leq k\leq 10\)
\(\color{#0066ff}{ 题解 }\)
构造生成函数
比如第一个样例,构造出\(x^1+x^8\)
然后序列的一半是2,就让它平方是\(x^2+2*x^9+x^{16}\)
每个x指数是凑出的和,前面的系数就是方案数,但是这是一半的,乘法原理
\(ans=\sum 系数平方\)
直接暴力快速幂套FFT可过
#include#define LL long longLL in() { char ch; LL x = 0, f = 1; while(!isdigit(ch = getchar()))(ch == '-') && (f = -f); for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48)); return x * f;}using std::vector;const int mod = 998244353;const int maxn = 8e6 + 10;LL ksm(LL x, LL y) { LL re = 1LL; while(y) { if(y & 1) re = re * x % mod; x = x * x % mod; y >>= 1; } return re;}int r[maxn], len;void FNTT(vector &A, int flag) { A.resize(len); for(int i = 0; i < len; i++) if(i < r[i]) std::swap(A[i], A[r[i]]); for(int l = 1; l < len; l <<= 1) { int w0 = ksm(3, (mod - 1) / (l << 1)); for(int i = 0; i < len; i += (l << 1)) { int w = 1, a0 = i, a1 = i + l; for(int k = 0; k < l; k++, a0++, a1++, w = 1LL * w * w0 % mod) { int tmp = 1LL * A[a1] * w % mod; A[a1] = ((A[a0] - tmp) % mod + mod) % mod; A[a0] = (A[a0] + tmp) % mod; } } } if(flag == -1) { std::reverse(A.begin() + 1, A.end()); int inv = ksm(len, mod - 2); for(int i = 0; i < len; i++) A[i] = 1LL * A[i] * inv % mod; }}vector operator * (vector A, vector B) { int tot = A.size() + B.size() - 1; for(len = 1; len <= tot; len <<= 1); for(int i = 0; i < len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) * (len >> 1)); FNTT(A, 1), FNTT(B, 1); vector ans; ans.resize(len); for(int i = 0; i < len; i++) ans[i] = 1LL * A[i] * B[i] % mod; FNTT(ans, -1); ans.resize(tot); return ans;}vector ksm(vector A, int B) { vector ans; ans.push_back(1); while(B) { if(B & 1) ans = ans * A; A = A * A; B >>= 1; } return ans;}int main() { int n = in(), k = in(); vector ans; ans.resize(10); for(int i = 1; i <= k; i++) ans[in()] = 1; ans = ksm(ans, n >> 1); LL tot = 0; for(int i = 0; i < (int)ans.size(); i++) (tot += 1LL * ans[i] * ans[i] % mod) %= mod; printf("%lld\n", tot); return 0;}