Problem 1161 - 科协的数字游戏II
Time Limit: 1000MS Memory Limit: 65536KB Difficulty:
Total Submit: 112 Accepted: 15 Special Judge: No
Total Submit: 112 Accepted: 15 Special Judge: No
Description
由于科协里最近真的很流行数字游戏。&＃xff08;&＃61; &＃61;&＃xff01;汗一个&＃xff09;某人又命名了一种取模数&＃xff0c;这种数字必须满足各位数字之和 mod N为0。现在大家又要玩游戏了&＃xff0c;指定一个整数闭区间[a,b]&＃xff0c;问这个区间内有多少个取模数。
Input
题目有多组测试数据。每组只含3个数字a, b, n (1 <&＃61; a, b <&＃61; 2^31,1 <&＃61; n <100)。
Output
每个测试用例输出一行&＃xff0c;表示各位数字和 mod N为0 的数的个数。
Sample Input
1 19 9
Sample Output
2
Hint
Source
tclh123
#include #include #include using namespace std; int dp[100][111],bit[100],a,b,n; int dfs(int pos,int res,bool limit) { if(pos&＃61;&＃61;-1) return res&＃61;&＃61;0; if(!limit&&~dp[pos][res]) return dp[pos][res]; int end&＃61;limit?bit[pos]:9; int ans&＃61;0; for(int i&＃61;0;i<&＃61;end;i&＃43;&＃43;) { int newres&＃61;(res&＃43;i)%n; ans&＃43;&＃61;dfs(pos-1,newres,limit&&(i&＃61;&＃61;end)); } if(!limit) dp[pos][res]&＃61;ans; return ans; } int cal(int x) { int len&＃61;0; while(x) { bit[len&＃43;&＃43;]&＃61;x%10; x/&＃61;10; } return dfs(len-1,0,true); } int main() { while(scanf("%d%d%d",&a,&b,&n)!&＃61;EOF) { memset(dp,-1,sizeof(dp)); printf("%d\n",cal(b)-cal(a-1)); } return 0; } |
![[c++基础]STL](https://img.php1.cn/3c972/1edc8/c5a/a04ecc977fd8ed28.jpeg)
京公网安备 11010802041100号