oj.uz

Submission #569100

# Submission time Handle Problem Language Result Execution time Memory
569100 2022-05-26T16:37:43 Z Redhood Kangaroo (CEOI16_kangaroo) C++14
0 / 100
 1 ms 212 KB 
#include<bits/stdc++.h>

#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pb push_back

typedef long long ll;
typedef long double ld;

using namespace std;

#define all(x) (x).begin(), (x).end()
const int mod = (int)1e9 + 7;
const int N = 2001;
void md(int &a){
    if(a >= mod)
        a-=mod;
}
int binpow(int a , int b){
    if(b == 0)return 1;
    int ans = binpow(a , b >> 1);
    ans = (1ll * ans * ans) % mod;
    if(b & 1)
        ans = (1ll * ans * a) % mod;
    return ans;
}
int INV(int x){
    return binpow(x , mod - 2);
}
int dp[2][N];
signed main(){
    int n , a , b;
    cin >> n >> a >> b;

    int bt = 0;



    dp[bt][0] = 1;

    int inv = 1;
    for(int i = 0; i < n - 2; ++i)
        inv *= 2;
    inv = INV(inv);

    int met = 0;
    int inv2 = INV(2);
    for(int i = n; i >= 1; --i){
        /// okay so?
        bt ^= 1;
        fill(dp[bt] , dp[bt] + N , 0);
        if(i == a || i == b){
            for(int j = 0; j <= n-i;++j){
                /// either add or what
                dp[bt][j + 1] += dp[bt^1][j];
                md(dp[bt][j + 1]);
                int t = j - met;
                if(t >= 0){
                    dp[bt][j] += (1ll * dp[bt^1][j] * t % mod * 2 % mod);
                    md(dp[bt][j]);
                }
                if(i == 1){
                    dp[bt][j - 1] += dp[bt^1][j];
                    md(dp[bt][j-1]);
                }
            }
            met++;
        }else{

            for(int j = 0; j <= n-i;++j){
                /// either add or what
                dp[bt][j + 1] += 1ll * dp[bt^1][j] * inv2 % mod;
                md(dp[bt][j + 1]);
                int t = j - met;
                if(t >= 0){
                    if(j >= 0)
                    dp[bt][j - 1] += (1ll * dp[bt^1][j] * t % mod * (t - 1) % mod * 4 % mod), md(dp[bt][j - 1]);
                    if(j >= 0)
                    dp[bt][j - 1] += (1ll * dp[bt^1][j] * t % mod * 2 % mod * met % mod), md(dp[bt][j - 1]);
                    if(i == 1){
                        dp[bt][j - 1] += dp[bt^1][j];
                        md(dp[bt][j-1]);
                    }
                }
            }
        }
//        cerr << " after " << i << '\n';
//        for(int x = 0; x <= n - i + 1; ++x)
//            cerr << dp[bt][x] << ' ';
//        cerr << '\n';
    }
    int ans = dp[bt][1];
    cout << ans;
    return 0;
}
/*
*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -