Submission #999579

#	Time	Username	Problem	Language	Result	Execution time	Memory
999579		codefox	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	49 ms	31836 KiB

kangaroo

#include<bits/stdc++.h>

using namespace std;

#define int long long
int mod = 1e9+7;

int32_t main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n, a, b;
    cin >> n >> a >> b;
    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
    dp[1][1] = 1;
    int bb = 0;
    if (a==1) bb++;
    if (b==1) bb++;
    for (int i = 2; i <= n; i++)
    {
        if (i==a) 
        {
            dp[i] = vector<int>(dp[i-1]);
            i++;
            bb++;
        }
        if (i==b)
        {
            if (n%2==0)
            {
                for (int j = 2; j <= n; j++)
                {
                    dp[i][j] += dp[i-1][j-1];
                }
            }
            else
            {
                dp[i] = vector<int>(dp[i-1]);
            }
            i++;
            bb++;
        }
        if (i==a) 
        {
            dp[i] = vector<int>(dp[i-1]);
            i++;
            bb++;
        }
        if (i>n) break;
        for (int j = 2; j <=n; j++)
        {
            dp[i][j] += dp[i-1][j-1]*(j);
            dp[i][j] -= dp[i-1][j-1]*bb;
            dp[i][j-1] += dp[i-1][j]*(j-1);
        }
        for (int j = 1; j <= n; j++) dp[i][j]%=mod;
    }
    int sol = dp[n][1];
    dp.assign(n+1, vector<int>(n+1, 0));
    dp[1][1] =1;
    bb=0;
    if (a==1) bb++;
    if (b==1) bb++;
    for (int i = 2; i <= n; i++)
    {
        if (i==a) 
        {
            for (int j = 2; j <= n; j++)
            {
                dp[i][j] += dp[i-1][j-1];
            }
            i++;
            bb++;
        }
        if (i==b)
        {
            if (n%2)
            {
                for (int j = 2; j <= n; j++)
                {
                    dp[i][j] += dp[i-1][j-1];
                }
            }
            else
            {
                dp[i] = vector<int>(dp[i-1]);
            }
            i++;
            bb++;
        }
        if (i==a) 
        {
            for (int j = 2; j <= n; j++)
            {
                dp[i][j] += dp[i-1][j-1];
            }
            i++;
            bb++;
        }
        if (i>n) break;
        for (int j = 2; j <=n; j++)
        {
            dp[i][j] += dp[i-1][j-1]*(j);
            dp[i][j] -= dp[i-1][j-1]*bb;
            dp[i][j-1] += dp[i-1][j]*(j-1);
        }
        for (int j = 1; j <= n; j++) dp[i][j]%=mod;
    }
    cout << (sol + dp[n][1])%mod;
}

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49