hdu_4373 Mysterious For

题目:

  MatRush is an ACMer from ZJUT, and he always love to create some special programs. Here we will talk about one of his recent inventions.
  This special program was called "Mysterious For", it was written in C++ language, and contain several simple for-loop instructions as many other programs. As an ACMer, you will often write some for-loop instructions like which is listed below when you are taking an ACM contest.

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        for (int k = j; k < n; k++) {
            blahblahblah();
        }       
    }      
}

  Now, MatRush has designed m for-loop instructions in the "Mysterious For" program, and each for-loop variable was stored in an array a[], whose length is m.
  The variable i represents a for-loop instructions is the i-th instruction of the "Mysterious For" program.There only two type of for-loop instructions will occur in MatRush's "Mysterious For" program:
  1-type: if a for-loop belongs to 1-type, it will be an instruction like this:

for (int a[i] = 0; a[i] < n; a[i]++) {
    ...
}

  2-type: if a for-loop belongs to 2-type, it will be an instruction like this:

for (int a[i] = a[i - 1]; a[i] < n; a[i]++) {
    ...
}

  In addition, after the deepest for-loop instruction there will be a function called HopeYouCanACIt(), here is what's inside:

void HopeYouCanACIt() {
    puts("Bazinga!");
}

  So, the "Mysterious For" program, obviously, will only print some line of the saying: "Bazinga!", as it designed for.
  For example, we can assume that n equals to 3, and if the program has three 1-type for-loop instructions, then it will run 3 3=27 times of the function HopeYouCanACIt(), so you will get 27 "Bazinga!" in total. But if the program has one 1-type for-loop instruction followed by two 2-type for-loop instructions, then it will run 3+2+1+2+1+1=10 times of that function, so there will be 10 "Bazinga!" on the screen.
  Now MatRush has the loop length n and m loop instructions with certain type, then he want to know how many "Bazinga!" will appear on the screen, can you help him? The answer is too big sometimes, so you just only to tell him the answer mod his QQ number:364875103.
  All for-loop instructions are surely nested. Besides, MatRush guaranteed that the first one belongs to the 1-type. That is to say, you can make sure that this program is always valid and finite. There are at most 15 1-type for-loop instructions in each program.

思路:

  因为每一个类型1的循环都是不会受上一个循环影响的,所以可以按照类型1的循环把代码分开考虑。
  观察可得,每一个类型2的循环的循环变量一定小于或等于上一个循环的循环变量。所以假设一个类型1的循环后面有连续的个类型2的循环,那么输出这些循环变量就会出现一个满足,长度为,那么求出数列种数就是这一段循环的次数了。
  这个数列的出现次数可以转化成重复组合的问题,由公式,转化成组合数,用lucas定理求解即可,lucas定理要求模数为质数,所以要把拆成,用中国剩余定理求出最终解即可。

代码:

#include <bits/stdc++.h>
#define DEBUG(x) cerr<<"DEBUG:"<<#x<<'='<<(x)<<endl
#define ll long long
using namespace std;
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b){d=a;x=1;y=0;return;}
    exgcd(b,a%b,d,y,x);y-=a/b*x;
}
ll inv(ll a,ll m){
    ll d,x,y;
    exgcd(a,m,d,x,y);
    return (x%m+m)%m;
}
const int mod[]={97,3761599};
ll fac[2][3761599+10],invfac[2][3761599+10];
void init(){
    fac[0][0]=fac[1][0]=invfac[0][0]=invfac[1][0]=1;
    for(int i=1;i<mod[0];i++)
        fac[0][i]=fac[0][i-1]*i%mod[0];
    for(int i=1;i<mod[1];i++)
        fac[1][i]=fac[1][i-1]*i%mod[1];
    invfac[0][mod[0]-1]=inv(fac[0][mod[0]-1],mod[0]);
    invfac[1][mod[1]-1]=inv(fac[1][mod[1]-1],mod[1]);
    for(int i=mod[0]-2;~i;i--)
        invfac[0][i]=invfac[0][i+1]*(i+1)%mod[0];
    for(int i=mod[1]-2;~i;i--)
        invfac[1][i]=invfac[1][i+1]*(i+1)%mod[1];
}
ll C(ll n,ll m,int k){
    return fac[k][n]*invfac[k][m]%mod[k]*invfac[k][n-m]%mod[k];
}
ll lucas(ll n,ll m,int k){
    if(!m)return 1;
    return lucas(n/mod[k],m/mod[k],k)*C(n%mod[k],m%mod[k],k)%mod[k];
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
#define lcm(a,b) ((a)/gcd(a,b)*(b))
ll calc(ll a,ll b,ll c){
    ll d,x,y;
    exgcd(a,b,d,x,y);
    if(c%d)return -1;
    b/=d;c/=d;
    return (x*c%b+b)%b;
}
struct CRT{
    ll A,M;
    CRT(){A=0;M=1;}
    bool insert(ll a,ll m){
        ll k=calc(M,m,a-A);
        if(!~k)return false;
        A+=M*k;
        M=lcm(M,m);
        return true;
    }
};
bool type[100005];
#define clr(a) memset(a,0,sizeof(a))
#define MOD 364875103
int main(){
    int T,n,m;
    init();
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        int k;
        clr(type);
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1,x;i<=k;i++){
            scanf("%d",&x);
            type[x]=true;
        }
        ll ans=1;
        int p=0,cnt;
        type[m]=true;
        while(p<m){
            CRT crt;
            p++;cnt=1;
            while(!type[p])
                cnt++,p++;
            crt.insert(lucas(n+cnt-1,cnt,0),mod[0]);
            crt.insert(lucas(n+cnt-1,cnt,1),mod[1]);
            ans=ans*crt.A%MOD;
        }
        printf("Case #%d: %lld\n",t,ans);
    }
    return 0;
}