loj #6059. 「2017 山东一轮集训 Day1」Sum — 倍增+NTT

  • 2018-01-07
  • 0
  • 0

#6059. 「2017 山东一轮集训 Day1」Sum

内存限制:256 MiB 时间限制:1500 ms

题目描述

求有多少 n 位十进制数是 p pp 的倍数且每位之和小于等于 mi(mi=0,1,2,…,m−1,m) ,允许前导 0,答案对 998244353 取模。

输入格式

一行三个整数 n,p,m

输出格式

输出一行 m+1个正整数,分别表示 mi=0,1,2,…,m−1,m 时的答案。

样例

样例输入

样例输出

数据范围与提示

 

首先裸dp比较好推,f[i][j][k]表示第i位,模p为j,数字和为k的方案数

由于n很大,我们可以考虑二进制拆分

倍增求出f[2^i][][],然后将n的二进制位是1的合并起来就好了

然后就是考虑如何合并两个数组

可以先枚举k,k=k1+k2,然后p^2的枚举每一个余数就好

我们不难发现这就是一个卷积

用NTT加速即可

这里复杂度是(p*mlogm+p^2 m)的,因为我们只需要一次正变换,然后乘完之后再变换回来即可

所以总复杂度(p*mlogm+p^2 m)logn

 

 

评论

还没有任何评论,你来说两句吧