結果

問題 No.336 門松列列
ユーザー asi1024asi1024
提出日時 2016-02-20 05:39:22
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 381 ms / 2,000 ms
コード長 1,517 bytes
コンパイル時間 1,243 ms
コンパイル使用メモリ 162,432 KB
実行使用メモリ 11,524 KB
最終ジャッジ日時 2024-06-12 01:12:32
合計ジャッジ時間 6,533 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 369 ms
11,272 KB
testcase_01 AC 358 ms
11,524 KB
testcase_02 AC 356 ms
11,520 KB
testcase_03 AC 367 ms
11,392 KB
testcase_04 AC 381 ms
11,520 KB
testcase_05 AC 361 ms
11,520 KB
testcase_06 AC 367 ms
11,520 KB
testcase_07 AC 370 ms
11,520 KB
testcase_08 AC 361 ms
11,392 KB
testcase_09 AC 372 ms
11,392 KB
testcase_10 AC 373 ms
11,392 KB
testcase_11 AC 366 ms
11,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef long long ll;

const int mod = 1000000007;

struct Mod {
  int n;
  Mod () : n(0) {;}
  Mod (int n) : n(n) {
    if (n >= mod) n %= mod;
    else if (n < 0) n = (n % mod + mod) % mod;
  }
  operator int() { return n; }
};

bool operator==(Mod a, Mod b) { return a.n == b.n; }
Mod operator+=(Mod &a, Mod b) { a.n += b.n; if (a.n >= mod) a.n -= mod; return a; }
Mod operator-=(Mod &a, Mod b) { a.n -= b.n; if (a.n < 0) a.n += mod; return a; }
Mod operator*=(Mod &a, Mod b) { a.n = ((long long)a.n * b.n) % mod; return a; }
Mod operator+(Mod a, Mod b) { return a += b; }
Mod operator-(Mod a, Mod b) { return a -= b; }
Mod operator*(Mod a, Mod b) { return a *= b; }
ll inv(ll a, ll p) {
  return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
Mod operator/(Mod a, Mod b) { return a * Mod(inv((int)b, mod)); }

#define MAX_N 1024000

Mod fact[MAX_N], factinv[MAX_N];
void init() {
  fact[0] = Mod(1); factinv[0] = 1;
  REP(i,MAX_N-1) {
    fact[i+1] = fact[i] * Mod(i+1);
    factinv[i+1] = factinv[i] / Mod(i+1);
  }
}
Mod comb(int a, int b) {
  return fact[a] * factinv[b] * factinv[a-b];
}

int main() {
  init();
  int N; cin >> N;
  vector<Mod> dp(N+1, 1);
  for (int i = 2; i <= N; ++i) {
    Mod sum = 0;
    REP(j,i) sum += dp[j] * dp[i-j-1] * comb(i-1, j);
    dp[i] = sum / Mod(2);
  }
  if (N <= 2) cout << 0 << endl;
  else cout << dp[N] * Mod(2) << endl;
  return 0;
}
0