【BZOJ】3026: 樓梯染色-卡特蘭數&盧卡斯定理&CRT

傳送門:bzoj3026

題解

題意不清楚，解釋一下：

對于一個高度為 n n n的階梯柱狀圖：

x

xx

xxx

求用 n n n個長方形覆寫全圖(不重疊，且完全覆寫)的總方案數 f ( n ) f(n) f(n)，答案即 K f ( n ) K^{f(n)} Kf(n)

每行最後一個方格顯然是屬于不同長方形的，考慮染了最上一行後的變化情況：

A

AB

CCC

假設選擇的是A區域這個長方形，顯然接下來不能存在長方形跨過BC區域。

是以方案數 f ( n ) = ∑ i = 0 n − 1 f ( i ) f ( n − 1 − i ) f(n)=\sum\limits_{i=0}^{n-1}f(i)f(n-1-i) f(n)=i=0∑n−1​f(i)f(n−1−i)

是以 f ( n ) f(n) f(n)為卡特蘭數 ( n + n n ) − ( n + n n − 1 ) \binom {n+n}{n}-\binom{n+n}{n-1} (nn+n​)−(n−1n+n​)

接下來就是求解 f ( n ) ( m o d φ ( m o d ) ) f(n)\pmod {\varphi( mod)} f(n)(modφ(mod))的值，将 φ ( m o d ) \varphi( mod) φ(mod)質因數分解後以每個質因數為模盧卡斯定理求出 ( n + n n ) \binom {n+n}{n} (nn+n​)和 ( n + n n − 1 ) \binom {n+n}{n-1} (n−1n+n​)，再CRT合并即可。

代碼

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000123,N=1e5+10,M=mod-1;
typedef long long ll;
const int mo[6]={2,3,11,2089,7253},w=5;

int n,K,ans,frc[10000],bs,p;

inline int sqr(int x){return (ll)x*x%p;} 

inline int fp(int x,int y)
{
	int re=1;
	for(;y;y>>=1,x=(ll)x*x%p)
	 if(y&1) re=(ll)re*x%p;
	return re;
}

void exgcd(int a,int b,int &x,int &y)
{
	if(!b) 	{x=1;y=0;return;}
	exgcd(b,a%b,y,x);y-=(a/b)*x;
}

inline int inv(int n)
{
	int x,y;
	exgcd(n,p,x,y);
	return (x%p+p)%p;
}

inline int C(int n,int m)
{
	if(m>n) return 0;
	int i,re=1,x,y;
	for(i=1;i<=m;++i){
		x=(ll)(n-i+1)*inv(i)%p;
		re=(ll)re*x%p; 
	}
	return re;
}

inline int lucas(int n,int m)
{
	if(!m) return 1;
	if(n<p) return C(n,m); 
    return (ll)lucas(n/p,m/p)*C(n%p,m%p)%p;
}

int sol(int n)
{return (lucas(n+n,n)-lucas(n+n,n-1)+M)%M*(ll)(M/p)%M*(ll)fp((M/p)%p,p-2)%M;}

int main(){
	int i;
	while(scanf("%d%d",&n,&K)!=EOF){ 
	for(ans=i=0;i<5;++i) {p=mo[i];ans=(ans+sol(n))%M;}
	  p=mod;printf("%d\n",fp(K,ans));
	} 
	return 0;
}