2020-2021:teams:namespace:牛客多校第六场

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:namespace:牛客多校第六场 [2020/07/31 22:51]
203.208.60.72 ↷ 链接因页面移动而自动修正
+++ 2020-2021:teams:namespace:牛客多校第六场 [2020/08/01 10:22] (当前版本)
great_designer [I]
@@ 行 734: / 行 734: @@
 =====I=====
-[[stirling数]]
+题目、解答与代码见[[Stirling数]]。
-<hidden>
-<code C>
-#include<stdio.h>
-int MOD;
-long long powmod(long long x,int k)
-{
-	long long ans=1;
-	while(k)
-	{
-		if(k&1)
-		{
-			ans=ans*x%MOD;
-		}
-		x=x*x%MOD;
-		k>>=1;
-	}
-	return ans;
-}
-int getfact(int x,int *p)
-{
-	int t=x,sz=0;
-	int i;
-	for(i=2;i*i<=t;i++)
-	{
-		if(x%i==0)
-		{
-			p[++sz]=i;
-			while(x%i==0)
-			{
-				x/=i;
-			}
-		}
-	}
-	if(x>1)
-	{
-		p[++sz]=x;
-	}
-	return sz;
-}
-long long facd[1000005],facv[1000005];
-long long G,mi[1000005],inv[1000005];
-void pre()
-{
-	facd[0]=1;
-	int i;
-	for(i=1;i<MOD;i++)
-	{
-		facd[i]=facd[i-1]*i%MOD;
-	}
-	facv[MOD-1]=facd[MOD-1];
-	for(i=MOD-2;i>=0;i--)
-	{
-		facv[i]=facv[i+1]*(i+1)%MOD;
-	}
-	int prime[10];
-	int sz=getfact(MOD-1,prime);
-	for(G=1;;G++)
-	{
-		bool ok=1;
-		for(i=1;i<=sz;i++)
-		{
-			if(powmod(G,(MOD-1)/prime[i])==1)
-			{
-				ok=0;
-				break;
-			}
-		}
-		if(ok)
-		{
-			break;
-		}
-	}
-	mi[0]=1;
-	for(i=1;i<MOD-1;i++)
-	{
-		mi[i]=mi[i-1]*G%MOD;
-	}
-	inv[1]=1;
-	for(i=2;i<MOD;i++)
-	{
-		inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
-	}
-}
-long long C(long long n,long long m)
-{
-	return (n<m)?0:facd[n]*facv[m]%MOD*facv[n-m]%MOD;
-}
-long long calc(long long n,long long m)
-{
-	if(!m)
-	{
-		return 1;
-	}
-	if(n<m)
-	{
-		return 0;
-	}
-	return C(n%MOD,m%MOD)*calc(n/MOD,m/MOD)%MOD;
-}
-long long query(long long n,long long m)
-{
-	m=(n<m)?n:m;
-	long long s=0;
-	int i;
-	for(i=0;i<MOD-1;i++)
-	{
-		int x=mi[i];
-		if(x+n>MOD)
-		{
-			continue;
-		}
-		if(!i)
-		{
-			s=(s+(m+1)*facd[x+n-1]%MOD*facv[x-1])%MOD;
-		}
-		else
-		{
-			s=(s+(mi[(MOD-1-i*(m+1)%(MOD-1))%(MOD-1)]-1LL)*inv[mi[MOD-1-i]-1LL]%MOD*facd[x+n-1]%MOD*facv[x-1])%MOD;
-		}
-	}
-	s=(MOD-s)%MOD;
-	if(n==MOD-1)
-	{
-		s=(s-1LL+MOD)%MOD;
-	}
-	return s;
-}
-long long solve(long long n,long long m)
-{
-	long long u1=n/MOD,v1=n%MOD;
-	if(m<u1)
-	{
-		return 0;
-	}
-	m-=u1;
-	long long u2=m/(MOD-1),v2=m%(MOD-1);
-	long long s=0;
-	if(u2)
-	{
-		s=(s+(((u2-1)&1)?MOD-1:1)*calc(u1-1,u2-1)%MOD*query(v1,MOD-2))%MOD;
-	}
-	s=(s+((u2&1)?MOD-1:1)*calc(u1,u2)%MOD*query(v1,v2))%MOD;
-	if(v1==MOD-1&&u2)
-	{
-		s=(s+(((u2-1)&1)?MOD-1:1)*calc(u1-1,u2-1))%MOD;
-	}
-	return s*((u1&1)?MOD-1:1)%MOD;
-}
-int main()
-{
-	long long n,l,r;
-	scanf("%lld%lld%lld%d",&n,&l,&r,&MOD);
-	pre();
-	long long s1=solve(n,r);
-	long long s2=solve(n,l-1);
-	printf("%lld\n",(s1-s2+MOD)%MOD);
-	return 0;
-}
-</code>
-</hidden>
 =====K=====

2020-2021/teams/namespace/牛客多校第六场.1596207108.txt.gz · 最后更改: 2020/07/31 22:51 由 203.208.60.72