题目链接:B-number
题意:
题解;
代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> #include <string> using namespace std; #define For(i,a) for(i=0;i<a;i++) #define Foru(i,a,b) for(i=a;i<=b;i++) #define Ford(i,a,b) for(i=a;i>=b;i--) #define clr(ar,vel) memset(ar,vel,sizeof(ar)) #define PB push_back typedef long long ll; const int maxint = 0x7fffffff; const ll maxll = 1LL<<60; int digtal[20]; int mod_num[20]; int ans; int dp[10][3][15]; // dp[i][0] -> 有13, dp[i][1] -> 没有13 3开头, dp[i][2] -> 没有13 int dfs(int p, int mod, int flag){ //p:长度; mod:前面的余数; flag:前面是否出现13 // cout << flag << ' ' << mod << ' ' << p << ' ' << digtal[p] << ' ' << mod_num[p] << endl; if( p == 0) { if( flag && !mod ) ans ++; return 0; } for(int i = 0; i < digtal[p]; i ++){ int nxt = i*mod_num[p]; nxt = 13*10 + mod - nxt; nxt %= 13; if( i == 1 && !flag) ans += dp[p-1][1][nxt]; ans += dp[p-1][0][nxt]; if(flag || (i == 3 && digtal[p+1] == 1)) ans += dp[p-1][2][nxt]; // cout << "####" << i << ' ' << ans << ' ' << nxt << ' ' << dp[p-1][0][nxt] << ' ' << dp[p-1][1][nxt] << ' ' << dp[p-1][2][nxt] << endl; } if(digtal[p] == 3 && digtal[p+1] == 1) flag = 1; dfs(p-1, (13*10+mod-digtal[p]*mod_num[p])%13, flag); } int main(){ #ifndef in ios::sync_with_stdio(false); #endif memset(dp, 0, sizeof(dp)); for(int i = 1; i < 10; i ++) dp[0][2][0] = 1; int mod = 1; for(int i = 1; i < 10; i ++){ for(int j = 0; j < 10; j ++){ for(int k = 0; k < 13; k ++){ int re = j*mod+k; // if( i == 1 )cout << re << ' ' << k << endl; dp[i][0][re%13] += dp[i-1][0][k]; if( j == 1) dp[i][0][re%13] += dp[i-1][1][k]; if( j == 3 ) dp[i][1][re%13] += dp[i-1][2][k]; dp[i][2][re%13] += dp[i-1][2][k]; if( j == 1 ) dp[i][2][re%13] -= dp[i-1][1][k]; } } mod = mod * 10 %13; // cout << mod << endl; } for(int i = 0; i < 5; i ++){ // for(int j = 0; j < 13; j ++) cout << dp[i][0][j] << ' '; cout << endl; } mod_num[1]=1; for(int i = 2; i < 15; i ++){ mod_num[i] = mod_num[i-1]*10%13; } int n; // for(int i = 0; i < 14; i ++) cout << mod_num[i] << ' '; cout << endl; n = 10000; while(cin >> n){ memset(digtal, 0, sizeof(digtal)); ans = 0; int x = n; int len = 0; while(x){ digtal[++len] = x%10; x /= 10; } dfs( len, 0, 0); cout << ans << endl; } return 0; }