Submission #203369

#	Time	Username	Problem	Language	Result	Execution time	Memory
203369		vanic	Zapina (COCI20_zapina)	C++14	55 / 110	1096 ms	83108 KiB

zapina

#include <cstdio>

typedef long long ll;

const int maxn=355, mod=1e9+7, Log=30;

int fact[maxn];
int dp[maxn][maxn][2];

inline int sum(int a, int b){
	if(a+b>=mod){
		return a+b-mod;
	}
	else if(a+b<0){
		return a+b+mod;
	}
	return a+b;
}


inline int mul(int a, int b){
	return (ll)a*b%mod;
}


int pot(int a, int b){
	int sol=1;
	for(int i=0; i<Log; i++){
		if((1<<i)&b){
			sol=mul(sol, a);
		}
		a=mul(a, a);
	}
	return sol;
}

inline int dijel(int a, int b){
	return mul(a, pot(b, mod-2));
}

int n;
int povrh[maxn][maxn][maxn];

void precompute(){
	fact[0]=1;
	for(int i=1; i<maxn; i++){
		fact[i]=mul(fact[i-1], i);
	}
	for(int i=0; i<=n; i++){
		for(int j=0; j<=i; j++){
			povrh[n-j][i-j][n-i]=dijel(fact[n-j], mul(fact[i-j], fact[n-i]));
		}
	}
}

int main(){
	scanf("%d", &n);
	precompute();
	dp[0][0][0]=1;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=n; j++){
			for(int l=0; l<=j; l++){
				if(j-l==i){
/*						if(i==1 && j==1 && l==0 && k==1){
						cout << "da" << endl;
						cout << dp[i-1][l][k-1] << endl;
						cout <<  fact[j-l] <<  " " << fact[n-j] << endl;
					}*/
					dp[i][j][1]=sum(dp[i][j][1], mul(sum(dp[i-1][l][0], dp[i-1][l][1]), povrh[n-l][j-l][n-j]));
				}
				else{
					dp[i][j][0]=sum(dp[i][j][0], mul(dp[i-1][l][0], povrh[n-l][j-l][n-j]));
					dp[i][j][1]=sum(dp[i][j][1], mul(dp[i-1][l][1], povrh[n-l][j-l][n-j]));
				}
			}
		}
	}
	int sol=0;
//	cout << dp[2][2][1] << " " << dp[2][2][2] << endl;
	for(int j=1; j<30; j++){
//		cout << dp[n][n][j] << " ";
		sol=sum(sol, dp[n][n][j]);
	}
//	cout << endl;
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

zapina.cpp: In function 'int main()':
zapina.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
zapina.cpp:82:10: warning: iteration 1 invokes undefined behavior [-Waggressive-loop-optimizations]
   sol=sum(sol, dp[n][n][j]);
       ~~~^~~~~~~~~~~~~~~~~~
zapina.cpp:80:16: note: within this loop
  for(int j=1; j<30; j++){
               ~^~~

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