問題
http://yukicoder.me/problems/no/389
1行M列のマスがある。
これを(空白)(H1連続で塗る)(空白)(H2連続で塗る)...(空白)(Hk連続で塗る)(空白)と塗る。
要はイラストロジックみたいに塗る。
この塗り方を数えて、10^9+7で割った余りを答える。
k==1でHi==0の時に限り、1通りとする。
入力された塗り方が存在しないならNAを出力。
1 <= M <= 10^6
考察
1. 組合せを数える系はいろんな解法があるが、まずは数学的に求められないか(俺は)考える
2. もっともっとよく考えるとできると気づく
サンプル1 M=10, k=2, H={7,1} で考える。 1. まず連続で塗る所の間は最低1つ空白が必要なので、必要最小限の構成を作る ■■■■■■■□■ 2. 空白が余るので、この空白の割り当て方を考える。今回の例であれば、1つの空白が余る 空白が入れられる部分が最左と最右と各塗られている所の間の3つある。 異なる3つのスペースに重複を許して1つの空白を分け与える組合せ -> 重複組合せ 1H3
3. 一般化する
Mマスでヒントがk個、ヒントで塗られるマスの総和をsumとする。 1. 最小限の構成に必要なマスの数は、sum + k - 1マス 与えられているマスがこのマス未満であれば、塗り方が存在しないためNA 2. 余っている空白はM-(sum + k - 1)マスで、空白を入れられるスペースはk+1個 -> 重複組合せ (M-(sum+k-1))H(k+1)
4. 重複組合せは組合せで計算可能 aHb = (a+b-1)C(b-1)
実装
http://yukicoder.me/submissions/102381
typedef long long ll; ll MOD = 1000000007; const int NUM_FAC = 2000001; ll modfact(ll x) { static ll _fact[NUM_FAC + 1]; if (_fact[0] == 0) { _fact[0] = 1; for (int i = 1; i <= NUM_FAC; ++i) _fact[i] = _fact[i - 1] * i%MOD; } return _fact[x]; } ll modpow(ll a, ll n) { ll r = 1; while (n) r = r*((n % 2) ? a : 1) % MOD, a = a*a%MOD, n >>= 1; return r; } ll moddiv(ll a, ll b) { ll ap_2 = modpow(b, MOD - 2); return (a * ap_2) % MOD; } ll aCb(ll a, ll b) { return moddiv(modfact(a), (modfact(a-b) * modfact(b))% MOD); } ll nHk(ll n, ll k) { return aCb(n + k - 1, k - 1); } //----------------------------------------------------------------- int M; vector<int> H; //----------------------------------------------------------------- int main() { cin >> M; int x; while (cin >> x) H.push_back(x); if (H.size() == 1 && H[0] == 0) { printf("1\n"); return 0; } int sum = 0; rep(i, 0, H.size()) sum += H[i]; int a = M - sum - (H.size() - 1); int b = H.size() + 1; if (a < 0) { cout << "NA" << endl; return 0; } ll ans = nHk(a, b); cout << ans << endl; }