Codeforces #678 Div2 F. Sum Over Subsets

Div2最終問にしてはオーソドックスな問題。
http://codeforces.com/contest/1436/problem/F

問題

1～10^5で構成されるMultiset Sが与えられる。
Sのsubset A,Bのうち、

• B ⊂ A
• |B| = |A|-1
• AのGCDは1

となるものについて、Aの総和とBの総和の積を求めよ。

解法

g(x) := 上記条件の最後、AのGCDがxの倍数であるものに関するAの総和とBの総和の積
を求められれば、約数包除の要領で
f(x) := 上記条件の最後、AのGCDがxであるものに関するAの総和とBの総和の積
を求められるので、f(1)を答えればよい。

g(x)は、multiset Sのうちxの倍数について、個数・総和・二乗和を求められれば計算できる。

int M;
ll F[101010];
ll V[101010];
const ll mo=998244353;
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;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	FOR(i,M) {
		cin>>x>>y;
		V[x]=y;
	}
	
	for(i=100000;i>=1;i--) {
		ll S1=0,S2=0,N=0;
		for(j=i;j<=100000;j+=i) {
			N+=V[j];
			(S1+=V[j]*j)%=mo;
			(S2+=V[j]*j%mo*j)%=mo;
		}
		
		if(N>=2) {
			F[i]+=S2*((N-1)%mo)%mo*modpow(2,N-2);
			ll v=(S1*S1%mo+mo-S2)%mo;
			F[i]+=v*modpow(2,N-2);
			if(N>=3) F[i]+=v*((N-2)%mo)%mo*modpow(2,N-3);
			
		}
		F[i]%=mo;
		
		
		for(j=i*2;j<=100000;j+=i) F[i]-=F[j];
		F[i]=(F[i]%mo+mo)%mo;
	}
	cout<<F[1]<<endl;
	
	
}

まとめ

なんか解法ありきで無理やり作った問題に見えて余り楽しめないな…