結果

問題 No.93 ペガサス
コンテスト
ユーザー btk
提出日時 2016-05-04 00:02:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,518 bytes
コンパイル時間 1,813 ms
コンパイル使用メモリ 177,232 KB
実行使用メモリ 153,472 KB
最終ジャッジ日時 2024-10-05 06:09:37
合計ジャッジ時間 4,451 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 2
other AC * 1 WA * 14 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector<LL> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
typedef vector<VVV> VVVV;


const LL MOD=1e9+7;
int main() {
    int N;
    cin >> N;
    VVVV dp(N+1,VVV(N+10,VV(2,V(2,0))));
    dp[1][0][0][0] = 1;
    dp[2][0][0][0] = 2;
    for(int i = 2; i <N; i++){
        dp[i + 1][0][0][0] += dp[i][0][0][0] * (i - 1);
        dp[i + 1][1][0][1] += dp[i][0][0][0] * 2;
        for(int j = 1; j <= N; j++){
            /*from [0][0]*/
            //間とi-2の隣以外に置く
            dp[i + 1][j][0][0] += dp[i][j][0][0] * (i -j - 1);
            //i-2の隣に置く
            dp[i + 1][j + 1][0][1] += dp[i][j][0][0] * 2;
            //間に差し込む
            dp[i + 1][j - 1][0][0] += dp[i][j][0][0] * j;

            /*from [0][1]*/
            //i-1,i-3の間に差し込む
            dp[i + 1][j - 1][0][0] += dp[i][j][0][1];
            //i-2の隣に置く
            dp[i + 1][j + 1][1][1] += dp[i][j][0][1] * 2;
            //間に差し込む
            dp[i + 1][j - 1][1][0] += dp[i][j][0][1] * (j - 1);
            //間とi-2の隣以外に置く
            dp[i + 1][j][1][0] += dp[i][j][0][1] * (i - j - 1);

            /*from [1][0]*/
            //i-2,i-4の間に差し込む
            dp[i + 1][j][0][1] += dp[i][j][1][0];
            //i-2の間じゃないほうに置く
            dp[i + 1][j + 1][0][1] += dp[i][j][1][0];
            //間に差し込む
            dp[i + 1][j - 1][1][0] += dp[i][j][1][0] * (j - 1);
            //間とi-2の隣以外に置く
            dp[i + 1][j][1][0] += dp[i][j][1][0] * (i - j);

            /*from [1][1]*/
            //i-1,i-3の間に差し込む
            dp[i + 1][j - 1][0][0] += dp[i][j][1][1];
            //i-2,i-4の間に差し込む
            dp[i + 1][j][1][1] += dp[i][j][1][1];
            //i-2の間じゃないほうに置く
            dp[i + 1][j + 1][1][1] += dp[i][j][1][1];
            //間に差し込む
            dp[i + 1][j - 1][1][0] += dp[i][j][1][1] * (j - 2);
            //間とi-2の隣以外に置く
            dp[i + 1][j][1][0] += dp[i][j][1][1] * (i - j);
        }
        for(int j = 0; j <= N; j++)
            for(int k = 0; k < 2; k++)
                for(int l = 0; l < 2; l++){
                    dp[i + 1][j][k][l] %=MOD;
                    //printf("dp[%d][%d][%d][%d]=%lld\n",i+1,j,k,l,dp[i+1][j][k][l]);
                }
    }
    cout << dp[N][0][0][0] << endl;
    return 0;
}
0