HackerRank HourRank 25 : B. Maximum Palindromes

明けましておめでとうございます。
https://www.hackerrank.com/contests/hourrank-25/challenges/maximum-palindromes

問題

アルファベット小文字で構成される文字列Sが与えられるので、以下のクエリに順次答えよ。
各クエリはSの部分S[L..R]で構成される。
このうち一部の文字を抜き出し、並べ替えて回文を作る。
作れる最長の回文において、その組み合わせ数を求めよ。

解法

文字ごとに登場回数の累積和をとっておき、クエリの区間における各文字の登場回数を求めよう。
まず、登場回数が奇数となる文字があるなら、それのどれかを回文の中央に持ってくるのでその文字の種類分答えがある。
それ以外は、a～zについて偶数個ずつ用いて回文の両端に持っていくことになる。
f(c) := S[L..R]における文字cの登場回数÷2(小数点以下切り捨て)とすると、中央以外の文字の並びは通りとなる。

string S;
int N;
int P[26][101010];
int Q,L,R;
ll mo=1000000007;

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	FOR(i,26) {
		FOR(x,N) {
			P[i][x+1]=P[i][x]+(S[x]=='a'+i);
		}
	}
	
	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;
	
	cin>>Q;
	while(Q--) {
		cin>>L>>R;
		L--;
		int num[26]={},odd=0,sum=0;
		FOR(i,26) {
			num[i]=(P[i][R]-P[i][L])/2;
			sum+=num[i];
			if((P[i][R]-P[i][L])&1) odd++;
		}
		ll ret=odd?odd:1;
		(ret*=fact[sum])%=mo;
		FOR(i,26) {
			ret=ret*factr[num[i]]%mo;
		}
		cout<<ret<<endl;
	}
}

まとめ

BまではFA取れたんだけどね。