結果

問題 No.93 ペガサス
ユーザー vjudge1
提出日時 2025-09-08 18:16:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 37 ms / 5,000 ms
コード長 2,965 bytes
コンパイル時間 1,624 ms
コンパイル使用メモリ 162,568 KB
実行使用メモリ 22,912 KB
最終ジャッジ日時 2025-09-08 18:16:30
合計ジャッジ時間 2,845 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
 
using namespace std;

#define int long long
#define fir first
#define sec second
#define mkp make_pair 
#define pb push_back
#define lep( i, l, r ) for ( int i = ( l ); i <= ( r ); ++ i )
#define rep( i, r, l ) for ( int i = ( r ); i >= ( l ); -- i )
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair < int, int > pii;
 
namespace IO{
	const int SIZE=1<<21;
  static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
  int qr;
  char qu[55],c;
  bool f;
	#define getchar() (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf)+fread(IO::ibuf,1,IO::SIZE,stdin),(IO::iS==IO::iT?EOF:*IO::iS++)):*IO::iS++)
	#define putchar(x) *IO::oS++=x,IO::oS==IO::oT?flush():0
	#define flush() fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout),IO::oS=IO::obuf
	#define puts(x) IO::Puts(x)
	template<typename T>
    inline void read(T&x){
    	for(f=1,c=getchar();c<48||c>57;c=getchar())f^=c=='-';
    	for(x=0;c<=57&&c>=48;c=getchar()) x=(x<<1)+(x<<3)+(c&15); 
    	x=f?x:-x;
    }
    template<typename T>
    inline void write(T x){
      if(!x) putchar(48); if(x<0) putchar('-'),x=-x;
      while(x) qu[++qr]=x%10^48,x/=10;
      while(qr) putchar(qu[qr--]);
    }
    inline void Puts(const char*s){
    	for(int i=0;s[i];i++)
			putchar(s[i]);
		putchar('\n');
	}
	struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::write;

template < class type > inline void chkmin ( type &x, type y ) { x = ( x <= y ? x : y ); }
template < class type > inline void chkmax ( type &x, type y ) { x = ( x >= y ? x : y ); }

const int N = 1e3 + 5;
const int mod = 1e9 + 7;

int n;
int f[N][N][2][2];

void Solve () {
  cin >> n;
  f[1][0][0][0] = 1, f[2][0][0][0] = 2;
  for ( int i = 3; i <= n; i ++ ) {
    for ( int j = 0; j <= i - 2; j ++ ) {
      f[i][j][0][0] += f[i - 1][j][0][0] * ( i - j - 2 ) % mod + f[i - 1][j][1][0] * ( i - j - 1 ) % mod;
      f[i][j][0][0] %= mod;
      f[i][j][0][0] += f[i - 1][j + 1][0][0] * ( j + 1 ) % mod + f[i - 1][j + 1][1][0] * j % mod;
      f[i][j][0][0] %= mod;
      f[i][j][0][0] += f[i - 1][j + 1][0][1] + f[i - 1][j + 1][1][1];
      f[i][j][0][0] %= mod;
      f[i][j][1][0] += f[i - 1][j][0][1] * ( i - j - 2 ) % mod + f[i - 1][j][1][1] * ( i - j - 1 ) % mod;
      f[i][j][1][0] %= mod;
      f[i][j][1][0] += f[i - 1][j + 1][1][1] * max ( 0ll, j - 1 ) % mod + f[i - 1][j + 1][0][1] * j % mod;
      f[i][j][1][0] %= mod;
      f[i][j][0][1] = f[i - 1][j][1][0];
      f[i][j][1][1] = f[i - 1][j][1][1];
      if ( j ) {
        f[i][j][0][1] += 2 * f[i - 1][j - 1][0][0] + f[i - 1][j - 1][1][0];
        f[i][j][0][1] %= mod;
        f[i][j][1][1] += 2 * f[i - 1][j - 1][0][1] + f[i - 1][j - 1][1][1];
        f[i][j][1][1] %= mod;
      }
    }
  }
  cout << f[n][0][0][0];
}

signed main () {
#ifdef judge
  freopen ( "Code.in", "r", stdin );
  freopen ( "Code.out", "w", stdout );
  freopen ( "Code.err", "w", stderr );
#endif
  Solve ();
  return 0;
}
0