diverta 2019 Programming Contest 2 : E - Balanced Piles

ちょっと戸惑ったけど、解けて良かった。
https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_e

問題

N個の整数列があり、初期値は各要素も0である。
以下の処理を繰り返す。

• 最小値を持つ要素を選ぶ。最小値となる要素が複数ある場合、どれかを選ぶ。この最小値をmとする。
• 数列中の最大値をMとする。先ほどのmが格納された要素を、M以上M+D以下にする。

操作を繰り返し、全要素Hになるような手順は何通りか。

解法

f(k) := 初めて数列中の最大値がkになった瞬間における、そこまでの遷移の手順の組み合わせ数
とする。
残り(N-1)個はk未満なので、うちいくつかがkに並び、そのうち最大値を更新するものが現れたとする。
とするとf(k+1)～f(k+D)にf(k)を足すことになるので、累積和またはBITを使うことができる。
ここで問題は、最小値を持つものが同着で複数あると、その分だけどの順で選ぶかという組み合わせが生じることになる。
これは面倒なので「うちいくつかがkに並び」の時点で考慮してしまうとする。

kに並ぶものが1～N個までであるケースを考えると、一度kの値になった要素がk+1以上になる手順は1!+2!+...+N!通りある。
よってf(k+1)～f(k+D)に(1!+2!+...+N!)*f(k)を足すようにしていけばよい。

ll N,D,H;
ll mo=1000000007;

template<class V, int ME> class BIT_mod {
public:
	V bit[1<<ME];
	BIT_mod(){ZERO(bit);};
	V operator()(int e) {ll s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s%mo;}
	V add(int e,V v) { e++; while(e<=1<<ME) { bit[e-1]+=v; bit[e-1] -= (bit[e-1]>=mo)?mo:0; e+=e&-e;}}
};
BIT_mod<ll,20> bt;
ll fact[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>H>>D;

	fact[0]=1;
	for(i=0;i<=1010000;i++) fact[i+1]=fact[i]*(i+1)%mo;
	
	ll sum=0;
	for(i=1;i<=N;i++) sum+=fact[i];
	sum%=mo;
	
	
	bt.add(1,fact[N]);
	bt.add(D+1,mo-fact[N]);
	for(i=1;i<=H-1;i++) {
		ll cur=bt(i)%mo;
		bt.add(i+1,cur*sum%mo);
		bt.add(i+D+1,mo-cur*sum%mo);
	}
	
	cout<<bt(H)%mo<<endl;
}

まとめ

BIT使っちゃったけど累積和で十分だった。