CF1096G Lucky Tickets 快速幂套FFT

(color{#0066ff}{ 题目描述 })

一个(n)位数，每位可以是给出的(k)个数码中的一个数，可以有前导(0),输出前(n/2)位之和与后(n/2)位之和相等的方案数，保证(n)是偶数。

(color{#0066ff}{输入格式})

输入的第一行是两个整数(n,k)

接下来的一行有(k)个数(d_1,d_2,cdots,d_k(0leq d_ileq 9))

(color{#0066ff}{输出格式})

输出一个数，为方案数模(998244353)的值

(color{#0066ff}{输入样例})

4 2
1 8

20 1
6

10 5
6 1 4 0 3

1000 7
5 4 0 1 8 3 2

(color{#0066ff}{输出样例})

(color{#0066ff}{数据范围与提示})

(2leq nleq 2*10^5,1leq kleq 10)

(color{#0066ff}{ 题解 })

构造生成函数

比如第一个样例，构造出(x^1+x^8)

然后序列的一半是2，就让它平方是(x^2+2*x^9+x^{16})

每个x指数是凑出的和，前面的系数就是方案数，但是这是一半的，乘法原理

(ans=sum 系数平方)

直接暴力快速幂套FFT可过

#include<bits/stdc++.h>
#define LL long long
LL 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<int> &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<int> operator * (vector<int> A, vector<int> 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<int> 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<int> ksm(vector<int> A, int B) {
	vector<int> 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<int> 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
", tot);
	return 0;
}