fork(1) download
copy 
  1. // -----------------------------------------------------------------------
  2. // 1. aの各位の数字の和 mod 9 = a mod 9 であることを利用する
  3. // 2. そうするとDP[i][j]のjの値によっては確実に0となるようなところがある。
  4. // 3. そのようなとことを探索しない。
  5. // 4. 計算量はO(|N|*D), 定数は約9分の1
  6. // -----------------------------------------------------------------------
  7. #include <string>
  8. #include <iostream>
  9. #define mod 1000000007
  10. using namespace std;
  11. string s; int d, sum, ret, dp[111][11119];
  12. int main() {
  13. 	cin >> s >> d;
  14. 	dp[0][0] = 1;
  15. 	for(int i = 1; i <= s.size(); i++) {
  16. 		sum += s[i - 1] - 48; sum %= 9;
  17. 		for(int j = 0; j * 9 + sum <= d; j++) {
  18. 			int x = 0, t = 1;
  19. 			for(int k = 1; i >= k; k++) {
  20. 				if(t <= j * 9 + sum) x += (s[i - k] - 48) * t, t *= 10;
  21. 				else if(s[i - k] != 48) break;
  22. 				if(x > j * 9 + sum) break;
  23. 				dp[i][j] = (dp[i][j] + dp[i - k][(j * 9 + sum - x) / 9]) % mod;
  24. 			}
  25. 		}
  26. 	}
  27. 	for(int i = 0; i * 9 + sum <= d; i++) ret = (ret + dp[s.size()][i]) % mod;
  28. 	printf("%d\n", ret);
  29. }
Success #stdin #stdout 0s 8288KB
comments (?)
stdin
copy 
123456
10000
stdout
copy 
29
https://ideone.com/XniH6y
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!