Submission #282929

#	Time	Username	Problem	Language	Result	Execution time	Memory
282929		AMO5	Zapina (COCI20_zapina)	C++17	110 / 110	180 ms	3832 KiB

zapina

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end()  
#define sz(x) int(x.size()) 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

const ll INF=63;
const int mxn=400;
bool DEBUG=0;

ll choose[mxn][mxn],dp[mxn][mxn][2];

void jia(ll &a, ll b){
	a=1ll*(a+b)%MOD;
}

ll mul(ll a, ll b){
	return 1ll*a*b%MOD;
}

ll modpow(ll a, ll b){
	ll res = 1ll;
	while(b){
		if(b&1)jia(res,a);
		mul(a,a);
		b/=2;
	}
	return res%MOD;
}

void init(){
	for(int i=0; i<mxn; i++){
		choose[i][0]=1ll;
		for(int j=1; j<=i; j++){
			choose[i][j]=(choose[i-1][j-1]+choose[i-1][j])%MOD;
		}
	}
}

int n;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    init();
    cin>>n;
    dp[1][0][0]=dp[1][1][1]=1;
    for(int i=2; i<=n; i++)
		dp[1][i][0]=1;
    for(int i=2; i<=n; i++){
		for(int j=0; j<=n; j++){
			for(int k=0; k<=j; k++){
				if(k==i){
					jia(dp[i][j][1],mul(dp[i-1][j-k][0],choose[j][k]));
					jia(dp[i][j][1],mul(dp[i-1][j-k][1],choose[j][k]));
				}else{
					jia(dp[i][j][0],mul(dp[i-1][j-k][0],choose[j][k]));
					jia(dp[i][j][1],mul(dp[i-1][j-k][1],choose[j][k]));
				}
			}
		}
	}
	cout<<dp[n][n][1];
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

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