yukicoder : No.2279 OR Insertion

こちらはすんなりだった。
https://yukicoder.me/problems/no/2279

問題

N文字の01で構成される文字列Sが与えられる。
この文字列を途中仕切りを入れて複数の文字列にするやり方は2^(N-1)通りある。

それぞれの区切り方において、区切った文字列を2進数とみなした上でbitwise-orを取った値の総和を求めよ。

解法

(0-indexで)d bit目が1になる組み合わせがf(d)通りあるなら、解に(2^d)*f(d)を計上すればよい。
f(d)は、2^(N-1)から(0-indexで)d bit目が0になる組み合わせを引けばよいので、これを数えよう。

Sを反転したうえで、これを区切っていく。
その際、d文字目が0となるように区切っていけばよい。
dp(d,n) := d bit目が0となるように、先頭n文字を区切る区切り方
とすると、
dp(d,n)の値をdp(d,n+1),dp(d,n+2),...dp(d,n+d)に加算できる。
また、S[n+d]=='0'なら、dp(d,n+d+1),dp(d,n+d+2),...にも加算できる。
累積和を取りながら計算すると、d1つにつきO(N)でdp(d,N)を求められるので、全体でO(N^2)。

int N;
string S;
const ll mo=998244353;
ll dp[4040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FORR(c,S) c-='0';
	reverse(ALL(S));
	ll pat=1;
	FOR(i,N-1) pat=pat*2%mo;
	
	ll ret=0;
	ll p2=1;
	FOR(i,N) {
		ZERO(dp);
		dp[0]=1;
		dp[1]=mo-1;
		FOR(j,N) {
			if(j) (dp[j]+=dp[j-1])%=mo;
			ll a=dp[j];
			(dp[j+1]+=a)%=mo;
			if(i+j<N&&S[i+j]==1) (dp[j+i+1]+=mo-a)%=mo;
		}
		
		(dp[N]+=dp[N-1])%=mo;
		ret+=(pat-dp[N]+mo)*p2%mo;
		p2=p2*2%mo;
	}
	cout<<ret%mo<<endl;
}

まとめ

ANDバージョンも大体同じ解き方できそうだね。