Codeforces Round #178 (Div. 2) C. Shaass and Lights

 

排列組合問題 參考官方題解

 

/*
 * GCA : "Computer is artificial subject absolutely,Math is God"
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
#include <ctime>
using namespace std;
#ifdef DEBUG
#define VAR(a,b) __typeof(b) a=(b)
#define debug(...) printf("DEBUG: "),printf(__VA_ARGS__)
#else
#define VAR(a,b) __typeof(b) a=(b)
#define debug(...)
#endif
typedef unsigned int uint;
typedef long long int Int;
typedef unsigned long long int UInt;
#define Set(a,s) memset(a,s,sizeof(a))
#define Pln() printf("\n")
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define M 1105
#define PB push_back
#define oo INT_MAX
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define eps 1e-9
#define X first
#define Y second
inline bool xdy(double x,double y){return x>y+eps;}
inline bool xddy(double x,double y){return x>y-eps;}
inline bool xcy(double x,double y){return x<y-eps;}
inline bool xcdy(double x,double y){return x<y+eps;}
const Int mod=1000000007;
int n,m;
Int c[M][M];
void init(){

    c[0][0]=1;
    for(int i=1;i<M;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
}
Int d[M];
Int powmod(Int b,Int n){
    if(n<0)return 1;
    Int ans=1,base=b;
    while(n){
        if(n&1)ans=(ans*base)%mod;
        base=(base*base)%mod;
        n>>=1;
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(0);
    init();
    while(~scanf("%d%d",&n,&m)){
        Int all;
        Set(d,0);
        d[0]=0;
        for(int i=1;i<=m;i++){
            scanf("%I64d",&d[i]);
        }
        sort(d,d+m+1);
        all=n-m;
        Int ans=1;
//        for(int i=1;i<=m;i++)debug("I"
        for(int i=1;i<=m;i++){
            ans=(ans*c[all][d[i]-d[i-1]-1])%mod;
//            debug("%I64d %I64d %I64d\n",all,d[i]-d[i-1]-1,c[all][d[i]-d[i-1]-1]);
            if(i!=1){
//                debug("ok");
                ans=(ans*powmod(2,d[i]-d[i-1]-2))%mod;
            }
            all-=d[i]-d[i-1]-1;
        }
        printf("%I64d\n",ans);

    }

















}