Submission #1223012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223012		vivkostov	Tents (JOI18_tents)	C++20	100 / 100	136 ms	82984 KiB

tents

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const long long int mod=1e9+7;
long long int n,m,dp[3005][3005],c[3005][3005],fac[3005];
long long int step(long long int base,long long int pow)
{
    long long int z=base;
    base=1;
    for(long long int i=0;i<=30;i++)
    {
        if(pow&(1<<i))
        {
            base*=z;
            base=base%mod;
        }
        z*=z;
        z=z%mod;
    }
    return base;
}
void prec()
{
    fac[0]=1;
    fac[1]=1;
    for(int i=2;i<=3000;i++)
    {
        fac[i]=(fac[i-1]*i)%mod;
    }
    for(int i=2;i<=3000;i++)
    {
        for(int j=2;j<=2;j++)
        {
            c[i][j]=(fac[i]*step((fac[j]*fac[i-j])%mod,mod-2))%mod;
        }
    }
}
void read()
{
    cin>>n>>m;
    prec();
    dp[n][m]=1;
    long long int otg=0;
    for(int i=n;i>=0;i--)
    {
        for(int j=m;j>=0;j--)
        {
            if(i)
            {
                dp[i-1][j]+=dp[i][j];
                dp[i-1][j]=dp[i-1][j]%mod;
            }
            if(i&&j)
            {
                dp[i-1][j-1]+=dp[i][j]*4*j;
                dp[i-1][j-1]=dp[i-1][j-1]%mod;
            }
            if(i>=2&&j)
            {
                dp[i-2][j-1]+=dp[i][j]*j*(i-1);
                dp[i-2][j-1]=dp[i-2][j-1]%mod;
            }
            if(i&&j>=2)
            {
                dp[i-1][j-2]+=dp[i][j]*c[j][2];
                dp[i-1][j-2]=dp[i-1][j-2]%mod;
            }
            if(i==0&&j!=m)
            {
                otg+=dp[i][j];
                otg=otg%mod;
            }
        }
    }
    cout<<otg<<endl;
}
int main()
{
    speed();
    read();
    return 0;
}

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