제출 #973154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
973154		8pete8	캥거루 (CEOI16_kangaroo)	C++17	100 / 100	149 ms	125772 KiB

kangaroo

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define int long long
#define double long double
const int mod=1e9+7,mxn=1e5+5,lg=60,inf=1e18,minf=-1e18,Mxn=1e6+50000;
int dp[2002][2002][2][2];
int32_t main(){
	fastio
	int n,x,y;cin>>n>>x>>y;
	dp[1][2][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=0;k<2;k++)for(int g=0;g<2;g++){
				//create
				if(i==x||i==y){
					dp[i+1][j][k][g]=dp[i][j][k][g];
					continue;
				}
				dp[i+1][j+1][k][g]=(dp[i+1][j+1][k][g]+(dp[i][j][k][g]*(j-1))%mod)%mod;//not counting gap before x and after y
				//merge
				int mul=j-1;
				bool lvalid=((i>x)||k),rvalid=((i>y)||g);
				if(j==2){
					if(lvalid&&rvalid)mul=1;
					else mul=0;//cant merge them
				}
				else{
					if(!lvalid)mul--;
					if(!rvalid)mul--;
				}
				dp[i+1][j-1][k][g]=(dp[i+1][j-1][k][g]+(dp[i][j][k][g]*mul)%mod)%mod;
				/*
				so we are over counting because when merging there might be case like
				cs=3 and merge 3->2<-1 which wont be correct
				so we can merge only i>x or k==1
				*/
				if(i<x&&!k)dp[i+1][j][1][g]=(dp[i+1][j][1][g]+(dp[i][j][k][g]))%mod;
				if(i<y&&!g)dp[i+1][j][k][1]=(dp[i+1][j][k][1]+dp[i][j][k][g])%mod;
			}
		}
	}
	int ans=0;
	for(int i=0;i<2;i++)for(int j=0;j<2;j++)ans=(ans+dp[n+1][1][i][j])%mod;
	cout<<ans;
	return 0;
}
/*
start with 2 comp
cs cf
i->n i!=cs&&cf
we can merge 2 component as everything in border of both com is <i
or create new com with only i
or put 1 right next to cs if i<cs
or put 1 before cf if i<cf
so dp[i][num of com][put next to cs?][put before cf?]
*/

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49