2012 Multi-University Training Contest 8
題意：
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)
接下來的問題就是如何求出這些東西對364875103的模，由於n和m都非常大，暴力統計必然是不行的。
364875103 = 97 * 3761599 （比賽時候哪有心情拆數玩，這個太不厚道了）
Lucas(n, m, p) = c(n % p,m % p) * Lucas(n / p, m / p, p);
用Lucas定理分別求出兩個質數的余數，然後利用中國剩余定理求出對364875103的余數。
[cpp]
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXK = 20;
const int MOD1 = 97;
const int MOD2 = 3761599;
const int MOD = MOD1 * MOD2;
int n, m, k;
int a[MAXK];
__int64 p1[MOD1], p2[MOD2];
__int64 c1, c2; www.2cto.com
__int64 pow_mod(__int64 x, __int64 y, __int64 mod)
{
__int64 res = 1;
while(y)
{
if(y & 1)
{
res = (res * x) % mod;
}
x = (x * x) % mod;
y >>= 1;
}
return res;
}
__int64 cm(__int64 n, __int64 m, __int64 mod, __int64 p[])
{
if(n < m)
{
return 0;
}
__int64 res = (p[n] * pow_mod(p[m], mod - 2, mod)) % mod;
return (res * pow_mod(p[n - m], mod - 2, mod)) % mod;
}
__int64 lucas(__int64 n, __int64 m, __int64 mod, __int64 p[])
{
__int64 res = 1;
while(n && m && res)
{
res = (res * cm(n % mod, m % mod, mod, p)) % mod;
n /= mod;
m /= mod;
}
return res;
}
void init()
{
p1[0] = p2[0] = 1;
for(int i=1;i<MOD1;++i)
{
p1[i] = (p1[i-1] * i) % MOD1;
}
for(int i=1;i<MOD2;++i)
{
p2[i] = (p2[i-1] * i) % MOD2;
}
c1 = MOD2 * pow_mod(MOD2, MOD1 - 2, MOD1);
c2 = MOD1 * pow_mod(MOD1, MOD2 - 2, MOD2);
}
int main()
{
init();
int caseNumber;
scanf("%d", &caseNumber);
for(int cas=1;cas<=caseNumber;++cas)
{
scanf("%d%d%d", &n, &m, &k);
for(int i=0;i<k;++i)
{
scanf("%d", &a[i]);
}
a[k] = m;
__int64 ans = 1;
for(int i=0;i<k;++i)
{
__int64 m1 = lucas(a[i+1] - a[i] + n - 1, a[i+1] - a[i], MOD1, p1);
__int64 m2 = lucas(a[i+1] - a[i] + n - 1, a[i+1] - a[i], MOD2, p2);
__int64 mm = (m1 * c1 + m2 * c2) % MOD;
ans = (ans * mm) % MOD;
}
printf("Case #%d: %I64d\n", cas, ans);
}
return 0;
}
