제출 #1341312

#제출 시각아이디문제언어결과실행 시간메모리
1341312PieArmyTents (JOI18_tents)C++20
100 / 100
82 ms35720 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

const int mod=1e9+7;

int sum(int x,int y){
	if(x+y<mod)return x+y;
	return x+y-mod;
}

int sub(int x,int y){
	if(x-y<0)return x-y+mod;
	return x-y;
}

int mul(ll x,ll y){
	return x*y%mod;
}

int n,m;
int dp[3023][3023];

signed main(){
	ios_base::sync_with_stdio(23^23);cin.tie(0);
	cin>>n>>m;
	dp[1][m]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			dp[i+1][j]=sum(dp[i+1][j],dp[i][j]);
			if(j>0){
				dp[i+1][j-1]=sum(dp[i+1][j-1],mul(dp[i][j],mul(4,j)));
				dp[i+2][j-1]=sum(dp[i+2][j-1],mul(dp[i][j],mul(j,n-i)));
			}
			if(j>1){
				int x=j,y=j-1;
				if(x&1)y/=2;
				else x/=2;
				dp[i+1][j-2]=sum(dp[i+1][j-2],mul(dp[i][j],mul(x,y)));
			}
		}
	}
	int ans=0;
	for(int i=0;i<m;i++){
		ans=sum(ans,dp[n+1][i]);
	}
	cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...