yukicoder : No.3304 INCREASE decrease

考察次第でコード長代わりそう。
https://yukicoder.me/problems/no/3304

問題

正整数Kと、(K+1)桁以上の整数Nが与えられる。
以下を満たすX,Y,Zは何通りか。
X,Y,Zの下K桁をx,y,zとする。

• 0＜X＜Y＜Z＜N
• 0＜Y-X＝Z-Y
• 0＜x-y＝y-z

解法

N,X,Y,ZのK桁目より上をXu,Yu,Zu、下K桁をNl,Xl,Yl,Zlとする。

Xu・Zu及びXl・Zlは、偶奇が一致しており、かつ大小関係がXu＜Zu・Xl＞Zlを満たしていれば、Yu・Ylが確定する。
なので、あとはXu,Xl,Zu,Zlを数え上げよう。

上の桁に関し

• A: Xu＜Zu=Nuの場合のXu,Zuの組み合わせ
• B: Xu＜Zu＜Nuの場合のXu,Zuの組み合わせ

下の桁に関し

• C: Nl≦Zl＜Xl＜10^K、の場合のXl,Zlの組み合わせ
• D: Zl＜NlかつZl＜Xl＜10^Kの場合のXl,Zlの組み合わせ

を求めよう。これらは偶奇を考慮しながら二項係数の計算を使えば求められる。
あとはA*D + B*(C+D)が解。

int T;
ll N,K;
const ll mo=998244353;

ll p10[20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p10[0]=1;
	FOR(i,19) p10[i+1]=p10[i]*10;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		
		ll U=N/p10[K];
		ll L=N%p10[K];
		
		// 奇数
		ll o=((U+1)/2-(U%2))%mo;
		//偶数
		ll e=(U/2-(U%2==0))%mo;
		// Zの上位桁がNと不一致
		ll U1=(o*(o-1)+e*(e+1))/2%mo;
		// Zの上位桁がNと一致
		ll U2=U/2%mo;
		
		// Zの上位桁がN以上
		o=(p10[K]/2-L/2)%mo;
		e=(p10[K]/2-(L+1)/2)%mo;
		
		ll L2=(o*(o-1)+e*(e-1))/2%mo;
		// 奇数と偶数を2つ選ぶ
		ll L1=((p10[K]/2)%mo*((p10[K]/2-1)%mo)%mo+mo-L2)%mo;
		
		ll ret=U1*L1+U1*L2+U2*L1;
		cout<<ret%mo<<endl;
		
		
	}
	
}

まとめ

両端の偶奇を合わせることによる数え上げ、いつぞやのAGCの解説動画を思い出すな。