Submission #724117

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
724117	2023-04-14T18:13:47 Z	amirhoseinfar1385	Tents (JOI18_tents)	C++17	100 / 100	466 ms	71100 KB

tents

#include<bits/stdc++.h>
using namespace std;
const int maxn=3000+10;
long long fact[maxn],revfact[maxn],mp[maxn];
long long mod=1e9+7;
long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}	
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}

void aval(){
	fact[0]=1;
	for(int i=1;i<maxn;i++){
		fact[i]=fact[i-1]*i;
		fact[i]%=mod;
	}
	revfact[maxn-1]=mypow(fact[maxn-1],mod-2);
	for(int i=maxn-2;i>=0;i--){
		revfact[i]=revfact[i+1]*(i+1)%mod;
	}
	mp[0]=1;
	for(int i=1;i<maxn;i++){
		mp[i]=mp[i-1]*4%mod;
	}	
}
long long dp[maxn][maxn];
long long c(int i,int j){
	if(i<0||j<0||j>i){
		return 0;
	}
	long long ret=fact[i]*revfact[j]%mod*revfact[i-j]%mod;
	return ret;
}
long long pre[maxn];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long n,m;
	cin>>n>>m;
	aval();
	//cout<<"whhat "<<c(2,2)<<'\n';
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(i==0){
				dp[i][j]=1;
				continue;
			}
			if(j==0){
				dp[i][j]=0;
				continue;
			}
			dp[i][j]=dp[i-1][j-1]*j%mod*4%mod;
			if(i>=2){
				dp[i][j]+=dp[i-2][j-1]*j%mod*(i-1)%mod;
			}
			dp[i][j]%=mod;
		}	
	}
	pre[0]=1;
	for(int i=1;i*2<=m;i++){
		pre[i]=pre[i-1];
		pre[i]*=c(m-(i-1)*2,2);
		pre[i]%=mod;
	}	
	long long res=0;
	for(int i=0;i<=n&&i*2<=m;i++){
		for(int j=0;j+i<=n;j++){
			if(i+j==0){
				continue;
			}	
			long long fake=c(n,i)*c(n-i,j)%mod*pre[i]%mod*dp[j][m-i*2]%mod;
			//cout<<i<<" "<<j<<" "<<c(n,i)<<" "<<c(n-i,j)<<" "<<pre[i]<<" "<<dp[j][m-i*2]<<" "<<fake<<"\n";
			res+=fake;
		}
	}
	res%=mod;
	cout<<res<<"\n";
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	584 KB	Output is correct
4	Correct	1 ms	1224 KB	Output is correct
5	Correct	1 ms	780 KB	Output is correct
6	Correct	2 ms	1364 KB	Output is correct
7	Correct	2 ms	840 KB	Output is correct
8	Correct	2 ms	1492 KB	Output is correct
9	Correct	1 ms	852 KB	Output is correct
10	Correct	4 ms	1876 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	6 ms	2312 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	584 KB	Output is correct
4	Correct	1 ms	1224 KB	Output is correct
5	Correct	1 ms	780 KB	Output is correct
6	Correct	2 ms	1364 KB	Output is correct
7	Correct	2 ms	840 KB	Output is correct
8	Correct	2 ms	1492 KB	Output is correct
9	Correct	1 ms	852 KB	Output is correct
10	Correct	4 ms	1876 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	6 ms	2312 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	4 ms	9684 KB	Output is correct
15	Correct	318 ms	55268 KB	Output is correct
16	Correct	13 ms	4052 KB	Output is correct
17	Correct	57 ms	12932 KB	Output is correct
18	Correct	88 ms	17152 KB	Output is correct
19	Correct	356 ms	63052 KB	Output is correct
20	Correct	283 ms	50948 KB	Output is correct
21	Correct	180 ms	33824 KB	Output is correct
22	Correct	186 ms	35552 KB	Output is correct
23	Correct	110 ms	27084 KB	Output is correct
24	Correct	466 ms	71100 KB	Output is correct
25	Correct	356 ms	61368 KB	Output is correct
26	Correct	411 ms	66956 KB	Output is correct
27	Correct	460 ms	69248 KB	Output is correct