Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define _ ios_base::sync_with_stdio(0);cin.tie(0);
- #define endl '\n'
- #define f first
- #define s second
- #define pb push_back
- typedef long long ll;
- typedef pair<int, int> ii;
- const int INF = 0x3f3f3f3f;
- const ll LINF = 0x3f3f3f3f3f3f3f3fll;
- const int MAX = 5e3+10, MOD = 1e9+7;
- int dp[MAX][MAX];
- int sulf[MAX][MAX];
- int sulf_pa[MAX][MAX];
- inline int multmod(int a, int b){
- return ll(a)*b % MOD;
- }
- int main(){ _
- int s, b; cin >> s >> b;
- for (int i = 1; i <= b; i++) dp[i][i] = 1;
- for (int j = 1; j <= b; j++) {
- for (int i = 1; i < j; i++) {
- // soma de PA da dp[x][j-i] para x \in {1, ..., i}
- // sum = (sum - sulf[j-i][i+1] + MOD) % MOD;
- int sum = sulf[j-i][1] - sulf[j-i][i+1];
- if(sum < 0) sum += MOD;
- // ans = (sulf_pa[j-i][1] - multmod(s-i, sum) + MOD) % MOD;
- int ans = sulf_pa[j-i][1] - multmod(s-i, sum);
- if(ans < 0) ans += MOD;
- // ans = (ans - sulf_pa[j-i][i+1] + MOD) % MOD;
- ans = ans - sulf_pa[j-i][i+1];
- if(ans < 0) ans += MOD;
- dp[j][i] = ans;
- }
- sulf[j][s] = dp[j][s];
- sulf_pa[j][s] = dp[j][s];
- for (int i = s-1; i > 0; i--) {
- // sulf[j][i] = (dp[j][i] + sulf[j][i+1]) % MOD;
- sulf[j][i] = dp[j][i] + sulf[j][i+1];
- if (sulf[j][i] >= MOD) sulf[j][i] -= MOD;
- // sulf_pa[j][i] = (multmod(dp[j][i], s-i+1) + sulf_pa[j][i+1]) % MOD ;
- sulf_pa[j][i] = multmod(dp[j][i], s-i+1) + sulf_pa[j][i+1];
- if(sulf_pa[j][i] >= MOD) sulf_pa[j][i] -= MOD;
- }
- }
- cout << dp[b][s] << endl;
- exit(0);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement