yukicoder : No.2001 Distanced Triple

そこまで難しくはない？
https://yukicoder.me/problems/no/2001

問題

整数の区間[L,R]と正整数A,B,Cが与えられる。この区間内の整数(x,y,z)の組のうち、以下を満たすのは何通りか。

• x + A ≦ y
• y + B ≦ z
• x + C ≦ z

解法

x,y,zをL引いても多項式の成立関係は変わらないので、[L,R]の区間を[0,R'] (R'=R-L)としても解は変わらない。
x + A + B ≦ y + B ≦ zであることを考える。

• C≦A+Bの場合
  • 3つ目の条件は無視してよい。x,y,zを最低A,Bの間隔をあけて3つ[0,R']の区間から値を選ぶ方法なので、これはComb(R'-A-B,3)を答えればよい。
• C＞A+Bの場合
  • まず3つ目の条件を無視すると、上と同様Comb(R'-A-B,3)となる。
  • ここから、包除原理の要領で、1つ目と2つ目の条件に違反するケースを足し引きしよう。

ll L,R,A,B,C;
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>R;
	cin>>A>>B>>C;
	R-=L;
	
	if(R<C) {
		cout<<0<<endl;
		return;
	}
	
	__int128 w;
	if(C<=A+B) {
		C=A+B;
		R-=C;
		__int128 v=R%mo;
		w=(v+3)*(v+2)*(v+1)/6;
	}
	else {
		R-=A+B;
		C-=A+B;
		__int128 v=R%mo;
		w=(v+3)*(v+2)*(v+1)/6;
		
		// (x+1)*(R-x+1)=-x^2+R*x+(R+1)
		__int128 a=(C-1)%mo;
		w+=a*(a+1)*(2*a+1)/6%mo;
		w-=(a*(a+1)/2)%mo*v%mo;
		w-=(a+1)*(v+1)%mo;
	}
	if(R<0) w=0;
	w=(w%mo+mo)%mo;
	cout<<(ll)w<<endl;
}

まとめ

細かいところを詰めるのが割としんどい。