Codeforces #722 Div1 : B. Kavi on Pairing Duty

Codeforcesの記事作成が遅れているので、今回からDiv1回はB問題から書くようにします。
https://codeforces.com/contest/1528/problem/B

問題

正整数Nが与えられる。
1次元の座標軸上で、等間隔で2N個の点が並んでいる。
これらの点を2つずつN個のペアを作ることを考える。

ペアの対は、以下のいずれかを満たさなければならない。

• 片方のペアが成す区間に、片方のペアが成す区間が内包される
• 両ペアが成す区間の長さが等しい

条件を満たすペアの作り方は何通りか。

解法

f(n) := 後者の条件だけを満たすような2n頂点のペアの組み方
g(n) := いずれかの条件を満たすような2n頂点のペアの組み方
とすると、これはf(n)=σ(n)となる。

次に、前者の条件を考える。
[0,2n-i-1],[1,2n-i-1+1],[2,2n-i-1+2]....[i,2n-1]と区間を作ると、その中にあと(2n-2i)個の点が残る。
その中身の埋め方はg(n-i)通りなので、結局
g(n) = f(n) + g(1)+g(2)+....+g(n-1)
となるので、g(n)を順次計算していこう。

int N;
const ll mo=998244353;

ll F[1010101];
ll S[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	for(i=1;i<=1000000;i++) {
		for(j=i;j<=1000000;j+=i) F[j]++;
	}
	
	for(i=1;i<=1000000;i++) {
		
		F[i]+=S[i-1];
		if(F[i]>=mo) F[i]-=mo;
		S[i]=S[i-1]+F[i];
		if(S[i]>=mo) S[i]-=mo;
		
	}
	cout<<F[N]<<endl;
}

まとめ

750ptでもいい気はするね。