제출 #1281809

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281809		Faisal_Saqib	Tents (JOI18_tents)	C++20	48 / 100	278 ms	1836 KiB

tents

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define ll long long
const int N=302,mod=1e9+7;
ll dp[N][N],ndp[N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    dp[m][0]=1;
    // ndp[m][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=m;k++)
            {
                // leave row empty
                ndp[j][k]+=dp[j][k];
                ndp[j][k]%=mod;
                // dp[j][k]*3*j --> dp[j-1][k] // face up left right
                if(j>0)
                {
                    ndp[j-1][k]+=(dp[j][k]*3*j)%mod;
                    ndp[j-1][k]%=mod;
                }
                
                // dp[j][k]*j  --> dp[j-1][k+1] // make it face down
                if(j>0)
                {
                    ndp[j-1][k+1]+=(dp[j][k]*j)%mod;
                    ndp[j-1][k+1]%=mod;
                }
                // dp[j][k]*(jC2) --> dp[j-2][k] // make them face each other
                if(j>1)
                {
                    ll w=((j*(j-1))/2)%mod;
                    ndp[j-2][k]+=(dp[j][k]*w)%mod;
                    ndp[j-2][k]%=mod;
                }
                // dp[j][k]*k --> dp[j][k-1] // Pair one of the previous facing down by making this one facing up
                if(k>0)
                {
                    ndp[j][k-1]+=(dp[j][k]*k)%mod;
                    ndp[j][k-1]%=mod;
                }
            }
        }
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=m;k++)
            {
                dp[j][k]=ndp[j][k];
                ndp[j][k]=0;
            }
        }
    }
    // summation dp 
    ll ans=0;
    for(int j=0;j<=m;j++)
    {
        for(int k=0;k<=m;k++)
        {
            ans+=dp[j][k];
            ans%=mod;
        }
    }
    ans=(ans+mod-1)%mod;
    cout<<ans<<endl;
}

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