【CF896D】Nephren Runs a Cinema

题意：一个序列中有n格数，每个数可能是0,1,-1，如果一个序列的所有前缀和都>=0且总和$\in [L,R]$，那么我们称这个序列是合法的。求合法序列的个数%P。

n,L,R<=100000，P<=2*10^9

题解：先不考虑0的数，那么总数显然就是卡特兰数的变形。我们将卡特兰数转换成在二维平面上，从(0,0)走到(a,b)，且不越过直线x=y的方案数。因为每个越过x=y的方案都可以转化成从(-1,1)走到(a,b)的方案，所以总方案数就是$C_{a+b}^b-C_{a+b}^{b-1}$。如果序列的总和为j，那么令a=(n+j)/2，b=(n-j)/2即可。如果我们要对$j\in [L,R]$的所有方案数求和，那么答案就变成$C_n^{\lfloor{n-L\over 2}\rfloor}-C_n^{\lceil{n-R\over r}\rceil}$。

那如果我们考虑0呢？如果i个人是0，那么总方案数*$C_n^i$即可。

但是问题来了，模数不是质数怎么办？还记得礼物那题吗？我们先将模数拆成$\prod p_i^{c_i}$的形式，然后对于$p_i^{c_i}$分开计算。我们希望把阶乘表示成$a*p^b$的形式，这样就可以支持除法了（a可以求逆元搞定，b可以直接相减），具体如何实现？我们将n!中p的倍数都拿出来，比如p=5，那么n!可以表示成
$n!=(1\times2\times3\times4\times6\times7\times8\times9\times11...)\times5^{\lfloor{n\over 5}\rfloor}\times(\lfloor{n\over 5}\rfloor)！$

对于前面那些东西我们可以预处理，后面那个阶乘我们递归算下去即可（也可以递推求出）。

最后用中国剩余定理合并即可。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const int maxn=100010;

ll n,L,R,cnt;

ll Pri,P,PP,phi,ans;

ll cp[10],cpp[10];

inline ll pm(ll x,ll y,ll z)

{

	ll ret=1;

	while(y)

	{

		if(y&1)	ret=ret*x%z;

		x=x*x%z,y>>=1;

	}

	return ret;

}

struct node

{

	ll x,y;

	node() {x=y=0;}

	node(ll a,ll b) {x=a,y=b;}

	node operator + (const node &a) {return node(x+a.x,y*a.y%PP);}

	node operator * (const int a) {return node(x*a,pm(y,a,PP));}

}jc[maxn],f[maxn];

inline ll c(ll a,ll b)

{

	if(b<0)	return 0;

	node x=f[a],y=f[a-b]+f[b];

	return pm(P,x.x-y.x,PP)*x.y%PP*pm(y.y,PP/P*(P-1)-1,PP)%PP;

}

inline ll solve()

{

	ll ret=0,i;

	memset(jc,0,sizeof(jc)),memset(f,0,sizeof(f));

	jc[0]=node(0,1);

	for(i=1;i<=min(n,PP-1);i++)

	{

		jc[i]=jc[i-1];

		if(i%P)	jc[i].y=jc[i].y*i%PP;

	}

	for(i=0;i<=min(n,P-1);i++)	f[i]=jc[i];

	for(;i<=n;i++)	f[i]=(n>=PP?(jc[PP-1]*(i/PP)):node(0,1))+jc[i%PP]+node(i/P,1)+f[i/P];

	for(i=L;i<=n;i++)	ret=(ret+c(n,i)*(c(i,i-(i+L+1)/2)-c(i,i-(i+R)/2-1)+PP))%PP;

	return ret;

}

int main()

{

	scanf("%I64d%I64d%I64d%I64d",&n,&Pri,&L,&R);

	int i;

	ll tmp=Pri;

	phi=1;

	for(i=2;i*i<=tmp;i++)

	{

		if(tmp%i==0)

		{

			tmp/=i,phi*=i-1;

			cp[++cnt]=i,cpp[cnt]=i;

			while(tmp%i==0)	tmp/=i,phi*=i,cpp[cnt]*=i;

		}

	}

	if(tmp!=1)	phi*=(tmp-1),cp[++cnt]=tmp,cpp[cnt]=tmp;

	for(i=1;i<=cnt;i++)

	{

		P=cp[i],PP=cpp[i];

		ans=(ans+(Pri/PP)*pm(Pri/PP,phi-1,Pri)%Pri*solve())%Pri;

	}

	printf("%I64d",ans);

	return 0;

}

巴特西

【CF896D】Nephren Runs a Cinema 卡特兰数+组合数+CRT

【CF896D】Nephren Runs a Cinema

最新文章

热门文章