結果

問題 No.336 門松列列
ユーザー kimiyukikimiyuki
提出日時 2016-06-10 13:31:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 106 ms / 2,000 ms
コード長 2,086 bytes
コンパイル時間 974 ms
コンパイル使用メモリ 76,764 KB
実行使用メモリ 4,372 KB
最終ジャッジ日時 2023-09-02 18:45:14
合計ジャッジ時間 2,375 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 85 ms
4,372 KB
testcase_01 AC 1 ms
4,368 KB
testcase_02 AC 1 ms
4,368 KB
testcase_03 AC 2 ms
4,372 KB
testcase_04 AC 104 ms
4,368 KB
testcase_05 AC 2 ms
4,368 KB
testcase_06 AC 13 ms
4,368 KB
testcase_07 AC 38 ms
4,368 KB
testcase_08 AC 68 ms
4,372 KB
testcase_09 AC 102 ms
4,372 KB
testcase_10 AC 105 ms
4,368 KB
testcase_11 AC 106 ms
4,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
typedef long long ll;
using namespace std;
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors<T, Y, Zs...>(a, y, zs...); return vector<decltype(cont)>(x, cont); }

ll powi(ll x, ll y, ll p) {
    assert (y >= 0);
    x = (x % p + p) % p;
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
ll inv(ll x, ll p) {
    assert ((x % p + p) % p != 0);
    return powi(x, p-2, p);
}
const int mod = 1000000007;
ll choose(ll n, ll r) { // O(n), O(1)
    static vector<ll> fact(1,1);
    static vector<ll> ifact(1,1);
    if (fact.size() <= n) {
        int l = fact.size();
        fact.resize( n + 1);
        ifact.resize(n + 1);
        repeat_from (i,l,n+1) {
            fact[i]  = fact[i-1] * i % mod;
            ifact[i] = inv(fact[i], mod);
        }
    }
    r = min(r, n - r);
    return fact[n] * ifact[n-r] % mod * ifact[r] % mod;
}


const int U = 0;
const int D = 1;
int main() {
    int n; cin >> n;
    vector<vector<vector<ll> > > dp = vectors<ll>(0, n+1, 2, 2);
    if (n == 1 or n == 2) {
        // nop
    } else {
        dp[0][U][D] = 1;
        dp[0][D][U] = 1;
        dp[1][U][U] = 1;
        dp[1][D][D] = 1;
        repeat_from (len,2,n+1) {
            repeat (l,len) {
                int r = len-1 - l;
                assert (l + 1 + r == len and 0 <= l and l < len and 0 <= r and r < len);
                repeat (x,2) repeat (y,2) {
                    dp[len][x][y] += dp[l][x][D] * dp[r][D][y] % mod * choose(l+r, l) % mod;
                }
            }
            repeat (x,2) repeat (y,2) dp[len][x][y] %= mod;
        }
    }
    ll ans = 0;
    repeat (x,2) repeat (y,2) ans += dp[n][x][y];
    cout << (ans % mod) << endl;
    return 0;
}
0