写作网站好吗,华夏集团网站建设,上市公司查询网站,常德网站设计文章目录简要题目描述解析dp定义:试填法代码thanks for reading#xff01;简要 数位dp#xff0c;天下第一 最重要的应该有两个#xff1a; 1.状态转移式的确定 2.试填法不断往后模拟 #xff08;至今是唯一一道数位dp#xff0c;究竟重要的是啥我其实也没有太多经验 简要 数位dp天下第一 最重要的应该有两个 1.状态转移式的确定 2.试填法不断往后模拟 至今是唯一一道数位dp究竟重要的是啥我其实也没有太多经验 半年之后的UPD为什么要试填法啊记搜天下第一 至少这道题提供了很好的方法与套路
题目描述 解析
dp定义:
pos表示位数 res表示膜13的余数 op表示关于出现13的状态其中 op0 啥也没有 op1没有出现13但最高位是3再来个1就ok啦 op2已经存在13了 dp[pos][res][op]就是表示符合上述状态的数的数量 具体状态转移见代码
试填法
比当前最高位设为s小的后面可以随便填 若本位填了s就不断向后模拟注意op这里op1的定义是最后一位是1和res随着填数的转移 大于s自然不能填啦 注意这么填最后会填到n-1所以要么一开始就把n1要么特判一下n
代码
数位dp法
#includebits/stdc.h
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N2e6100;
const int M2e6100;
int dp[12][15][5],mi[15];
int a,m;
void Dp(){//预处理dpmi[0]1;for(int i1;i9;i) mi[i]mi[i-1]*10;dp[0][0][0]1;for(int pos1;pos10;pos){//从后往前填 for(int i0;i9;i){for(int res10;res112;res1){int res2(res113-i*mi[pos-1]%13)%13;if(i!1i!3) dp[pos][res1][0]dp[pos-1][res2][1];if(i!3) dp[pos][res1][0]dp[pos-1][res2][0];if(i3){dp[pos][res1][1]dp[pos-1][res2][0]dp[pos-1][res2][1];}if(i1) dp[pos][res1][2]dp[pos-1][res2][1];dp[pos][res1][2]dp[pos-1][res2][2];}}}
}
int solve(int n){//试填法int op0,res10,ans0;for(int pos10;pos1;pos--){//从前往后填 int sn/mi[pos-1];for(int is-1;i0;i--){//s以下自由填 int op2,resnow(res1i*mi[pos-1])%13,res2(13-resnow)%13;//res2是后面需要的模数if(op2||(op1i3)) op22;else if(i1) op21;else op20;ansdp[pos-1][res2][2];if(op2) ansdp[pos-1][res2][1];if(op22) ansdp[pos-1][res2][0]; }if(op!2){if(op1s3) op2;else if(s1) op1;else op0;}res1(res1s*mi[pos-1])%13;n%mi[pos-1];}
// if(op2res10) ans;
//这里的特判和下面的a1有一个即可return ans;
}
int main(){Dp();while(scanf(%d,a)!EOF){printf(%d\n,solve(a1));}return 0;
}
/*
13
100
200
1000
*/
thanks for reading
