@codeforces - 1096G@ Lucky Tickets

@description@
@solution@
@accepted code@
@details@

@description@

已知一个数（允许前导零）有 n 位（n 为偶数），并知道组成这个数的数字集合（并不一定要把集合内的数用完）。求有多少种可能，使得这个数前半部分的数位和等于后半部分的数位和。

模 998244353。

input

第一行两个整数：n k。表示这个数的位数以及组成这个数的数字集合大小。2 <= n <= 2*10^5，1 <= k <= 10。

第二行 k 个两两不同的整数 d1，d2，...，dk，表示组成这个数的数字集合。0 <= di <= 9。

output

输出可能数，模 998244353。

sample input

4 2

1 8

sample output

6

sample explain

6 种可能分别是：1111,1818,8118,1881,8181,8888。

@solution@

模数暗示 NTT。

如果长度为 n/2，数位和为 s 的数有 k 种，则它对答案的贡献为 \(k^2\)。

问题等价于求，长度为 n/2，数位和为 0,1,2,... 的数有多少种。

我们于是可以 dp。定义状态 \(dp[i][j]\) 表示长度为 i 的数，数位和为 j 的方案数。

定义 \(f\)，使得 \(f[d[i]]=1(1\le i \le k)\)。可以得到状态转移方程：

\[dp[i][j] = \sum_{k=0}^{9}dp[i-1][j-k]*f[k]
\]

嗯好的这是一个卷积形式的 dp，我们可以用 NTT 来优化。

可以得到 \(dp[\frac{n}{2}][j] = f^{\frac{n}{2}}[j]\)。

转换成点值形式后直接快速幂再转换回来。

@accepted code@

#include<cstdio>

#include<algorithm>

using namespace std;

const int G = 3;

const int MOD = 998244353;

const int MAXN = 200000*9*2;

int pow_mod(int b, int p) {

	int ret = 1;

	while( p ) {

		if( p & 1 ) ret = 1LL*ret*b%MOD;

		b = 1LL*b*b%MOD;

		p >>= 1;

	}

	return ret;

}

void ntt(int A[], int n, int type) {

	for(int i=0,j=0;i<n;i++) {

		if( i < j ) swap(A[i], A[j]);

		for(int l=(n>>1);(j^=l)<l;l>>=1);

	}

	for(int s=2;s<=n;s<<=1) {

		int t = (s >> 1);

		int u = (type == 1) ? (pow_mod(G, (MOD-1)/s)) : (pow_mod(G, (MOD-1)-(MOD-1)/s));

		for(int i=0;i<n;i+=s) {

			for(int p=1,j=0;j<t;j++,p=1LL*p*u%MOD) {

				int x = A[i+j], y = 1LL*A[i+j+t]*p%MOD;

				A[i+j] = (x + y)%MOD, A[i+j+t] = (x + MOD - y)%MOD;

			}

		}

	}

	if( type == -1 ) {

		int inv = pow_mod(n, MOD-2);

		for(int i=0;i<n;i++)

		A[i] = 1LL*A[i]*inv%MOD;

	}

}

int f[MAXN + 5];

int main() {

	int n, k, d, mx = 0;

	scanf("%d%d", &n, &k);

	for(int i=1;i<=k;i++) {

		scanf("%d", &d);

		mx = max(mx, d);

		f[d] = 1;

	}

	int len; for(len = 1;len <= ((n>>1)*mx);len<<=1);

	ntt(f, len, 1);

	for(int i=0;i<len;i++)

		f[i] = pow_mod(f[i], (n>>1));

	ntt(f, len, -1);

	int ans = 0;

	for(int i=0;i<len;i++)

		ans = (ans + 1LL*f[i]*f[i]%MOD)%MOD;

	printf("%d\n", ans);

}

@details@

连续做了几天多项式毒瘤算法，做一个卷积优化是真的轻松惬意。

我才不会说因为 mx 没有弄初值 RE 了让我懵逼了好久。

我怎么可能会因为傻逼错误做不出来傻逼题。

巴特西

@codeforces - 1096G@ Lucky Tickets

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章