Codeforces #1041 : F. Hamed and AghaBalaSar

問題名の部分なんて読むんだろ。
https://codeforces.com/contest/2127/problem/F

問題

正整数N,Mが与えられる。
以下を満たす整数列Aを考える。

• 長さはN
• 各要素0～Mのいずれかの値を持ち、また末尾は最大値である。

f(A)を以下の通り定義する。

• posの初期値は1
• resの初期値は0
• nex[i]は、A[i]＜A[nex[i]]となるi以上最小のindex。
• A[pos]がA[N]未満の間、pos=nex[pos]で遷移する。その際、resにA[nex[pos]]-A[pos]を加える。
• A[pos]=A[N]の時、posをインクリメントする。
• 最終的なresがf(A)の値

N,Mが与えられたとき、条件を満たすAにおけるf(A)の総和を求めよ。

解法

f(A)は、A中の最大値の総和から、最大値のすぐ右にある値及びA[1]を引いたものとなる。
g(n,m,x) := N要素の整数列のうち、各要素がX以下であり、総和がMのもの
を用いると、

• 最大値の総和
• 最大値のすぐ右にある値の総和
• A[1]の総和

をそれぞれ算出できる。

int T,N,M;
const ll mo=1000000007;

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		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;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(ll P_,ll Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}

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;
}

ll g(int n,int m,int x) {
	if(m<0) return 0;
	ll ret=0;
	for(int t=0;m-t*(x+1)>=0;t++) {
		ll a=comb(n,t)*comb(m+n-1-t*(x+1),n-1)%mo;
		if(t%2) a=mo-a;
		ret+=a;
	}
	return ret%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		ll ret=0;
		
		for(x=1;x<=M;x++) {
			ll ans=x*g(N-1,M-x,x)%mo;
			ll ais=x*g(N-2,M-2*x,x)%mo*(N-1)%mo;
			
			ll a1s=(M-x)*modpow(N-1)%mo*g(N-1,M-x,x)%mo;
			ll ars=(M-x)*g(N-2,M-2*x,x)%mo;
			ret+=ans+ais-a1s-ars;
			
			
		}
		
		/*
		//正解だが計算時間が長い
		cout<<"!"<<N<<" "<<M<<endl;
		for(int ma=1;ma<=M;ma++) {
			for(int num=1;num*ma<=M&&num<N;num++) {
				//基本(ma+1)*num点入るが、先頭の要素がxの時(x+1)点失う
				//(N-num)要素に合計M-ma*num個を振り分けるやり方、ただし上限はma
				//ここから先頭要素分引く
				ll pat=0;
				for(k=0;k<(M-num*ma+ma)/ma;k++) {
					for(int f=0;f<ma&&M-num*ma-k*ma-f>=0;f++) {
						ll a=hcomb(N-num-1,M-num*ma-k*ma-f)*comb(N-num-1,k)%mo;
						//cout<<ma<<" "<<num<<" "<<k<<" "<<a<<endl;
						//(N-num-1)個をnum個のスロットに分ける
						a=a*hcomb(num,N-num-1)%mo;
						a=a*(ma-f)%mo;
						a=a*num%mo;
						if(k%2) a=(mo-a)%mo;
						pat+=a;
					}
				}
				ret+=pat;
			}
		}
		*/
		cout<<(ret%mo+mo)%mo<<endl;
		
	}
}

まとめ

本番中計算量を落としきれなかった。