結果
| 問題 | No.93 ペガサス |
| ユーザー |
 codershifth
|
| 提出日時 | 2015-08-30 14:54:43 |
| 言語 | C++11 (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 424 ms / 5,000 ms |
| コード長 | 8,761 bytes |
| コンパイル時間 | 1,704 ms |
| コンパイル使用メモリ | 177,636 KB |
| 実行使用メモリ | 152,192 KB |
| 最終ジャッジ日時 | 2024-07-18 15:38:36 |
| 合計ジャッジ時間 | 4,289 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 16 |
ソースコード
#include <bits/stdc++.h>typedef long long ll;typedef unsigned long long ull;#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)#define REP(i,n) FOR(i,0,n)#define RANGE(vec) (vec).begin(),(vec).end()class ModInt {long long value_;public:static long long Mod;static void set_mod(long long mod) { Mod= mod; }static long long get_mod(void) { return Mod; }ModInt() : value_(0) {}ModInt(long long val) {if (val >= Mod)value_ = val % Mod;else if (val >= 0)value_ = val;else // val < 0value_ = (((-val)/Mod+1)*Mod+val) % Mod;assert(value_ < Mod);}ModInt(const ModInt &other) { value_ = other.value_; }~ModInt() {}#define OPT(OP) \ModInt operator OP (const ModInt &other) const { \return ModInt(value_ OP other.value_); \} \template<class T> \ModInt &operator OP##=(const T &other) { \return (*this = (*this OP ModInt(other))); \}OPT(+) OPT(-) OPT(*)#undef OPTbool operator==(const ModInt &other) const {return (value_ == other.value_);}bool operator!=(const ModInt &other) const {return !(*this == other);}ModInt &operator=(const ModInt &other) {value_ = other.value_;return *this;}// cast overloadoperator int() const { return value_; }operator long long() const { return value_; }static long long pow(ModInt a, int k) {ModInt b = 1;while (k > 0){if (k & 1)b = (b*a);a = (a*a);k >>= 1;}return b;}// call when Mod is primeModInt inv() { return ModInt::pow(*this, Mod-2); }long long value() const { return value_; }friend std::ostream& operator<<(std::ostream& os, const ModInt& m) {os<<m.value_;return os;}};// 互換性サポートは int, long long のみ#define OPT(OP,T) \ModInt operator OP (const ModInt &a, T b) { return a OP ModInt(b); } \ModInt operator OP (T a, const ModInt &b) { return ModInt(a) OP b; }OPT(*,int) OPT(+,int) OPT(-,int) OPT(*,long long) OPT(+,long long) OPT(-,long long)#undef OPTlong long ModInt::Mod = (long long)(1E+9)+7;namespace multi_dimentional_vector {template<typename T> void resize(std::vector<T> &vec, size_t sz) { vec.resize(sz); }template<typename T, typename S>void resize(std::vector<T> &vec, size_t sz, const S &init) { vec.resize(sz, static_cast<T>(init)); }template<typename T, typename... S>void resize(std::vector<T> &vec, size_t sz, const S&... follows) {vec.resize(sz);for (auto &v : vec) resize(v, follows...);}template <typename T>struct has_iterator {template <typename U> static char test(typename U::iterator* x);template <typename U> static long test(U* x);static const bool value = sizeof(test<T>(0)) == 1;};template <typename T, typename S>typename std::enable_if<!has_iterator<T>::value, void>::typefill(std::vector<T>& vec, const S &value) { std::fill(vec.begin(), vec.end(), static_cast<T>(value)); }template <typename T, typename S>typename std::enable_if<has_iterator<T>::value, void>::typefill(std::vector<T>& vec, const S &value) { for (auto &v : vec) fill(v, value); }template<typename T, typename... S>std::vector<T> define(size_t sz, const S&... follows) {std::vector<T> vec;return std::move(vec);}};namespace mdv = multi_dimentional_vector;using namespace std;class Pegasus {public:void solve(void) {//// 縦横にはおけないのと N*N 盤面であることから//// +-+-+-+-+// | |o| | |// +-+-+-+-+// |o| | | |// +-+-+-+-+// | | | |o|// +-+-+-+-+// | | |o| |// +-------+// [2,1,4,3]//// のように 1...n の順列のうち隣り合う数字との差の絶対値が// 2 にならないようなものの総数を求めれば良い。// 以下隣接する数字の差の絶対値が 2 になる条件を cond と表す。//// 挿入 DP でやる。// 1,2,3,..,N の順に挿入して順列をつくると考える。//// 1,2,..,n の順列にたいして n+1 を挿入する時// * n-1 の隣に挿入してしまうと cond をみたすものが 1 つできる。// (1,2,... の順で挿入するので片側だけ考えれば良い。)// * ただし n-3,n-1 が隣接するとき間に cond を満たすものの総数は変わらない ((-1) + (+1) = 0)// * それ以外の cond をみたす隣接2数の間に挿入すれば cond を満たすものの総数を減らせる。//// n+1 の挿入時に n-3,n-1 が隣接しているかの情報が必要になる。// つまり次の更新時のために n,n-2 が隣り合うかの情報更新が必要。//// 以上を踏まえると dp は// dp[n][k][a][b] := n 番目まで挿入したときに、 cond をみたす場所が k 個あるときの挿入結果の総数// ただし a==1 のとき (n-3,n-1) が隣接// ただし b==1 のとき (n-2,n) が隣接//// となる。int N;cin>>N;vector<vector<vector<vector<ModInt>>>> dp;mdv::resize(dp, N+1, N+1, 2, 2, 0);dp[1][0][0][0] = 1;// O(N^2)FOR(n,1,N)REP(k,N)REP(a,2)REP(b,2){if (n == 1){// 1 枚しかないときはどこに挿入しても cond を満たさないdp[n+1][k][0][0] += (n+1)*dp[n][k][a][b];continue;}// (n-2,n) -> (n-3,n-1)// (n-1,n+1) -> (n-2,n)if (a==1) // (n-3,n-1) が隣接{// n-1 のとなりに挿入するケース// (n-3,n-1) の間に挿入dp[n+1][k][b][1] += dp[n][k][a][b];// (n-3,n-1)じゃないほうの n-1 のとなりdp[n+1][k+1][b][1] += dp[n][k][a][b];// cond 総数を減らすような挿入。 k-1 なのは上の (n-3,n-1) のケースを省くからif (k >= 1){if (b==1) // (n-2,n) が隣接するケース{ // (n-2,n) の間に挿入dp[n+1][k-1][0][0] += dp[n][k][a][b];// それ以外dp[n+1][k-1][1][0] += ((k-1)-1)*dp[n][k][a][b];}elsedp[n+1][k-1][b][0] += (k-1)*dp[n][k][a][b];}// のこり (n+1) なのは 1,...,n の両側を含めるからdp[n+1][k][b][0] += ((n+1)-k-1)*dp[n][k][a][b];}else{// n-1 のとなりに挿入(左右二通り)dp[n+1][k+1][b][1] += 2*dp[n][k][a][b];// k を減らすような挿入if (k >= 1){if (b==1){ // (n-2,n) の間に挿入dp[n+1][k-1][0][0] += dp[n][k][a][b];// それ以外dp[n+1][k-1][1][0] += (k-1)*dp[n][k][a][b];}elsedp[n+1][k-1][b][0] += k*dp[n][k][a][b];}// のこりdp[n+1][k][b][0] += ((n+1)-k-2)*dp[n][k][a][b];}}cout<<dp[N][0][0][0]<<endl;}};#if 1int main(int argc, char *argv[]){ios::sync_with_stdio(false);auto obj = new Pegasus();obj->solve();delete obj;return 0;}#endif