結果
| 問題 | No.93 ペガサス |
| コンテスト | |
| ユーザー |
 codershifth
|
| 提出日時 | 2015-08-30 14:54:43 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0 + boost 1.89.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 < 0
value_ = (((-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 OPT
bool 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 overload
operator 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 prime
ModInt 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 OPT
long 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>::type
fill(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>::type
fill(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];
}
else
dp[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];
}
else
dp[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 1
int main(int argc, char *argv[])
{
ios::sync_with_stdio(false);
auto obj = new Pegasus();
obj->solve();
delete obj;
return 0;
}
#endif