Submission #1219675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219675		boclobanchat	Tents (JOI18_tents)	C++20	100 / 100	204 ms	71056 KiB

tents

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3005;
const long long mod=1e9+7;
long long fr[MAXN],inv[MAXN],dp[MAXN][MAXN];
long long poww(long long n,long long m)
{
	long long res=n,ans=1;
	while(m)
	{
		if(m&1) ans=ans*res%mod;
		res=res*res%mod,m/=2;
	}
	return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    dp[0][0]=fr[0]=inv[0]=1;
    for(int i=1;i<=max(n,m);i++) inv[i]=poww(fr[i]=fr[i-1]*i%mod,mod-2);
    for(int i=1;i<=n;i++) for(int j=0;j<=m;j++)
    {
    	dp[i][j]=dp[i-1][j];
    	if(j>0) dp[i][j]=(dp[i][j]+dp[i-1][j-1]*(m-j+1)*4)%mod;
    	if(j>1) dp[i][j]=(dp[i][j]+dp[i-1][j-2]*(m-j+1)%mod*(m-j+2)%mod*500000004)%mod;
	}
	long long ans=0;
	for(int i=n;i>=0;i-=2) for(int j=0;j<=m;j++) if(m-j-(n-i)/2>=0)
		ans=(ans+dp[i][j]*fr[n]%mod*inv[i]%mod*inv[n-i]%mod*fr[m-j]%mod*inv[(n-i)/2]%mod*inv[m-j-(n-i)/2]%mod*fr[n-i]%mod*poww(500000004,(n-i)/2)%mod)%mod;
	cout<<(ans-1+mod)%mod;
}

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