結果

問題 No.93 ペガサス
コンテスト
ユーザー vjudge1
提出日時 2026-06-05 12:53:45
言語 C++17(clang)
(clang++ 22.1.2 + boost 1.89.0)
コンパイル:
clang++ -O2 -lm -std=c++1z -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 23 ms / 5,000 ms
コード長 2,152 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,800 ms
コンパイル使用メモリ 173,072 KB
実行使用メモリ 23,296 KB
最終ジャッジ日時 2026-06-05 12:54:06
合計ジャッジ時間 9,159 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
//#define LOCAL
using namespace std;
typedef long long ll;
const int N=1005;
const ll mod=1e9+7;
int n; 
ll f[N][N][2][2]; 
//???????????????????????? 
void upd(ll &x,ll y){
	x=(x+y)%mod;
	if(x<0) x+=mod;
}
namespace solve1{
	void calc(){
		f[1][0][0][0]=1;
		f[2][0][0][0]=2;
		for(int i=3;i<=n;i++){
		    for(int j_old=0;j_old <i-1;j_old++){ // ???????
		        for(int a=0;a<2;a++){ // ?a?i-2?i-4????
		            for(int b=0;b<2;b++){ // ?b?i-1?i-3????
		                ll val = f[i-1][j_old][a][b];
		                if(val ==0) continue;	                    
		                // 1a????i-1?i-3????????a=1?
		                if(a ==1) upd(f[i][j_old][b][1], val);
		                // 1b????i-1???????
		        		upd(f[i][j_old+1][b][1], val * (2 -a) % mod); 
		                // 2a????i-1?i-3????????b=1?????a'=0
		                if(b ==1 && j_old >=1){
		                    upd(f[i][j_old-1][0][0], val);
		                }
		                // 2b??????????
		                ll cnt2b = (j_old -a) - b;
		                if(cnt2b >0 && j_old >=1){
		                    upd(f[i][j_old-1][b][0], val * cnt2b % mod);
		                }	
		                // 3??????
		                ll cnt3 = (i -2) - (j_old -a);
		                upd(f[i][j_old][b][0], val * cnt3 % mod);
		            }
		        }
		    }
		}
		cout<<f[n][0][0][0]<<endl;
	}
}
int main(){
	#ifdef LOCAL
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);	
	#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	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-1;j++){
			for(int a=0;a<2;a++){ //i-1 & i-3
				for(int b=0;b<2;b++){ //i-2 & i-4
					ll w=f[i-1][j][a][b];
					//???i-1 & i-3 ??? 
					if(a && j) (f[i][j-1][0][0]+=w)%=mod;
					//???i-2 & i-4 ??
					if(b) (f[i][j][1][a]+=w)%=mod;
					//????????
					if(j-a-b>0 && j>0) (f[i][j-1][0][a]+=w*(j-a-b))%=mod;
					//??i-2??
					if(2-b>0) (f[i][j+1][1][a]+=w*(2-b))%=mod;
					//??????
					if(i-j-(2-b)>0) (f[i][j][0][a]+=w*(i-j-(2-b)))%=mod; 
				}
			}
		}
	
	}
	cout<<f[n][0][0][0];
	cerr<<'\n'<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
	return 0;
}
0