結果

問題 No.336 門松列列
ユーザー asi1024asi1024
提出日時 2016-02-20 05:28:34
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,627 bytes
コンパイル時間 1,301 ms
コンパイル使用メモリ 163,836 KB
実行使用メモリ 11,656 KB
最終ジャッジ日時 2024-09-22 12:24:48
合計ジャッジ時間 5,316 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 245 ms
11,392 KB
testcase_02 AC 245 ms
11,396 KB
testcase_03 AC 245 ms
11,268 KB
testcase_04 WA -
testcase_05 AC 245 ms
11,396 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
権限があれば一括ダウンロードができます

ソースコード

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;

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; }
Mod operator^(Mod a, int n) {
  if (n == 0) return Mod(1);
  Mod res = (a * a) ^ (n / 2);
  if (n % 2) res = res * a;
  return res;
}

int inv(int a, int p) {
  return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
Mod operator/(Mod a, Mod b) { return a * Mod(inv(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