【Codechef DEVLOCK Devu and Locks】【倍增二维FFT】题意分析代码
题意求有多少个nnn位十进制数(可以有前导零),满足模ppp等于000且每一位数字之和不超过mmm。n≤109,p≤16,m≤15000n\le 10^9,p\le 16, m\le 15000n≤109,p≤16,m≤15000分析注意到第iii位贡献的系数为10i mod p10^i\bmod p10imodp,两位的贡献不同当且仅当对应系数不同。因此可以把数位按照系数分类。设numinum_inumi表示有多少位满足贡献系数为iii。numinum_inumi可以通过求10k10^k1