제출 #749930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
749930		Trunkty	Zapina (COCI20_zapina)	C++14	110 / 110	426 ms	3396 KiB

zapina

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,mod=1e9+7;
int comb[355][355];
int dp[355][355][2];

int dopow(int x, int y){
    if(y==0){
        return 1;
    }
    int z = dopow(x,y/2);
    if(y%2){
        return (((z*z)%mod)*x)%mod;
    }
    else{
        return (z*z)%mod;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=0;i<=n;i++){
        comb[i][0] = 1;
        for(int j=1;j<=i;j++){
            comb[i][j] = comb[i][j-1]*(i-j+1LL);
            comb[i][j] %= mod;
            comb[i][j] *= dopow(j,mod-2);
            comb[i][j] %= mod;
        }
    }
    dp[0][n][0] = 1;
    for(int i=0;i<=n-1;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                if(j>=k){
                    dp[i+1][j-k][1] += dp[i][j][1]*comb[j][k];
                    dp[i+1][j-k][1] %= mod;
                    if(k==i+1){
                        dp[i+1][j-k][1] += dp[i][j][0]*comb[j][k];
                        dp[i+1][j-k][1] %= mod;
                    }
                    else{
                        dp[i+1][j-k][0] += dp[i][j][0]*comb[j][k];
                        dp[i+1][j-k][0] %= mod;
                    }
                }
            }
        }
    }
    cout << dp[n][0][1] << "\n";
    return 0;
}

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