HDU4373 Mysterious For

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.zzzyk.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;
}

补充：软件开发 , C++ ,