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;
- struct mod{
- int num;
- mod(){}
- mod(int num_):num(num_){
- if (num < 0) num += MOD;
- }
- mod operator+(mod a){
- int x = this->num;
- x += a.num;
- if (x >= MOD) return x-MOD;
- return x;
- }
- mod operator-(mod a){
- int x = this->num;
- x -= a.num;
- if (x < 0) return x+MOD;
- return x;
- }
- mod operator*(mod b){
- int x = this->num;
- return ll(x)*b.num % MOD;
- }
- };
- mod dp[MAX][MAX];
- mod sulf[MAX][MAX];
- mod sulf_pa[MAX][MAX];
- 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++) {
- mod ans = 0;
- mod summ = sulf[j-i][1];
- summ = summ - sulf[j-i][i+1];
- ans = sulf_pa[j-i][1] - (mod(s-i)*summ) - sulf_pa[j-i][i+1];
- 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];
- sulf_pa[j][i] = (dp[j][i]*mod(s-i+1)) + sulf_pa[j][i+1];
- }
- }
- cout << dp[b][s].num << endl;
- exit(0);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement