题意

求有多少个$n$位十进制数（可以有前导零），满足模$p$等于$0$且各位数字之和不超过$m$。
$n\le 10^9,p\le 16,m\le 15000$

分析

注意到第$i$位贡献的系数为$10^i\mathrm{m}\mathrm{o}\mathrm{d}p$，两位的贡献不同当且仅当对应系数不同。因此可以把数位按照系数分类。设$nu{m}_i$表示有多少位满足贡献系数为$i$。$nu{m}_i$可以通过求$10^k$模$p$的周期来求出。

可以用倍增FFT求出$f_{i,j}$表示选了$nu{m}_i$个$0$到$9$之间的数，和为$j$的方案数。显然$f_{i,j}$的每种方案中，选取数字乘上对应系数之和模$p$的值为$ij\mathrm{m}\mathrm{o}\mathrm{d}p$。从而得到$g_{i,k,j}$表示在系数为$i$的位置中，选出来的数乘上系数之和模$p$的值为$k$，且选出来的数之和为$j$的方案数。把$g_0,\cdots ,g_{p-1}$通过二维FFT合并，就得到答案了。

二维FFT的实现方法是先对$A$的第一维做DFT得到数组$B$，再对$B$的第二维做DFT得到数组$C$。则$C$就是二维DFT得到的数组。但这题里面$p$比较小，因此第二维可以直接暴力卷积。

倍增FFT的时间复杂度为$O(pm\log n\log m)$，二维FFT的时间复杂度为$O(p^{2}m\log m+p^{3}m)$，因此总的时间复杂度为$O(pm\log n\log m+p^{2}m\log m+p^{3}m)$。

代码

#include<bits/stdc++.h>
#define pb push_back
using namespace std;

typedef long long LL;

const int N = 33005;
const int P = 55;
const int MOD = 998244353;

int n, p, m, num[P], bz[40][N], f[P][N], g[P][N], tmp[P][N], ans[P][N], L, rev[N];
vector<int> wn1[25], wn2[25];

int gcd(int x, int y)
{
	return !y ? x : gcd(y, x % y);
}

int ksm(int x, int y, int mo)
{
	int ans = 1;
	while (y)
	{
		if (y & 1) ans = (LL)ans * x % mo;
		x = (LL)x * x % mo; y >>= 1;
	}
	return ans;
}

void pre()
{
	int now[p], w = 1 % p, ls;
	memset(now, 0, sizeof(now));
	for (int i = 1; i <= n && !now[w]; i++, w = w * 10 % p) num[w]++, now[w] = i, ls = i;
	int T = ls - now[w] + 1, tmp = n - now[w] + 1 - T;
	for (int i = 0; i < T; i++, w = w * 10 % p) num[w] += tmp / T;
	for (int i = 0; i < tmp % T; i++, w = w * 10 % p) num[w]++;
	int lg = 0;
	for (L = 1; L <= m * 2; L <<= 1, lg++);
	for (int i = 0; i < L; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lg - 1));
	for (int i = 0; i < 20; i++)
	{
		int w1 = ksm(3, (MOD - 1) / (1 << i) / 2, MOD), w2 = ksm(3, MOD - 1 - (MOD - 1) / (1 << i) / 2, MOD);
		wn1[i].pb(1); wn2[i].pb(1);
		for (int j = 1; j < (1 << i); j++) wn1[i].pb((LL)wn1[i][j - 1] * w1 % MOD), wn2[i].pb((LL)wn2[i][j - 1] * w2 % MOD);
	}
}

void NTT(int * a, int f)
{
	for (int i = 0; i < L; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int i = 1, lg = 0; i < L; i <<= 1, lg++)
		for (int j = 0; j < L; j += (i << 1))
			for (int k = 0; k < i; k++)
			{
				int u = a[j + k], v = (LL)a[j + k + i] * (f == 1 ? wn1[lg][k] : wn2[lg][k]) % MOD;
				a[j + k] = (u + v) % MOD; a[j + k + i] = (u + MOD - v) % MOD;
			}
	if (f == -1) for (int i = 0, inv = ksm(L, MOD - 2, MOD); i < L; i++) a[i] = (LL)a[i] * inv % MOD;
}

void solve1()
{
	int mx = 0;
	for (int i = 0; i < p; i++) mx = max(mx, num[i]), f[i][0] = 1;
	for (int i = 0; i <= min(9, m); i++) bz[0][i] = 1;
	NTT(bz[0], 1);
	for (int i = 0; (1 << i) <= mx; i++)
	{
		for (int j = 0; j < p; j++)
			if (num[j] & (1 << i))
			{
				NTT(f[j], 1);
				for (int k = 0; k < L; k++) f[j][k] = (LL)f[j][k] * bz[i][k] % MOD;
				NTT(f[j], -1);
				for (int k = m + 1; k < L; k++) f[j][k] = 0;
			}
		if ((1 << (i + 1)) > mx) break;
		for (int j = 0; j < L; j++) bz[i + 1][j] = (LL)bz[i][j] * bz[i][j] % MOD;
		NTT(bz[i + 1], -1);
		for (int j = m + 1; j < L; j++) bz[i + 1][j] = 0;
		NTT(bz[i + 1], 1);
	}
}

void solve2()
{
	ans[0][0] = 1;
	for (int i = 0; i < p; i++)
	{
		for (int j = 0; j < p; j++) memset(g[j], 0, sizeof(g[j])), memset(tmp[j], 0, sizeof(tmp[j]));
		for (int j = 0; j <= m; j++)
			(g[j * i % p][j] += f[i][j]) %= MOD;
		for (int j = 0; j < p; j++) NTT(ans[j], 1), NTT(g[j], 1);
		for (int j = 0; j < p; j++)
			for (int k = 0, tar = j; k < p; k++, tar = (tar + 1) % p)
				for (int l = 0; l < L; l++)
					(tmp[tar][l] += (LL)ans[j][l] * g[k][l] % MOD) %= MOD;
		for (int j = 0; j < p; j++)
		{
			NTT(tmp[j], -1);
			for (int k = 0; k <= m; k++) ans[j][k] = tmp[j][k];
			for (int k = m + 1; k < L; k++) ans[j][k] = 0;
		}
	}
}

int main()
{
	scanf("%d%d%d", &n, &p, &m);
	pre();
	solve1();
	solve2();
	for (int i = 1; i <= m; i++) (ans[0][i] += ans[0][i - 1]) %= MOD;
	for (int i = 0; i <= m; i++) printf("%d ", ans[0][i]);
	return 0;
}

最后

以上就是犹豫睫毛膏为你收集整理的【Codechef DEVLOCK Devu and Locks】【倍增二维FFT】题意分析代码的全部内容，希望文章能够帮你解决【Codechef DEVLOCK Devu and Locks】【倍增二维FFT】题意分析代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。