Magic Numbers
题意:求区间[l ,r]间偶数位都是d,奇数位都不是d的个数。l和r位数相等。
解:l和r位数相等,很舒服,不用判前导0了。记录一下位数,判断其位置和是不是d即可。多取点模。
代码:
#include <bits/stdc++.h> using namespace std; #define maxx 100005 #define maxn 25 #define maxm 205 #define ll long long #define inf 1000000009 #define mod 1000000007 char a[2005]; int len; ll dp[2005][2005]={0}; int m,d; ll dfs(ll pos,ll sum,ll limit){ if(pos==len+1) { return sum%m==0; } if(!limit&&dp[pos][sum]!=-1) return dp[pos][sum]; ll ret=0; ll res=limit?a[pos]:9; for(int i=0;i<=res;i++){ if((i==d&&pos%2)||(i!=d&&!(pos%2))) continue; ret=(ret+dfs(pos+1,(sum*10+i)%m,limit&&(i==a[pos])))%mod; } return !limit?dp[pos][sum]=ret:ret; } ll solve(){ len=strlen(a+1); for(int i=1;i<=len;i++){ a[i]-='0'; } return dfs(1,0,1); } signed main() { // int T; // scanf("%d",&T); // while(T--) { // // } memset(dp,-1,sizeof dp); scanf("%d%d",&m,&d); scanf("%s",a+1); int flag=1; ll res=0; ll r1=solve(); for(int i=1;i<=len;i++){ res=(res*10+a[i])%m; if((a[i]==d&&i%2)||(a[i]!=d&&!(i%2))) { flag = 0; } } if(res!=0) flag=0; scanf("%s",a+1); ll r2=solve(); printf("%lld\n",((r2-r1+mod)%mod+flag)%mod); return 0; }View Code
The Maths Lecture
题意:求有多少n位数(不算前导0),其后缀之一为k的倍数(不包含0)。
解:一个条件一个条件来。先记录一个con,判断这个后缀是不是0(因为要对k取模)。再记录一下前缀,最后的时候判断第一位是不是0。从低位往高位dp,求和的时候记录一下当前位权。全塞进dp数组就行。a数组是debug用的,debug了半天发现自己把now打成n,直接昏过去。
代码:
#include <bits/stdc++.h> using namespace std; #define maxx 100005 #define maxn 25 #define maxm 205 #define ll long long #define inf 1000000009 #define mod 2520 char a[1005]; int len; ll dp[1005][10][2][2][105]={0}; int n,k,m; ll dfs(ll pos,ll pre,ll con,ll con2,ll sum,ll now){ if(pos==0) { a[pos+1]=pre+'0'; a[0]='0'; if(pre&&(con2||(!con&&sum%k==0))){ printf(""); } return pre&&(con2||(!con&&sum%k==0)); } a[pos+1]=pre==-1?'\0':pre+'0'; if(pre!=-1&&dp[pos][pre][con][con2][sum]!=-1) return dp[pos][pre][con][con2][sum]; ll ret=0; ll res=9; for(int i=0;i<=res;i++){ if(!con&&sum%k==0) con2=1; ret=(ret+dfs(pos-1,i,con&&i==0,con2,(sum+(i*now)%k)%k,now*10%k))%m; } if(pre!=-1) dp[pos][pre][con][con2][sum]=ret; return ret; } signed main() { // int T; // scanf("%d",&T); // while(T--) { // // } memset(dp,-1,sizeof dp); scanf("%d%d%d",&n,&k,&m); printf("%lld\n", dfs(n,-1,1,0,0,1)); return 0; }View Code
标签:数位,pre,ll,pos,二则,sum,dp,define From: https://www.cnblogs.com/capterlliar/p/16866149.html