传送门
想做好这个题真的真的好不容易啊T T，照旧记录一下……
题意：定义两种循环，第一种循环是直接从1-n，第二种循环是从上一层循环的数字到n，给出两种类型的循环，求最后总循环次数，再对364875103取模
思路：计算循环次数，第一种循环就不用说了，第二种循环是通过找规律归纳出来结果……第二种循环的开始一定是第一种循环，若是第一种循环里只有一个第二种循环即
for(a[0]=0;a[0]<n;a[0]++)
for(a[1]=a[0];a[1]<n;a[1]++)
那么总共循环次数是n+(n-1)+...+1=n*(n+1)/2=C(n+1,2)
若是第一种循环有两个第二种循环即
for(a[0]=0;a[0]<n;a[0]++)
for(a[1]=a[0];a[1]<n;a[1]++)
for(a[2]=a[1];a[2]<n;a[2]++)
那么总循环次数是(n+1)*n/2+n*(n-1)/2+...+2*1/2=C(n+2,3)
可以发现连续多个的第二种循环是有规律的，若设上一次第一种循环到下一次第一种循环的差值为m，那么这之间的总循环数为C(m+n-1,m)，然后再把所有的都乘起来就是最后的总循环数了（循环是嵌套的，是乘积关系）
这个数还要对364875103取模，这就是另一个难点了，因为364875103它不是素数，不是素数，不是素数！虽说可以拆成两个素数的乘积97*3761599，但这一点也不好发现啊……
这里就要用中国剩余定理了，我们设mod1=97，mod2=3761599，mod=364875103，最后的总循环数ans，设x=ans%mod，x1=ans%mo1,x2=ans%mod2,那么
x%mod1=x1,x%mod2=x2，我们就是要求这个x
根据中国剩余定理公式，那么x=(mod2*(mod1对mod2取模的逆元)*x1+mod1*(mod2对mod1取模的逆元)*x2)%mod，嗯，因为mod1、mod2都是素数，逆元用费马小定理计算就可以了
完整代码：
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; typedef long long LL; const int mod1=97; const int mod2=3761599; const int mod=mod1*mod2; const int maxn=25; LL n,m,k; int cnt; LL a[maxn]; LL fac1[mod1+5]; LL fac2[mod2+5]; LL inv1,inv2; LL quick_mod(LL a,LL b,LL p) { LL ans=1; a%=p;///这里要的，WA了很多次因为这里 while(b) { if(b&1) { ans=ans*a%p; b--; } b>>=1; a=a*a%p; } return ans; } void init() { fac1[0]=fac2[0]=1; for(int i=1;i<mod1;i++) fac1[i]=(fac1[i-1]*i)%mod1; for(int i=1;i<mod2;i++) fac2[i]=(fac2[i-1]*i)%mod2; } LL C(LL n,LL m,int p,LL fac[]) { if(m>n) return 0; LL ans=fac[n]*quick_mod(fac[m]*fac[n-m],p-2,p)%p; return ans; } LL Lucas(LL n, LL m,LL p,LL fac[]) { if(m==0) return 1; return C(n%p,m%p,p,fac)*Lucas(n/p,m/p,p,fac); } int main() { init(); inv1=mod2*quick_mod(mod2,mod1-2,mod1); inv2=mod1*quick_mod(mod1,mod2-2,mod2); int t; scanf("%d",&t); int cnt=0; while(t--) { cnt++; scanf("%lld%lld%lld",&n,&m,&k); for(int i=0;i<k;i++) scanf("%lld",&a[i]); a[k]=m; LL ans=1; for(int i=1;i<=k;i++) { LL x1=Lucas(a[i]-a[i-1]+n-1,a[i]-a[i-1],mod1,fac1); LL x2=Lucas(a[i]-a[i-1]+n-1,a[i]-a[i-1],mod2,fac2); ans=(ans*(x1*inv1%mod+x2*inv2%mod)%mod)%mod; } printf("Case #%d: %lld\n",cnt,ans); } return 0; }
