結果

問題 No.93 ペガサス
コンテスト
ユーザー btk
提出日時 2016-05-04 00:21:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 580 ms / 5,000 ms
コード長 2,959 bytes
コンパイル時間 2,195 ms
コンパイル使用メモリ 177,300 KB
実行使用メモリ 303,872 KB
最終ジャッジ日時 2024-10-11 00:24:42
合計ジャッジ時間 5,727 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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+2,VVV(N+10,VV(2,V(2,0))));
    VVVV cnt(N+2,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][0][0] += dp[i][j][1][0] * (j - 1);
            //間とi-2の隣以外に置く
            dp[i + 1][j][0][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);
        }
        //vector<int> p(i+1);iota(p.begin(),p.end(),1);do{int a=0,b=0,c=0;for(int j = 0; j < i; j++){if(p[j]==i+1&&p[j+1]==i-1)a++;if(p[j]==i-1&&p[j+1]==i+1)a++;if(p[j]==i-2&&p[j+1]==i)b++; if(p[j]==i&&p[j+1]==i-2)b++; if(abs(p[j]-p[j+1])==2)c++;}cnt[i+1][c][b][a]++;}while(next_permutation(p.begin(),p.end()));
        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 ",i+1,j,k,l,dp[i+1][j][k][l]);
                    //printf("cnt[%d][%d][%d][%d]=%lld\n",i+1,j,k,l,cnt[i+1][j][k][l]);
                }
    }
    cout << dp[N][0][0][0] << endl;
    return 0;
}
0