Submission #873688

#	Time	Username	Problem	Language	Result	Execution time	Memory
873688		maxFedorchuk	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	106 ms	131892 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
const long long MOD=1e9+7;
const long long MX=2100;
long long dp[MX][MX][4]={0};
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    long long n,s,f;
    cin>>n>>s>>f;

    dp[1][1][0]=1;

    for(long long i=1;i<n;i++)
    {
        for(long long k=1;k<n;k++)
        {
            if((i+1)<=s)
            {
                dp[i+1][k][2]=(dp[i+1][k][2]+dp[i][k][0])%MOD;
                dp[i+1][k][3]=(dp[i+1][k][3]+dp[i][k][1])%MOD;
            }

            if((i+1)<=f)
            {
                dp[i+1][k][1]=(dp[i+1][k][1]+dp[i][k][0])%MOD;
                dp[i+1][k][3]=(dp[i+1][k][3]+dp[i][k][2])%MOD;
            }



            if((i+1)!=s && (i+1)!=f)
            {
                dp[i+1][k-1][0]=(dp[i+1][k-1][0]+dp[i][k][0]*(k-1))%MOD;
                dp[i+1][k-1][1]=(dp[i+1][k-1][1]+dp[i][k][1]*(k-1))%MOD;
                dp[i+1][k-1][2]=(dp[i+1][k-1][2]+dp[i][k][2]*(k-1))%MOD;
                dp[i+1][k-1][3]=(dp[i+1][k-1][3]+dp[i][k][3]*(k-1))%MOD;
            }


            if((i+1)==s)
            {
                dp[i+1][k+1][0]=(dp[i+1][k+1][0]+dp[i][k][0])%MOD;
                dp[i+1][k+1][1]=(dp[i+1][k+1][1]+dp[i][k][1])%MOD;
                continue;
            }

            if((i+1)==f)
            {
                dp[i+1][k+1][0]=(dp[i+1][k+1][0]+dp[i][k][0])%MOD;
                dp[i+1][k+1][2]=(dp[i+1][k+1][2]+dp[i][k][2])%MOD;
                continue;
            }

            if((i+1)<f && (i+1)<s)
            {
                dp[i+1][k+1][0]=(dp[i+1][k+1][0]+dp[i][k][0]*(k+1))%MOD;
                dp[i+1][k+1][1]=(dp[i+1][k+1][1]+dp[i][k][1]*k)%MOD;
                dp[i+1][k+1][2]=(dp[i+1][k+1][2]+dp[i][k][2]*k)%MOD;
                dp[i+1][k+1][3]=(dp[i+1][k+1][3]+dp[i][k][3]*(k-1))%MOD;
                continue;
            }

            if((i+1)>f && (i+1)>s)
            {
                dp[i+1][k+1][0]=(dp[i+1][k+1][0]+dp[i][k][0]*(k-1))%MOD;
                dp[i+1][k+1][1]=(dp[i+1][k+1][1]+dp[i][k][1]*(k-1))%MOD;
                dp[i+1][k+1][2]=(dp[i+1][k+1][2]+dp[i][k][2]*(k-1))%MOD;
                dp[i+1][k+1][3]=(dp[i+1][k+1][3]+dp[i][k][3]*(k-1))%MOD;
                continue;
            }

            if(s<(i+1) && (i+1)<f)
            {
                dp[i+1][k+1][0]=(dp[i+1][k+1][0]+dp[i][k][0]*k)%MOD;
                dp[i+1][k+1][1]=(dp[i+1][k+1][1]+dp[i][k][1]*(k-1))%MOD;
                dp[i+1][k+1][2]=(dp[i+1][k+1][2]+dp[i][k][2]*k)%MOD;
                dp[i+1][k+1][3]=(dp[i+1][k+1][3]+dp[i][k][3]*(k-1))%MOD;
                continue;
            }

            if(f<(i+1) && (i+1)<s)
            {
                dp[i+1][k+1][0]=(dp[i+1][k+1][0]+dp[i][k][0]*k)%MOD;
                dp[i+1][k+1][1]=(dp[i+1][k+1][1]+dp[i][k][1]*k)%MOD;
                dp[i+1][k+1][2]=(dp[i+1][k+1][2]+dp[i][k][2]*(k-1))%MOD;
                dp[i+1][k+1][3]=(dp[i+1][k+1][3]+dp[i][k][3]*(k-1))%MOD;
                continue;
            }
        }
    }

    cout<<(dp[n][1][0]+dp[n][1][1]+dp[n][1][2]+dp[n][1][3])%MOD<<"\n";
    return 0;
}

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