Madiyar

Untitled

Jan 11th, 2013
212
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include <iostream>        
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <cassert>
  9. #include <ctime>
  10. #include <cmath>
  11. #include <string>
  12. #include <cstring>
  13. #include <queue>
  14. using namespace std;
  15.  
  16. #define f first
  17. #define s second
  18. #define mp make_pair
  19. #define pb push_back
  20. #define pii pair<int, int>
  21. #define vi vector<int>
  22. #define all(v) (v).begin(), (v).end()
  23. #define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
  24. #define f0(a) memset(a, 0, sizeof(a))
  25. #define ll long long
  26.  
  27. #ifdef WIN32
  28.     #define I64 "%I64d"
  29. #else
  30.     #define I64 "%lld"
  31. #endif
  32. const int mod = (int)1e9 + 7;
  33. ll dp[210][2000], cnt[210][2000];
  34. bool calced[210][2000];
  35. int n, dig;
  36.  
  37. inline void Calc(int cur, int sum) {
  38.  
  39.     if (cur == n + n) {
  40.         cnt[cur][sum] = (sum == 0);
  41.         dp[cur][sum] = 0;
  42.         return;
  43.     }
  44.  
  45.     ll &ans = dp[cur][sum];
  46.  
  47.     if (calced[cur][sum]) return;  
  48.     calced[cur][sum] = true;
  49.    
  50.     cnt[cur][sum] = ans = 0;
  51.  
  52.  
  53.     for (int i = 0; i < 10; ++i) {
  54.         int nsum = (cur >= n) ? sum - i : sum + i;
  55.         if (nsum < 0) break;
  56.  
  57.         Calc(cur + 1, nsum);
  58.  
  59.         ans = (ans + dp[cur + 1][nsum] + (i == dig) * cnt[cur + 1][nsum]) % mod;
  60.         cnt[cur][sum] = (cnt[cur][sum] + cnt[cur + 1][nsum]) % mod;
  61.     }
  62. }
  63.  
  64. int main() {
  65.     cin >> n;
  66.     for (dig = 0; dig < 10; ++dig) {
  67.         f0(calced);
  68.         Calc(0, 0);
  69.         cout << dp[0][0] << " ";
  70.     }
  71. }
Advertisement
Add Comment
Please, Sign In to add comment