C++の練習を兼ねて, AtCoder Regular Contest 023 の 問題C (C – タコヤ木) を解いてみた.
■感想.
1. 組み合わせの復習が出来たので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 023 解説をご覧下さい.
■C++版プログラム(問題C／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) const LL MOD = 1e9 + 7; const int LIMIT = 2020; LL INV[LIMIT]; // Fermat's little theorem から, 大きな冪乗の計算を行う. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL mPow(LL a, LL b){ LL t = 1; while(b){ if(b & 1) t = (t * a) % MOD; a = a * a % MOD; b >>= 1; } return t % MOD; } // 組み合わせ(nCk)計算用(mod版). // @param n: 対象となる要素の個数. // @param k: 選択する要素の個数. // @return: 組み合わせ(nCk)の計算結果(mod版). LL combination(LL n, LL k){ LL ret = 1, i = 0; while(i < k){ ret *= (n - i); ret %= MOD; ret *= INV[i + 1]; ret %= MOD; i++; } return ret; } int main(){ // 1. 入力情報. int N; scanf("%d", &N); repx(i, 1, LIMIT) INV[i] = mPow((LL)i, MOD - 2); // 2. 記録のパターンをカウント. LL bef = 0, cur, one = 0, ans = 1; rep(i, N){ scanf("%lld", &cur); // -1 の 個数 を カウント. if(cur == -1) one++; // -1 でない. if(cur != -1){ if(bef != 0){ // 右方向: one個, 上方向: (cur - bef)個 から 進路選択するイメージ. ans *= combination(cur - bef + one, one); ans %= MOD; } // 初期化. one = 0; bef = cur; } } // 3. 出力. printf("%lld\n", ans); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
[入力例] 3 1 -1 3 [出力例] 3 ※AtCoderのテストケースより [入力例] 6 2 -1 -1 9 -1 9 [出力例] 36 ※AtCoderのテストケースより [入力例] 5 1 -1 -1 -1 1000000000 [出力例] 999999972 ※AtCoderのテストケースより [入力例] 15 1 -1 -1 -1 -1 7 -1 -1 10 -1 -1 13 -1 15 16 [出力例] 63000 [入力例] 28 1 -1 2 -1 -1 3 -1 -1 -1 4 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 7 [出力例] 5040 [入力例] 27 1 -1 10 -1 -1 2020 -1 -1 -1 -1 303030 -1 -1 -1 -1 -1 -1 40404040 -1 -1 -1 -1 -1 -1 -1 -1 50505050 [出力例] 297905265 |
■参照サイト
AtCoder Regular Contest 023