首页 > 代码库 > Codeforces Round #287 D.The Maths Lecture
Codeforces Round #287 D.The Maths Lecture
The Maths Lecture
题意：求存在后缀Si mod k =0，的n位数的数目。（n <=1000,k<=100）;
用f[i][j]代表 长为i位,模k等于j的数的个数.
可以用 f[i+1][(t*10i+j)%k]=∑f[i][j]+(j==0),(t*10i+j)%k!=0;动态规划
这样可以求出所有f[n][i] i>0 的值。
最后用9*10^(n-1)-∑f[n][i] 就可以得到 答案
#include <bits/stdc++.h>using namespace std;#define ll long longint n, k, MOD;ll f[1009][109], tem = 1, ans, tot = 9;int main() { ios::sync_with_stdio(0); cin >> n >> k >> MOD; for (int i = 1; i <= n; i++) { for (int j = 0; j < k; j++) { for (int t = 0 + (i == n); t <= 9; t++) { ll d = (t * tem + j) % k; if (d) f[i][d] += f[i - 1][j] + (j == 0); if (f[i][d] >= MOD) f[i][d] -= MOD; } } tem = (tem * 10) % k; } for (int i = 1; i < n; i++) tot *= 10, tot %= MOD; for (int i = 1; i < k; i++) ans += f[n][i], ans %= MOD; cout << (MOD + tot - ans) % MOD << endl; return 0;}
Codeforces Round #287 D.The Maths Lecture
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。