2020-2021:teams:namespace:牛客多校第六场
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:牛客多校第六场 [2020/07/30 17:31] great_designer [F] |
2020-2021:teams:namespace:牛客多校第六场 [2020/08/01 10:22] (当前版本) great_designer [I] |
||
|---|---|---|---|
| 行 734: | 行 734: | ||
| =====I===== | =====I===== | ||
| - | [[Stling数]] | + | 题目、解答与代码见[[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===== | =====K===== | ||
2020-2021/teams/namespace/牛客多校第六场.1596101467.txt.gz · 最后更改: 2020/07/30 17:31 由 great_designer
