Codeforces #448 Div2 D. String Mark

また今回もしょうもないミスを繰り返した。
http://codeforces.com/contest/895/problem/D

問題

２つのN文字の文字列A,Bが与えられる。
Aのpermutationである文字列Cのうち、辞書順でB＞C＞Aとなるものは何通りか。

解法

B＞CとなるCの数から、A≧CとなるCの数を引くことを考えると、結局Cとして使える各文字の文字数がわかっているとき、ある文字列Xより辞書順で前に来る文字列の生成方法を求める問題に置き換えられる。
先頭からp文字が等しく、(p+1)文字目でC[p+1]＜X[p+1]となる文字列の数を考える。
残りの(N-(p+1))文字における各文字cの登場回数cnt(c)はわかるので、を足しこんでいけばよい。

string A,B;
int N;
ll fact[1010100];
ll rev[1010100];
ll mo=1000000007;


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

ll hoge(string S,string T) {
	int cnt[26]={};
	ll q=1;
	FORR(c,T) q=q*(++cnt[c])%mo;
	q=modpow(q,mo-2);
	ll ret=0;
	
	int left=S.size();
	FORR(c,S) {
		left--;
		for(int i=0;i<c;i++) if(cnt[i]) {
			(ret+=fact[left]*q%mo*cnt[i])%=mo;
		}
		if(cnt[c]==0) break;
		(q*=cnt[c])%=mo;
		cnt[c]--;
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B;
	N=A.size();
	FORR(c,A) c-='a';
	FORR(c,B) c-='a';
	
	fact[0]=rev[0]=1;
	for(i=1;i<=1010000;i++) {
		fact[i]=fact[i-1]*i%mo;
		rev[i]=modpow(i,mo-2);
	}
	
	
	cout<<(hoge(B,A)-hoge(A,A)-1+mo*2)%mo<<endl;
	
}

まとめ

これは2000ptにしては簡単かも。