WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #178 Div2 C "Shaass and Lights"

問題

http://codeforces.com/contest/294/problem/C

n個のライトが一列に並んでいる。
ライトには左から右に向かって1~nの番号が振られている。
m個のライトは既にスイッチがオンになっている。
既にオンになっているライトの隣のライトを順にオンにしていって、
全てのライトをオンにしたい。

ライトのつけ方は何通りあるかを出力せよ。

制約

1 <= n <= 1000
1 <= m <= n


Editorialsの訳

(Editorialsはコチラ)



3つ目のサンプルを使って説明します。

3つ目のサンプルは次のようになっています。

# - スイッチオンのランプ
. - スイッチオフのランプ

...#...#...

ここで、ランプを次のように3つのグループにわけることが出来ます。

グループA...番号1~3のランプ
グループB...番号5~7のランプ
グループC...番号9~11のランプ

各グループに対し、3回オンの操作を、合計で9回加える必要があります。
この9回の操作のやり方は、
9個の文字 AAABBBCCC を使って何種類の文字列が作れるか
と一緒で、9! / (3!*3!*3!) =1680通りとなります。

グループA, Cでは、そのグループ内に限るとランプのつけ方は1通りだけですが、
グループBは左右どちらにするかを2回まで選択する事ができ、
それは2^(3-1)=4通りになります。

結果として、答えは1680*1*4*1 = 6720通りになります。


(さらに一般的な解決について、概要が記述してあります)


ソースコード

4/11追記
ソースコードが間違いだらけだったので修正

const int MOD = 1000000007;
long long F[1010]; // F[n] n! % MODはいくつか?

long long mod_pow( long long a, int b ){
    if( b == 1 ) return a;
    if( b % 2 ){
        long long r = mod_pow( a, b-1 );
        return r * a % MOD;
    }else{
        long long r = mod_pow( a, b/2 );
        return r * r % MOD;
    }
}

long long mod_inv( long long a ){
    return mod_pow( a, MOD - 2 );
}


int main() {
    // 階乗を初期化
    F[1] = 1;
    for( int i = 2; i <= 1000; i++ ){
        F[i] = F[i-1] * i % MOD;
    }

    // 入力
    int N, M;
    cin >> N >> M;
    vector<int> onLamps;
    for( int i = 0; i < M; i++ ){
        int t;
        cin >> t;
        onLamps.push_back(t);
    }
    sort( onLamps.begin(), onLamps.end() );

    // グループ情報を初期化
    int groupNum[1000];   // 各グループのランプ数
    bool canChoice[1000]; // グループはランプを選択できるか
    int n = 0;            // グループの数
    int p = 0;
    for( int i = 0; i < M; i++ ){
        int o = onLamps[i];
        if( o - p >= 2 ){
            groupNum[n] =  o - p - 1;
            canChoice[n] = p != 0;
            n++;
        }
        p = o;
    }
    if( p != N ){
        groupNum[n] = N - p;
        canChoice[n] = false;
        n++;
    }

    // AAABBBCCCのアルファベットの選び方を計算
    long long res;
    long long sum = 0;
    for( int i = 0; i < n; i++ ){
        sum += groupNum[i];
    }
    res = F[sum];
    for( int i = 0; i < n; i++ ){
        res = res * mod_inv( F[groupNum[i]] ) % MOD;
    }

    // ランプを選択できるグループのパターンをかけていく
    for( int i = 0; i < n; i++ ){
        if( canChoice[i] ){
            for( int j = 0; j < groupNum[i] - 1; j++ ){
                res = res * 2 % MOD;
            }
        }
    }

    printf( "%d\n", (int)res );
}