Submission #43993

#	Time	Username	Problem	Language	Result	Execution time	Memory
43993		zscoder	Tents (JOI18_tents)	C++17	100 / 100	395 ms	76744 KiB

tents

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

const int MOD = 1e9 + 7;

int add(int a, int b)
{
	a+=b; while(a>=MOD) a-=MOD;
	return a;
}

int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}

int C[3111][3111];
int fact[6111];
int pow2[6111];
int ipow2[6111];
int modpow(int a, int b)
{
	int r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a); b>>=1;
	}
	return r;
}

int choose(int a, int b)
{
	if(a<b) return 0;
	if(b==0) return 1;
	if(C[a][b]!=-1) return C[a][b];
	return (C[a][b] = add(choose(a-1,b-1), choose(a-1,b)));
}

int dp[3111][3111];

int solve(int a, int b)
{
	if(a==0) return 1;
	if(a<0||b<0) return 0;
	if(dp[a][b]!=-1) return dp[a][b];
	return (dp[a][b] = add(solve(a-1,b),add(mult(4*b, solve(a-1,b-1)), mult((b*(b-1))/2, solve(a-1,b-2)))));
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,m; cin>>n>>m;
	memset(C,-1,sizeof(C)); memset(dp,-1,sizeof(dp));
	fact[0]=1; pow2[0]=ipow2[0]=1;
	for(int i=1;i<=6001;i++)
	{
		pow2[i]=add(pow2[i-1],pow2[i-1]);
		ipow2[i] = modpow(pow2[i], MOD-2);
	}
	for(int i=1;i<=6001;i++) fact[i]=mult(fact[i-1],i);
	int ans=0;
	for(int i=0;i<=m;i++)
	{
		int coeff = mult(choose(m, i), mult(choose(n, 2*i), mult(fact[2*i], ipow2[i])));
		ans = add(ans, mult(coeff, solve(n - 2*i, m - i)));
	}
	ans=add(ans,MOD-1);
	cout<<ans<<'\n';
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52