Advertisement
Guest User

Untitled

a guest
Nov 11th, 2019
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.35 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.  
  19. struct mod{
  20.     int num;
  21.     mod(){}
  22.     mod(int num_):num(num_){
  23.         if (num < 0) num += MOD;
  24.     }
  25.     mod operator+(mod a){
  26.         int x = this->num;
  27.         x += a.num;
  28.         if (x >= MOD) return x-MOD;
  29.         return x;
  30.     }
  31.     mod operator-(mod a){
  32.         int x = this->num;
  33.         x -= a.num;
  34.         if (x < 0) return x+MOD;
  35.         return x;
  36.     }
  37.     mod operator*(mod b){
  38.         int x = this->num;
  39.         return ll(x)*b.num % MOD;
  40.     }
  41. };
  42.  
  43. mod dp[MAX][MAX];
  44. mod sulf[MAX][MAX];
  45. mod sulf_pa[MAX][MAX];
  46.  
  47. int main(){ _
  48.     int s, b; cin >> s >> b;
  49.     for (int i = 1; i <= b; i++) dp[i][i] = 1;
  50.     for (int j = 1; j <= b; j++) {
  51.         for (int i = 1; i < j; i++) {
  52.             mod ans = 0;
  53.             mod summ = sulf[j-i][1];
  54.             summ = summ - sulf[j-i][i+1];
  55.             ans = sulf_pa[j-i][1] - (mod(s-i)*summ) - sulf_pa[j-i][i+1];
  56.             dp[j][i] = ans;
  57.         }
  58.  
  59.         sulf[j][s] = dp[j][s];
  60.         sulf_pa[j][s] = dp[j][s];
  61.         for (int i = s-1; i > 0; i--) {
  62.             sulf[j][i] = dp[j][i] + sulf[j][i+1];
  63.  
  64.             sulf_pa[j][i] = (dp[j][i]*mod(s-i+1)) + sulf_pa[j][i+1];
  65.         }
  66.     }
  67.     cout << dp[b][s].num << endl;
  68.     exit(0);
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement