【codeforces 508D】The Maths lecture
2024-10-01 07:32:58
【题目链接】:http://codeforces.com/problemset/problem/507/D
【题意】
让你找符合这样数字的数的个数:
1.有n个数码
2.某个后缀%k的值为0
3.大于0
【题解】
数位DP;
设f[i][j][0]和f[i][j][1]分别表示;
(把最后的数字倒过来)
前i个数字组成的数%k的结果为j;
且前i-1个数字没有出现过%k结果为0;
前i-1个数字有出现过%k结果为0的方案数;
枚举新添加的一位;
看看新的取余值是啥;
然后想一想转移方程就好;
dp[0][0][0]=1;
(一开始那个不算取余值为0)
(第一位必须为正数!)
最后累计∑f[n][0..k-1][1];
输出答案;
【Number Of WA】
0
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0),cin.tie(0)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 1100;
const int K = 110;
LL n,k,m,dp[N][K][2],pre[N];
//0不含%k==0
//1含%k==0
int main()
{
//Open();
Close();//scanf,puts,printf not use
//init??????
cin >> n >> k >> m;
pre[0] = 1%k;
rep1(i,1,1000)
pre[i] = (pre[i-1]*10)%k;
dp[0][0][0] = 1;
rep1(i,0,n-1)
rep1(j,0,k-1)
rep1(num,(i==(n-1)?1:0),9)
{
LL now = (j+num*pre[i])%k;
if (now==0 && num!=0)
{
dp[i+1][now][1] = (dp[i+1][now][1] + dp[i][j][0])%m;
}
else
//now!=0 || (now==0 && num==0)
dp[i+1][now][0] = (dp[i+1][now][0] + dp[i][j][0])%m;
dp[i+1][now][1] = (dp[i+1][now][1] + dp[i][j][1])%m;
}
LL ans = 0;
rep1(i,0,k-1)
ans = (ans + dp[n][i][1])%m;
cout << ans << endl;
return 0;
}
最新文章
- javascript Date format(js日期格式化)
- 智能车学习(十五)&mdash;&mdash;K60野火2013版例程
- Information
- 深入理解js——继承
- 使用TransactionScopeOption 管理事务流
- Libsvm自定义核函数【转】
- 自定义sublime代码片段
- java笔记01-反射
- 13、Android的多线程与异步任务
- Android Button悬浮在SurfaceView上
- [JS]九种网页弹窗代码
- css3属性:column分栏
- 三分钟使用webpack-dev-sever搭建一个服务器
- clickhouse修改时区
- 监控linux服务器是否能登陆 邮件报警
- Java并发编程基础——同步
- 为VisualStudio2017添加bits/stdc++.h
- 使用共同函数,将PNotify弹出提示框公用
- FJUT16级第一周寒假作业题解I题
- ubuntu下修改mysql默认data路径
热门文章
- Emgu cv人脸检测识别
- springMVC入门截图
- FactoryBean简介
- struts配置问题
- Spring Boot 第一个demo
- [GraphQL] Fetch Server Data and Client-side State in One Query using React Apollo + GraphQL
- 剑指Offer面试题33(java版):把数组排成最小的数
- 【Java并发编程实战】—–synchronized
- java 顺序 读写 Properties 配置文件 支持中文 不乱码
- Android应用之——自己定义控件ToggleButton