Advertisement
Guest User

Untitled

a guest
Nov 11th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define _ ios_base::sync_with_stdio(0);cin.tie(0);
  6. #define endl '\n'
  7. #define f first
  8. #define s second
  9. #define pb push_back
  10.  
  11. typedef long long ll;
  12. typedef pair<int, int> ii;
  13.  
  14. const int INF = 0x3f3f3f3f;
  15. const ll LINF = 0x3f3f3f3f3f3f3f3fll;
  16.  
  17. const int MAX = 5e3+10, MOD = 1e9+7;
  18. int dp[MAX][MAX];
  19. int sulf[MAX][MAX];
  20. int sulf_pa[MAX][MAX];
  21.  
  22. inline int multmod(int a, int b){
  23.   return ll(a)*b % MOD;
  24. }
  25.  
  26. int main(){ _
  27.   int s, b; cin >> s >> b;
  28.   for (int i = 1; i <= b; i++) dp[i][i] = 1;
  29.   for (int j = 1; j <= b; j++) {
  30.     for (int i = 1; i < j; i++) {
  31.       // soma de PA da dp[x][j-i] para x \in {1, ..., i}
  32.       // sum = (sum - sulf[j-i][i+1] + MOD) % MOD;
  33.       int sum = sulf[j-i][1] - sulf[j-i][i+1];
  34.       if(sum < 0) sum += MOD;
  35.  
  36.       // ans = (sulf_pa[j-i][1] - multmod(s-i, sum) + MOD) % MOD;
  37.       int ans = sulf_pa[j-i][1] - multmod(s-i, sum);
  38.       if(ans < 0) ans += MOD;
  39.  
  40.       // ans = (ans - sulf_pa[j-i][i+1] + MOD) % MOD;
  41.       ans = ans - sulf_pa[j-i][i+1];
  42.       if(ans < 0) ans += MOD;
  43.      
  44.       dp[j][i] = ans;
  45.     }
  46.  
  47.     sulf[j][s] = dp[j][s];
  48.     sulf_pa[j][s] = dp[j][s];
  49.     for (int i = s-1; i > 0; i--) {
  50.       // sulf[j][i] = (dp[j][i] + sulf[j][i+1]) % MOD;
  51.       sulf[j][i] = dp[j][i] + sulf[j][i+1];
  52.       if (sulf[j][i] >= MOD) sulf[j][i] -= MOD;
  53.  
  54.       // sulf_pa[j][i] = (multmod(dp[j][i], s-i+1) + sulf_pa[j][i+1]) % MOD ;
  55.       sulf_pa[j][i] = multmod(dp[j][i], s-i+1) + sulf_pa[j][i+1];
  56.       if(sulf_pa[j][i] >= MOD) sulf_pa[j][i] -= MOD;
  57.     }
  58.   }
  59.  
  60.   cout << dp[b][s] << endl;
  61.   exit(0);
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement