結果

問題 No.93 ペガサス
コンテスト
ユーザー maroon_kuri
提出日時 2019-06-20 23:20:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 5,000 ms
コード長 3,953 bytes
コンパイル時間 2,015 ms
コンパイル使用メモリ 179,208 KB
実行使用メモリ 19,532 KB
最終ジャッジ日時 2024-12-23 00:16:50
合計ジャッジ時間 3,207 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=a;i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(a>b)a=b;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

using uint=unsigned;
using ull=unsigned long long;

//const uint mod=998244353;
const uint mod=1000000007;
struct mint{
	uint v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint& s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator-()const{return mint()-*this;}
	mint& operator+=(const mint&rhs){return s(v+rhs.v);}
	mint&operator-=(const mint&rhs){return s(v+mod-rhs.v);}
	mint&operator*=(const mint&rhs){
		v=ull(v)*rhs.v%mod;
		return *this;
	}
	mint&operator/=(const mint&rhs){return *this*=rhs.inv();}
	mint operator+(const mint&rhs)const{return mint(*this)+=rhs;}
	mint operator-(const mint&rhs)const{return mint(*this)-=rhs;}
	mint operator*(const mint&rhs)const{return mint(*this)*=rhs;}
	mint operator/(const mint&rhs)const{return mint(*this)/=rhs;}
	mint pow(int n)const{
		mint res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
	friend ostream& operator<<(ostream&os,const mint&m){
		return os<<m.v;
	}
};

//res: k by d table
//for all n sum_{0<=i<k} f_i(n)*a_{n+i} = 0
//f_i(n)=sum_{0<=j<d} res[i][j]*(n+i)^j
vvc<mint> p_recursive(const vc<mint>&a,int d){
	int n=a.size();
	int k=(n+2)/(d+1);
	int m=k*d;
	vvc<mint> x(m,vc<mint>(m+m-1));
	rep(p,m-1)rep(i,k){
		mint w=a[p+i];
		rep(j,d){
			x[i*d+j][p]=w;
			w*=(p+i);
		}
	}
	rep(i,m)
		x[i][m-1+i]=1;
	vc<mint> v;
	rep(i,m){
		int j=0;
		while(j<m-1&&x[i][j].v==0)
			j++;
		if(j==m-1){
			rep(h,i+1)
				v.pb(x[i][m-1+h]);
			break;
		}else{
			rng(h,i+1,m){
				mint w=x[h][j]/x[i][j];
				rep(l,m+m-1)
					x[h][l]-=x[i][l]*w;
			}
		}
	}
	assert(v.size());
	vvc<mint> res=vvc<mint>(int(v.size()+d-1)/d,vc<mint>(d));
	rep(i,v.size())
		res[i/d][i%d]=v[i];
	return res;
}

vc<mint> extend_sequence(const vc<mint>&a,const vvc<mint>& f,int n){
	int k=f.size(),d=f[0].size();
	assert(int(a.size())>=k-1);
	vc<mint> res(n),w(k);
	rep(i,n){
		if(i<k-1)
			res[i]=a[i];
		else{
			rep(j,k){
				w[j]=0;
				mint z=1;
				rep(h,d){
					w[j]+=f[j][h]*z;
					z*=i-k+1+j;
				}
			}
			assert(w[k-1].v);
			mint s=0;
			rep(j,k-1)
				s+=w[j]*res[i-k+1+j];
			res[i]=-s/w[k-1];
		}
	}
	return res;
}

const int Nmax=1010;

mint dp[Nmax][Nmax][2][2];

vc<mint> calc(int n){
	vc<mint> res(n+1);
	res[1]=1;
	dp[2][0][0][0]=2;
	rng(i,2,n+1){
		res[i]=dp[i][0][0][0];
		rep(j,i){
			rep(p,2)rep(q,2){
				mint a=p==0?j:j-1;
				mint b=p==0?2:1;
				mint c=p==0?0:1;
				mint d=mint(i+1)-a-b-c;
				if(j){
					if(q==0){
						dp[i+1][j-1][q][0]+=dp[i][j][p][q]*a;
					}else{
						dp[i+1][j-1][q][0]+=dp[i][j][p][q]*(a-1);
						dp[i+1][j-1][0][0]+=dp[i][j][p][q];
					}
				}
				dp[i+1][j+1][q][1]+=dp[i][j][p][q]*b;
				dp[i+1][j][q][1]+=dp[i][j][p][q]*c;
				dp[i+1][j][q][0]+=dp[i][j][p][q]*d;
			}
		}
	}
	return res;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	auto a=calc(100);
	a.erase(a.bg);
	
	auto f=p_recursive(a,5);
	
	auto ans=extend_sequence(a,f,1000);
	
	int n;cin>>n;
	cout<<ans[n-1]<<endl;
}
0