题意：
m个for循环嵌套，有两种形式，第一类从1开始到n，第二类从上一层循环当前数开始到n，第一层一定是第一种类型，问总的循环的次数对364875103取余的结果。
首先可以看出，每一个第一类循环都是一个新的开始，与前面的状态无关，所以可以把m个嵌套分为几个不同的部分，每一个部分由第一类循环开始，最终结果相乘就可以。
剩下的就是第二类循环的问题，假设一个m层循环，最大到n，
只有第一层：循环n次。
只有前两层：循环n + (n - 1) + ... + 1 = (n + 1) * n / 2 = C(n + 1, 1)
只有前三层：
(n + 1) * n / 2 + n * (n - 1) / 2 + ... + 1
= (1 + 2 + ... + n) / 2 + (1 + 4 + ... + n^2) / 2
= (n + 1) * n / 2 / 2 + n * (n + 1) * (2n + 1) / 6 / 2
= (n + 2) * (n + 1) * n / 6 = C(n + 2, 2)
找规律得第m层：C(n + m - 1, m)
- #include <iostream>
- #include <string.h>
- #include <stdio.h>
- using namespace std;
- typedef long long LL;
- const int N=25;
- const int MOD1=97;
- const int MOD2=3761599;
- const int MOD=MOD1*MOD2;
- int m,n,k;
- int a[N];
- LL fac1[MOD1+10];
- LL fac2[MOD2+10];
- LL inv1,inv2;
- LL quick_mod(LL a,LL b,LL m)
- {
- LL ans=1;
- a%=m;
- while(b)
- {
- if(b&1)
- {
- ans=ans*a%m;
- b--;
- }
- b>>=1;
- a=a*a%m;
- }
- return ans;
- }
- LL C(LL n,LL m,LL p,LL fac[])
- {
- if(n<m) return 0;
- return fac[n]*quick_mod(fac[m]*fac[n-m],p-2,p)%p;
- }
- 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);
- }
- 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;
- inv1=MOD2*quick_mod(MOD2,MOD1-2,MOD1);
- inv2=MOD1*quick_mod(MOD1,MOD2-2,MOD2);
- }
- int main()
- {
- Init();
- int t,tt=1;
- scanf("%d",&t);
- while(t--)
- {
- scanf("%d%d%d",&n,&m,&k);
- for(int i=0;i<k;i++)
- scanf("%d",&a[i]);
- a[k]=m;
- LL ans=1;
- for(int i=0;i<k;i++)
- {
- LL m1=Lucas(a[i+1]-a[i]+n-1,a[i+1]-a[i],MOD1,fac1);
- LL m2=Lucas(a[i+1]-a[i]+n-1,a[i+1]-a[i],MOD2,fac2);
- LL mm=(m1*inv1+m2*inv2)%MOD;
- ans=(ans*mm)%MOD;
- }
- printf("Case #%d: ",tt++);
- cout<<ans<<endl;
- }
- return 0;
- }