제출 #1199838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199838		12345678	Zapina (COCI20_zapina)	C++20	110 / 110	151 ms	2484 KiB

zapina

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=351, mod=1e9+7;

ll n, dp[nx][nx], dp2[nx][nx], f[2*nx], inv[2*nx];

ll binpow(ll a, ll x)
{
    if (x==0) return 1;
    ll tmp=binpow(a, x/2);
    tmp=(tmp*tmp)%mod;
    if (x%2) return (tmp*a)%mod;
    else return tmp;
}

ll ncr(ll n, ll k)
{
    return ((f[n]*inv[k])%mod*inv[n-k])%mod;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    f[0]=1;
    for (int i=1; i<=2*n; i++) f[i]=(f[i-1]*i)%mod;
    inv[2*n]=binpow(f[2*n], mod-2);
    for (int i=2*n-1; i>=0; i--) inv[i]=(inv[i+1]*(i+1))%mod;
    dp[0][0]=dp2[0][0]=1;
    for (int i=1; i<=n; i++)
    {
        for (int j=0; j<=n; j++)
        {
            for (int g=0; g<=n; g++)
            {
                if (g<=j)
                {
                    if (g!=i) dp[i][j]=(dp[i][j]+dp[i-1][j-g]*ncr(n-(j-g), g))%mod;
                    dp2[i][j]=(dp2[i][j]+dp2[i-1][j-g]*ncr(n-(j-g), g))%mod;
                }
            }
        }
    }
    cout<<((dp2[n][n]-dp[n][n])%mod+mod)%mod;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55