有趣的数列 bzoj-1485 HNOI-2009

题目大意：求所有1~2n的排列满足奇数项递增，偶数项递增。相邻奇数项大于偶数项的序列个数%P。

注释：$1\le n\le 10^6$，$1\le P \le 10^9$。

想法：好题啊。

我们依次考虑1~2n，就是把当前$i$放进奇数项还是偶数项的问题。因为我们有相邻奇数项大于偶数项的问题。所以当前放进奇数项的个数不能多于放进偶数项的个数。

进而我们将放进奇数项比作进栈，放进偶数项比作出栈。

答案就相当于$n$的出栈入栈序的个数。

等于$Catalan_n$。

利用卡特兰数的通项公式：$Catalan_n=\frac{C_{2n}^{n}}{(n+1)}$。

$=\frac{(2n)!}{n!(n+1)!}$。

用枚举质因子的方式求每个质因子的贡献即可。

Code：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

ll mod;

bool vis[2000010];

int prime[2000010],cnt;

ll qmul(ll x,ll y)

{

	ll ans=0; x%=mod,y%=mod; while(y)

	{

		if(y&1) (ans+=x)%=mod;

		y>>=1;

		(x+=x)%=mod;

	}

	return ans;

}

ll qpow(ll x,ll y)

{

	ll ans=1; x%=mod; while(y)

	{

		if(y&1) (ans*=x)%=mod;

		y>>=1;

		(x*=x)%=mod;

	}

	return ans;

}

void init()

{

	for(int i=2;i<=2000000;i++)

	{

		if(!vis[i]) prime[++cnt]=i;

		for(int j=1;j<=cnt&&1ll*i*prime[j]<=2000000;j++)

		{

			vis[i*prime[j]]=true;

			if(i%prime[j]==0) break;

		}

	}

}

ll num(ll x,ll p)

{

	ll re=0; while(x)

	{

		re+=(x/p); x/=p;

	}

	return re;

}

int main()

{

	init();

	ll n; cin >> n >> mod ;

	ll ans=1;

	for(int i=1;i<=cnt&&prime[i]<=n*2;i++)

	{

		ans=qmul(ans,qpow(prime[i],num(2*n,prime[i])-num(n,prime[i])-num(n+1,prime[i])));

	}

	cout << ans << endl ;

	return 0;

}

小结：好题啊。关于模型的转化总是非常重要且巧妙的。

巴特西

[bzoj1485][HNOI2009]有趣的数列_卡特兰数_组合数

有趣的数列 bzoj-1485 HNOI-2009

最新文章

热门文章