Codeforces #940 : Div2 E. Carousel of Combinations

なるほど。
https://codeforces.com/contest/1957/problem/E

問題

C(i,k)は、1～iのうちk個を選び円周状に並べる組み合わせの数とする。
整数Nが与えられるので、
を答えよ。

解法

C(i,j) = P(i,j)/jだが、P(i,j)は連続するj個の整数の積なので、C(i,j) = (j-1)! * floor(i,j)と置き換えられる。
jが4以外の合成数の時、(j-1)!はjの倍数なのでC(i,j)%j=0となる。
jが素数の場合、(j-1)!%j=j-1なので、結局C(i,j)=(-1)*floor(i,j)となる。

区間加算できるBITを用いて素数jに対しfloor(i,j)の寄与分を各iに計上しよう。

int T,N;
const ll mo=1000000007;

template<class V, int ME> class BIT_r {
public:
	V bit[2][1<<ME];
	BIT_r(){clear();};
	void clear() {ZERO(bit);};
	
	void update(int entry, V val0, V val1) {
		entry++;
		while(entry <= 1<<ME) bit[0][entry-1]+=val0, bit[1][entry-1] += val1, entry += entry & -entry;
	}
	V total(int entry) {
		if(entry<0) return 0;
		int e=entry++;
		V v0=0,v1=0;
		while(entry>0) v0+=bit[0][entry-1], v1+=bit[1][entry-1], entry -= entry & -entry;
		return e*v0+v1;
	}
	void add(int L, int R, V val) { // add val to L<=x<=R
		update(L,val,-val*(L-1));
		update(R+1,-val,val*R);
	}
	int lower_bound(V val) { //単調増加の時のみ使える
		V v0=0,v1=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) {
			if((ent+(1<<i)-1)*(v0+bit[0][ent+(1<<i)-1])+(v1+bit[1][ent+(1<<i)-1])<val) {
				v0+=bit[0][ent+(1<<i)-1];
				v1+=bit[1][ent+(1<<i)-1];
				ent+=(1<<i);
			}
		}
		return ent;
	}
};
BIT_r<ll,21> bt;

int p[2010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=1000000;i++) bt.add(i,i,(6*(i/4)%4));
	for(i=2;i<=1000000;i++) if(p[i]==0) {
		for(j=1;i*j<=1000000;j++) {
			p[i*j]=1;
			bt.add(i*j,i*(j+1)-1,(i-j%i)%i);
		}
	}
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll a=bt.total(N);
		a=(a%mo+mo)%mo;
		cout<<a<<endl;
	}
	
	
	
}

まとめ

実装は割と軽めではあるんだよな。