Submission #914139

#	Time	Username	Problem	Language	Result	Execution time	Memory
914139		alexdd	Tents (JOI18_tents)	C++17	100 / 100	110 ms	141704 KiB

tents

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
int put(int a, int exp)
{
    if(exp==0)
        return 1;
    if(exp%2==0)
        return put((a*a)%MOD,exp/2);
    else
        return (put((a*a)%MOD,exp/2)*a)%MOD;
}
int cm[3005][3005];
int fact[6005];
int comb(int x, int y)
{
    return cm[x][y];
}
int dp[3005][3005];
signed main()
{
    fact[0]=1;
    for(int i=1;i<=6000;i++)
        fact[i]=(fact[i-1]*i)%MOD;
    for(int i=0;i<=3000;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(i==j)
                cm[i][j]=1;
            else if(j==0)
                cm[i][j]=1;
            else
                cm[i][j]=(cm[i-1][j-1]+cm[i-1][j])%MOD;
        }
    }
    int n,m;
    cin>>n>>m;
    dp[n][m]=1;
    for(int i=n;i>=0;i--)
    {
        for(int j=m;j>=0;j--)
        {
            if(i==n && j==m)
                continue;
            dp[i][j] += dp[i+1][j];
            dp[i][j] += (dp[i+1][j+1] * (j+1) * 4LL)%MOD;
            dp[i][j] += (dp[i+1][j+2] * comb(j+2,2))%MOD;
            dp[i][j] += (dp[i+2][j+1] * (i+1) * (j+1))%MOD;
            dp[i][j]%=MOD;
        }
    }
    int sum=MOD-1;
    for(int i=0;i<=m;i++)
        sum=(sum+dp[0][i])%MOD;
    cout<<sum;
    return 0;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52