Codeforces #810 : Div1 C. XOR Triangle

まぁまぁすんなり。
https://codeforces.com/contest/1710/problem/C

問題

2進数で最大200000桁の整数Nが与えられる。
以下を満たす整数の組(a,b,c)は何通りか。

• a,b,cは0以上N以下
• (a xor b),(a xor c),(b xor c)の長さを3辺に取る面積正の三角形ができる

解法

(a xor b),(a xor c),(b xor c)の2進数における各桁では、1となる箇所が0個か2個である。
よって、(a xor b),(a xor c),(b xor c)のそれぞれ、どこかの桁で、単独で0を取るタイミングが1回以上あれば、面積が正となる。

この情報をもとに、a,b,cがN以下であることが確定したか、また(a xor b),(a xor c),(b xor c)それぞれ単独で0を取るタイミングが合ったかどうかを状態として持ち、桁DPしていこう。

int N;
string S;
const ll mo=998244353;

ll dp[202020][2][2][2][2][2][2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	dp[0][1][1][1][0][0][0]=1;
	FOR(i,N) {
		int sa2,sa1,sa0,is2,is1,is0;
		int t2,t1,t0;
		FOR(sa2,2) FOR(sa1,2) FOR(sa0,2) FOR(t2,2) FOR(t1,2) FOR(t0,2) {
			int nsa2=sa2;
			int nsa1=sa1;
			int nsa0=sa0;
			if(sa2) {
				if(S[i]=='0'&&t2) continue;
				if(S[i]=='1'&&t2==0) nsa2=0;
			}
			if(sa1) {
				if(t1>t2) continue;
				if(t1<t2) nsa1=0;
			}
			if(sa0) {
				if(t0>t1) continue;
				if(t0<t1) nsa0=0;
			}
			
			
			FOR(is2,2) FOR(is1,2) FOR(is0,2) if(dp[i][sa2][sa1][sa0][is2][is1][is0]) {
				int nis2=is2;
				int nis1=is1;
				int nis0=is0;
				if(t2==0&&t1&&t0) nis2=1;
				if(t2==1&&t1==0&&t0==0) nis2=1;
				if(t1==0&&t2&&t0) nis1=1;
				if(t1==1&&t2==0&&t0==0) nis1=1;
				if(t0==0&&t2&&t1) nis0=1;
				if(t0==1&&t2==0&&t1==0) nis0=1;
				(dp[i+1][nsa2][nsa1][nsa0][nis2][nis1][nis0]+=dp[i][sa2][sa1][sa0][is2][is1][is0])%=mo;
			}
			
		}
	}
	
	ll ret=dp[N][1][0][0][1][1][1]+dp[N][0][0][0][1][1][1];
	cout<<ret*6%mo<<endl;
	
	
}

まとめ

どうにか解けてよかったね。