Codeforces #563 Div2 E. Ehab and the Expected GCD Problem

Div2にしても簡単よりだった回っぽい？
https://codeforces.com/contest/1174/problem/E

問題

数列pに対し、f(p)とはpのprefixのGCDからなる数列g中に現れるユニークな値の種類とする。
整数Nが与えられる。1～Nの全通りのPermutation pに対し、f(p)が最大となるようなものの数を求めよ。

解法

f(p)が最大となるようにするには、gは徐々に値が増えていくものが良い。
実際、gの最大値は2^kまたは3*2^kとなるのがベストである。

前者の場合、gは(重複分を削除すると)1,2,4,....2^kと倍々になるのが良く、後者はどこかで3倍になるタイミングがある。
あとはそのようなPermutationをそれぞれ数え上げればよい。

ll mo=1000000007;
ll N;
const int NUM_=1400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll comb(ll N_, ll C_) {
	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 hoge(int cur,vector<int> V) {
	int sum=0;
	ll ret=1;
	FORR(v,V) {
		int n=N/cur-sum;
		ret=ret*comb(N-sum-1,n-1)%mo*fact[n]%mo;
		sum+=n;
		cur/=v;
	}
	ret=ret*fact[N-sum]%mo;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	comb(1,1);
	cin>>N;
	x=y=0;
	while(1<<(x+1) <= N) x++;
	while(3<<(y+1) <= N) y++;
	
	ll ret=0;
	vector<int> V;
	ll sum=0;
	FOR(i,x) V.push_back(2);
	ret+=hoge(1<<x,V);
	if(y+1==x) {
		V.clear();
		FOR(i,y) V.push_back(2);
		V.push_back(3);
		do {
			ret+=hoge(3<<y,V);
		} while(next_permutation(ALL(V)));
	}
	cout<<ret%mo<<endl;
}

まとめ

どんどん書くのが遅れていく…。