Submission #291669

#	Time	Username	Problem	Language	Result	Execution time	Memory
291669		penguinhacker	Zapina (COCI20_zapina)	C++17	110 / 110	640 ms	512 KiB

zapina

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

#define ll long long
#define ar array

const int MOD=1e9+7;
int binPow(ll b, int p=MOD-2) {
	ll res=1;
	while(p>0) {
		if (p&1) res=res*b%MOD;
		b=b*b%MOD;
		p>>=1;
	}
	return res;
}

vector<ll> f={1}, iF={1};
ll C(int a, int b) {
	if (a<0||b<0||b>a) return 0;
	assert(a<=(int)5e6);
	while(f.size()<=a) {
		int x=f.size();
		f.push_back(f.back()*x%MOD);
		iF.push_back(iF.back()*binPow(x)%MOD);
	}
	return f[a]*iF[b]%MOD*iF[a-b]%MOD;
}

int n;
vector<vector<ll>> dp, last;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	dp.assign(n+1, vector<ll>(2, 0));
	dp[0][0]=1;
	for (int i=1; i<=n; ++i) {
		last=dp;
		for (int j=i; j<=n; ++j) {
			dp[j][1]=(dp[j][1]+(last[j-i][0]+last[j-i][1])*C(n-j+i, i))%MOD;
		}
		for (int j=1; j<=n; ++j) {
			for (int k=1; k<=j; ++k) if (k!=i) {
				dp[j][1]=(dp[j][1]+last[j-k][1]*C(n-j+k, k))%MOD;
				dp[j][0]=(dp[j][0]+last[j-k][0]*C(n-j+k, k))%MOD;
			}
		}
	}
	cout << dp[n][1] << "\n";
	return 0;
}

Compilation message (stderr)

zapina.cpp: In function 'long long int C(int, int)':
zapina.cpp:22:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |  while(f.size()<=a) {
      |        ~~~~~~~~^~~

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