Submission #350015

#	Time	Username	Problem	Language	Result	Execution time	Memory
350015		arnold518	Zapina (COCI20_zapina)	C++14	110 / 110	179 ms	2540 KiB

zapina

#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 350;
const ll MOD = 1e9+7;

ll mypow(ll x, ll y)
{
	if(y==0) return 1;
	if(y%2) return mypow(x, y-1)*x%MOD;
	ll t=mypow(x, y/2);
	return t*t%MOD;
}

int N;
ll ifac[MAXN+10];
ll dp[MAXN+10][MAXN+10][2];

int main()
{
	scanf("%d", &N); 

	ifac[0]=1;
	for(int i=1; i<=N; i++) ifac[i]=ifac[i-1]*mypow(i, MOD-2)%MOD;

	dp[0][0][0]=1;
	for(int i=1; i<=N; i++)
	{
		for(int j=0; j<=N; j++)
		{
			for(int k=0; k<=j; k++)
			{
				if(j-k==i)
				{
					dp[i][j][1]+=dp[i-1][k][1]*ifac[j-k]%MOD;
					dp[i][j][1]+=dp[i-1][k][0]*ifac[j-k]%MOD;
					dp[i][j][1]%=MOD;
				}
				else
				{
					dp[i][j][0]+=dp[i-1][k][0]*ifac[j-k]%MOD;
					dp[i][j][1]+=dp[i-1][k][1]*ifac[j-k]%MOD;

					dp[i][j][0]%=MOD;
					dp[i][j][1]%=MOD;
				}
			}
		}
	}
	ll ans=dp[N][N][1];
	for(int i=1; i<=N; i++) ans=ans*i%MOD;
	printf("%lld\n", ans);
}

Compilation message (stderr)

zapina.cpp: In function 'int main()':
zapina.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~

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