B-number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3257 Accepted Submission(s): 1819
Problem Description
A
wqb-number, or B-number for short, is a non-negative integer whose
decimal form contains the sub- string "13" and can be divided by 13. For
example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your
task is to calculate how many wqb-numbers from 1 to n for a given
integer n.
Input
Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).
Output
Print each answer in a single line.
Sample Input
13
100
200
1000
Sample Output
1
1
2
2
Author
wqb0039
Source
Recommend
lcy
这道题跟只是将不要62的那道题稍微变形了一下，dp[i][j][k]长度为i，对13取余为j的数。
dp[i][j][0]代表不含13的整数的个数
dp[i][j][1]代表不含13，且首位为3的整数的个数
dp[i][j][2]代表含有13的整数的个数
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=12; int md[N],dp[N][13][3]; void Init(){ md[0]=1; for(int i=1;i<N;i++) md[i]=md[i-1]*10; memset(dp,0,sizeof(dp)); dp[0][0][0]=1; for(int i=0;i<N-1;i++) for(int j=0;j<13;j++){ for(int k=0;k<10;k++) dp[i+1][(j+md[i]*k)%13][0]+=dp[i][j][0]; dp[i+1][(j+md[i])%13][0]-=dp[i][j][1]; dp[i+1][(j+md[i]*3)%13][1]+=dp[i][j][0]; dp[i+1][(j+md[i])%13][2]+=dp[i][j][1]; for(int k=0;k<10;k++) dp[i+1][(j+md[i]*k)%13][2]+=dp[i][j][2]; } } int solve(int x) { int s[15],len=0,xx=x; while(x>0) { s[++len]=x%10; x/=10; } s[len+1]=0; //初始化前缀为0，0是没有任何影响的，后面一位可能会用到前面一位 // cout<<len<<endl; int ans=0,flag=0; int yy=0,yyy=0; int answer; for(int i=len;i>=1;i--) //每次枚举的数是：上界前缀+i这一位的数字+符合要求的dp[i][j][k] { answer=ans; for(int kk=0;kk<s[i];kk++) { for(int j=0;j<13;j++) { if(( (yyy*10+ kk)*md[i-1] +j)%13==0) //i这一位上枚举的数字变化，就得判断 { ans+=dp[i-1][j][2]; } } } if(flag) //如果前缀中有出现13，并且 { // ans+=s[i]*dp[i-1][0]; for(int kk=0;kk<s[i];kk++) for(int j=0;j<13;j++) { if(( (yyy*10+ kk)*md[i-1] +j)%13==0) { ans+=dp[i-1][j][0]; } } } //只考虑以len位置为i的开头的数 if(!flag && s[i]>1) { // ans+=dp[i-1][1];//因为是大于号，所以低一位可以完全枚举,加上首位为3的个数 for(int j=0;j<13;j++) { if(( (yyy*10+ 1)*md[i-1] +j)%13==0) { ans+=dp[i-1][j][1]; } } } //考虑前缀的影响 if(!flag && s[i+1]==1 && s[i]>3) // ans+=dp[i][1]; { for(int j=0;j<13;j++) { if(( ((yyy-s[i+1]+1)*10+ 3)*md[i-1] + j )%13==0) { ans+=dp[i-1][j][0]; } } } if(s[i+1]==1 && s[i]==3) { flag=1; } yyy=yyy*10+s[i]; } return ans; } int main(){ // freopen("test.txt","r",stdin); //cout<<(0%13)<<endl; Init(); int n; while(~scanf("%d",&n)){ printf("%d ",solve(n+1)); } return 0; }
小优化的代码：
已知(a+b)%13=0，已知a，求b;
1:(a+b)%13=0;
2:(a%13+b%13)%13=0;
3:(13-a%13)%13=b;(第二次再MOD13，是因为a有可能等于0)
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int V=10; const int mod=13; const int N=12; int md[N],dp[N][13][3]; void Init(){ md[0]=1; for(int i=1;i<N;i++) md[i]=md[i-1]*10%13; memset(dp,0,sizeof(dp)); dp[0][0][0]=1; for(int i=0;i<N-1;i++) for(int j=0;j<13;j++){ for(int k=0;k<10;k++) dp[i+1][(j+md[i]*k)%13][0]+=dp[i][j][0]; dp[i+1][(j+md[i])%13][0]-=dp[i][j][1]; dp[i+1][(j+md[i]*3)%13][1]+=dp[i][j][0]; dp[i+1][(j+md[i])%13][2]+=dp[i][j][1]; for(int k=0;k<10;k++) dp[i+1][(j+md[i]*k)%13][2]+=dp[i][j][2]; } } int solve(int x) { int s[15],len=0,xx=x; while(x>0) { s[++len]=x%10; x/=10; } s[len+1]=0; //初始化前缀为0，0是没有任何影响的，后面一位可能会用到前面一位 // cout<<len<<endl; int ans=0,flag=0; int yy=0,yyy=0; int answer; for(int i=len;i>=1;i--) { // ans+=(s[i]*dp[i-1][2]); //含4和62的个数 answer=ans; int temp_mod; for(int kk=0;kk<s[i];kk++) { temp_mod = (13 - ( (yyy * 10 + kk) * md[i-1] )% 13) %13; ans+=dp[i-1][temp_mod][2] ; if(flag) //如果前缀中有出现13，并且 ans+=dp[i-1][temp_mod][0]; if(!flag && kk==1) { ans+=dp[i-1][temp_mod][1]; } if(!flag && s[i+1]==1 && kk==3) ans+=dp[i-1][temp_mod][0]; } //只考虑以len位置为i的开头的数 if(s[i+1]==1 && s[i]==3) { flag=1; } yyy=yyy*10+s[i]; // printf("%d ",ans-answer); } return ans; } int main() { // freopen("test.txt","r",stdin); //cout<<(0%13)<<endl; Init(); int n; while(~scanf("%d",&n)){ printf("%d ",solve(n+1)); } return 0; }