TopCoder SRM 825 : Div1 Hard FalseAbove

凡ミスもったいない…。
https://community.topcoder.com/stat?c=problem_statement&pm=17428

問題

1～NのPermutation Pに対し、以下を考える。
i番の人は、「1番から(i-1)番のうちP[i]人が嘘をついている」と発言しているとする。
Pに対し、何人かは正しく、何人かは正しくないことになる。

その時、

• 正しい人の最多数
• 正しい人が最多となるPの組み合わせ数
• 正しい人が最多となるPの組み合わせにおいて、Pのハッシュ値の総和

をそれぞれ求めよ。

解法

Nが偶数の時、以下のパターン(これはN=10の例)が正しい人がN/2名で最多である。(_の部分はN/2より大きい値が何が入っても良い)

_1_2_3_4_5

組み合わせ数は(N/2)!だし、ハッシュ値の総和も計算が容易である。

Nが奇数の時はfloor(N/2)名が最多となり、そのパターンは例えばN=9の時は以下の通り。

_1_2_3_4_
__2_3_4_5
_1__3_4_5
_1_2__4_5
_1_2_3__5

一番上は、(ceil(N/2))以上の値はどこに入ってもよいので計算は容易。
それ以外は、1,2,3,4は2,3,4,5の直前には入ってはいけないので、その点を注意して計算していこう。
各パターンについて一発で数え上げても良いし、差分を考えて行ってもよい。
以下はパターン毎の差分を更新していく方法である。

const ll mo=1000000007;

const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

class FalseAbove {
	public:
	vector <int> solve(int N) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
		
		ll L=N/2;
		ll R=N/2+1;
		ll M=N+1;
		ll pat=0;
		ll spat=0;
		int i;
		if(N%2==0) {
			pat=fact[L];
			ll sum=1LL*(N/2+1+N)*(N/2)/2%mo;
			for(i=0;i<N;i+=2) {
				spat+=sum*modpow(M,i)%mo*fact[L-1]%mo;
			}
			for(i=1;i<N;i+=2) {
				spat+=(i+1)/2*pat%mo*modpow(M,i)%mo;
			}
		}
		else {
			
			// _1_2_3_4_
			pat=fact[R];
			ll sum=1LL*(N/2+1+N)*(N-L)/2%mo;
			for(i=0;i<N;i+=2) {
				spat+=sum*modpow(M,i)%mo*fact[L]%mo;
			}
			for(i=1;i<N;i+=2) {
				spat+=(i+1)/2*fact[R]%mo*modpow(M,i)%mo;
			}
			
			
			//_1_2_3__5
			//_1_2__4_5
			//_1__3_4_5
			//__2_3_4_5
			ll w=0;
			FOR(i,N) {
				if(i&&i%2==0) continue;
				w+=modpow(M,i);
			}
			w%=mo;
			ll usum=1LL*(R+1+N)*(N-R)/2%mo;
			ll LS=0,RS=0;
			for(i=2;i<=R;i++) (RS+=i*modpow(M,i*2-2))%=mo;
			for(i=1;i<=L;i++) {
				pat+=L*fact[L]%mo;
				spat+=(L*fact[L-1]%mo)*usum%mo*modpow(M,i*2-1)%mo;
				spat+=((L-1)*fact[L-1]%mo)*usum%mo*(w-modpow(M,i*2-1)+mo)%mo;
				spat+=(fact[L]%mo)*i%mo*(w-modpow(M,i*2-1)+mo)%mo;
				spat+=(LS+RS)*L%mo*fact[L]%mo;
				
				w=(w-modpow(M,i*2-1)+modpow(M,i*2)+mo)%mo;
				(LS+=i*modpow(M,i*2-1)%mo)%=mo;
				(RS+=mo-(i+1)*modpow(M,i*2)%mo)%=mo;
				
			}
			
			
		}
		
		
		return {(int)L,(int)(pat%mo),(int)(spat%mo)};
	}
}

まとめ

本番剰余を1個入れ忘れてオーバーフローした…。
まあ通っても順位は2しか変わらないんだけども。