Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstdlib>
- #include <vector>
- #include <set>
- #include <map>
- #include <cassert>
- #include <ctime>
- #include <cmath>
- #include <string>
- #include <cstring>
- #include <queue>
- using namespace std;
- #define f first
- #define s second
- #define mp make_pair
- #define pb push_back
- #define pii pair<int, int>
- #define vi vector<int>
- #define all(v) (v).begin(), (v).end()
- #define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
- #define f0(a) memset(a, 0, sizeof(a))
- #define ll long long
- #ifdef WIN32
- #define I64 "%I64d"
- #else
- #define I64 "%lld"
- #endif
- const int mod = (int)1e9 + 7;
- ll dp[210][2000], cnt[210][2000];
- bool calced[210][2000];
- int n, dig;
- inline void Calc(int cur, int sum) {
- if (cur == n + n) {
- cnt[cur][sum] = (sum == 0);
- dp[cur][sum] = 0;
- return;
- }
- ll &ans = dp[cur][sum];
- if (calced[cur][sum]) return;
- calced[cur][sum] = true;
- cnt[cur][sum] = ans = 0;
- for (int i = 0; i < 10; ++i) {
- int nsum = (cur >= n) ? sum - i : sum + i;
- if (nsum < 0) break;
- Calc(cur + 1, nsum);
- ans = (ans + dp[cur + 1][nsum] + (i == dig) * cnt[cur + 1][nsum]) % mod;
- cnt[cur][sum] = (cnt[cur][sum] + cnt[cur + 1][nsum]) % mod;
- }
- }
- int main() {
- cin >> n;
- for (dig = 0; dig < 10; ++dig) {
- f0(calced);
- Calc(0, 0);
- cout << dp[0][0] << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment