kmjp's blog

競技プログラミング参加記です

yukicoder : No.1062 素敵なスコア

yukicoder

この数え上げは結構しんどい。
https://yukicoder.me/problems/no/1062

問題

1～Nの順列に対し、整数Kを定めたとき以下のように数列を変形する。

  • Kより大きな値の最左のものが、K以下の値の最も右のものより左にある限り、それらを入れ替える。

今、Nと2整数A1,A2が与えられる。
N!通りの順列に対し、K=A1とK=A2を適用して得られる数列において値が一致する要素数の総和を求めよ。

解法

Editorialそのままだけど。
A1＜A2として一般化する。
x=A1、y=A2-A1、z=N-A2とする。

どちらの操作でも移動しない数と、どちらの操作でも同じように移動する数をそれぞれ数えよう。

  • どちらの操作でも移動しない数
    • 数列を先頭x個、次のy個、最後のz個の3ブロックに分ける。K=A1の操作では1～xが先頭に集まるし、K=A2の操作ではN-y+1～Nが最後に集まる。
    • よって、(1～x)、(x+1～y)、(y+1～N)の各ブロックに各ブロックがあれば、それらはいずれの操作でも移動しない。
    • 各ブロック内の値が、ブロック内のどこかにいるパターンを考えると総和は(x^2+y^2+z^2)*(N-1)!
  • どちらの操作でも移動する数
    • 問題はこちら。先頭ブロックにある(y+1～N)の値は、この操作で最後のブロックに行く可能性があるし、最後のブロックにある(1～x)の値はこの操作で最初のブロックに行く可能性がある。これらがうまく入れ替わるケースを考えよう。
    • P[i]とP[N-j]が入れ替わってうまくいくには、以下を両方満たす必要がある。
      • P[i]の手前にあるA1より大きな数の登場頻度とP[N-j]以降にあるA2以下の登場頻度が等しい
      • P[i]の手前にあるA2より大きな数の登場頻度とP[N-j]以降にあるA1以下の登場頻度が等しい
    • これを満たすには、先頭i個と末尾j個がA1以下かA2より大きいのいずれかであればよい。
    • i,jを総当たりすると、 \displaystyle \sum_{i=0}^{x-1} \sum_{j=0}^{z-1} {}_{i+j}{\rm C}_{i} \times \frac{(N-i-j-2)!}{(x-i-1)! \cdot (z-j-1)!} \cdot 2 \cdot x! \cdot z! \displaystyle = \sum_{i=0}^{x-1} \sum_{j=0}^{z-1} 2 \times (i+j)! \times (N-(i+j)-2)! \times \frac{x!}{i! \times (x-i-1)!} \times \frac{z!}{j! \times (z-j-1)!}となり、iに関する式とjに関する式の積和の形になるのでNNTに持ち込める。
ll N,A1,A2;
const ll mo=998244353;
ll fact[202020];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}
vector<ll> fft(vector<ll> v, bool rev=false) {
	int n=v.size(),i,j,m;
	
	for(i=0,j=1;j<n-1;j++) {
		for(int k=n>>1;k>(i^=k);k>>=1);
		if(i>j) swap(v[i],v[j]);
	}
	for(int m=2; m<=n; m*=2) {
		ll wn=modpow(5,(mo-1)/m);
		if(rev) wn=modpow(wn);
		for(i=0;i<n;i+=m) {
			ll w=1;
			for(int j1=i,j2=i+m/2;j2<i+m;j1++,j2++) {
				ll t1=v[j1],t2=w*v[j2]%mo;
				v[j1]=t1+t2;
				v[j2]=t1+mo-t2;
				while(v[j1]>=mo) v[j1]-=mo;
				while(v[j2]>=mo) v[j2]-=mo;
				w=w*wn%mo;
			}
		}
	}
	if(rev) {
		ll rv = modpow(n);
		FOR(i,n) v[i]=v[i]*rv%mo;
	}
	return v;
}

vector<ll> MultPoly(vector<ll> P,vector<ll> Q,bool resize=false) {
	if(resize) {
		int maxind=0,pi=0,qi=0,i;
		int s=2;
		FOR(i,P.size()) if(norm(P[i])) pi=i;
		FOR(i,Q.size()) if(norm(Q[i])) qi=i;
		maxind=pi+qi+1;
		while(s*2<maxind) s*=2;
		P.resize(s*2);Q.resize(s*2);
	}
	P=fft(P), Q=fft(Q);
	for(int i=0;i<P.size();i++) P[i]=P[i]*Q[i]%mo;
	return fft(P,true);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	fact[0]=1;
	for(i=1;i<=202010;i++) fact[i]=fact[i-1]*(i)%mo;
	
	cin>>N>>A1>>A2;
	if(A2<A1) swap(A1,A2);
	ll X=A1;
	ll Y=A2-A1;
	ll Z=N-A2;
	ll ret=(X*X+Y*Y+Z*Z)%mo*fact[N-1]%mo;
	vector<ll> P,Q;
	FOR(i,X) P.push_back(modpow(fact[X-i-1]*fact[i]%mo)*fact[X]%mo);
	FOR(i,Z) Q.push_back(modpow(fact[Z-i-1]*fact[i]%mo)*fact[Z]%mo);
	P=MultPoly(P,Q,1);
	
	FOR(i,X+Z-1) {
		ret+=fact[i]*fact[N-i-2]%mo*2*P[i]%mo;
	}
	
	
	
	cout<<ret%mo<<endl;
	
}

まとめ

これさらっとは思いつかないなぁ。