제출 #857385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857385		MilosMilutinovic	Zapina (COCI20_zapina)	C++14	110 / 110	285 ms	1768 KiB

zapina

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int cys=1e9+7;
int fct[355],inv[355];
void ckadd(int& x,int y){ x+=y; if(x>=cys) x-=cys; }
int ckmul(int x,int y){ return (1ll*x*y)%cys; }
int ckpow(int a,int b) { int res=1; for(;b;b>>=1,a=ckmul(a,a)){ if(b&1) res=ckmul(res,a); } return res; }
int C(int x,int y){ return ckmul(fct[x],ckmul(inv[y],inv[x-y])); }
void init(){
	fct[0]=1;
	for(int i=1;i<=350;i++) fct[i]=ckmul(fct[i-1],i);
	inv[350]=ckpow(fct[350],cys-2);
	for(int i=349;i>=0;i--) inv[i]=ckmul(inv[i+1],i+1);
}

int dp[355][355][2];

int main(){
	init();
	int n=readint();
	dp[0][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int x=0;x<=n;x++){
			for(int f=0;f<2;f++){
				for(int y=0;x+y<=n;y++){
					int nf=(f|(y==i));
					ckadd(dp[i][x+y][nf],ckmul(C(n-x,y),dp[i-1][x][f]));
				}
			}	
		}
	}
	printf("%d\n",dp[n][n][1]);
	return 0;
}

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