이진 시퀀스의 특성 함수 값을 수학적으로 표현합니다.
w를 \\(0\\), b를 \\(1\\)로 매핑합니다. 연속된 00 또는 11의 삭제 연산은 각 비트의 패리티(홀짝성)에 영향을 주지 않습니다.
홀수 위치의 비트를 반전시키면, 01 또는 10의 삭제가 허용되며, 최종 남은 단색 세그먼트의 길이가 함수를 결정합니다.
\\(u_0, u_1\\): 홀/짝 미지수 개수
\\(v\\): 알려진 값의 합
목표: 분포 차 \\(d\\)를 기반으로 이항 계수 합산
\[\sum_{i-j=d} \binom{u_0}{i} \binom{u_1}{j}\]
이를 선형 시간 내에 계산하기 위해 Vandermonde 합을 활용합니다.
개선된 핵심 공식:
\[\sum_{d \equiv V \pmod{2}} |d - V| \binom{A+B}{B+d}\]
재귀적 합산을 위한 보조 함수 정의:
\[F(A,B,V) = \sum_{k \geq 0} \binom{A+B}{B+V-2k}\]
이항 계수의 패리티 그룹화를 통해:
\[\binom{A+B}{B+V-2k} + \binom{A+B}{B+V-2k-1} = \binom{A+B}{B+V-k}\]
\[\binom{A+B}{B+V-2k} - \binom{A+B}{B+V-2k-1} = \binom{A+B-1}{B+V}\]
이를 이용해 단일 변수 업데이트 시 \\(O(1)\\) 연산이 가능해집니다.
기본 해법
#include <iostream>
using namespace std;
typedef long long ll;
const int MOD = 998244353, HALF = (MOD+1)/2;
int fac[200005], invFac[200005];
int modPow(int base, int exp) {
int res = 1;
while(exp) {
if(exp & 1) res = (ll)res * base % MOD;
base = (ll)base * base % MOD;
exp >>= 1;
}
return res;
}
void precalc() {
fac[0] = 1;
for(int i=1; i<=200000; i++) fac[i] = (ll)fac[i-1]*i % MOD;
invFac[200000] = modPow(fac[200000], MOD-2);
for(int i=199999; i>=0; i--) invFac[i] = (ll)invFac[i+1]*(i+1) % MOD;
}
int nCr(int n, int r) {
if(r<0 || r>n) return 0;
return (ll)fac[n]*invFac[r] % MOD * invFac[n-r] % MOD;
}
int main() {
precalc();
int len, q;
string seq;
cin >> len >> q >> seq;
int unknown[2]={0}, knownSum=0;
for(int i=0; i<len; i++) {
if(seq[i]=='?') unknown[i&1]++;
else knownSum += (seq[i]=='b')^(i&1) ? 1 : -1;
}
int target = (knownSum + unknown[0] - unknown[1])/2;
ll total = 0;
for(int d=-len; d<=len; d++)
if((d^target)&1 == 0)
total = (total + abs(d-target)*nCr(unknown[0]+unknown[1], unknown[1]+d)) % MOD;
ll result = total * modPow(HALF, unknown[0]+unknown[1]) % MOD;
cout << result;
}#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 200000, MOD = 998244353, HALF = (MOD+1)/2;
int power2[MAX_N+1], invPower2[MAX_N+1], fac[MAX_N+1], invFac[MAX_N+1];
int modPow(int base, int exp) {/* 동일 구현 */};
void precompute() {/* 팩토리얼 및 거듭제곱 테이블 생성 */};
int nCr(int n, int r) {/* 동일 구현 */};
struct State {
int paramA, paramB, paramV;
State(int a, int b, int v) : paramA(a), paramB(b), paramV(v) {}
};
int dynamicF(int A, int B, int V) {
static int currA=0, currB=0, currSum=1;
while(currA < A) {
currSum = (2LL*currSum - nCr(currA, currB) + MOD) % MOD;
currA++;
}
while(currB < V) currSum = (currSum + nCr(currA, ++currB)) % MOD;
return currSum * HALF % MOD;
}
int solve(int A, int B, int V) {
int res = 0;
if(A+B == 1) return (B+V>=0 && ((B+V)&1)) ? 1 : 0;
ll term1 = (ll)(A+B)*power2[A+B-2] % MOD;
ll term2 = (ll)(A+B)*(MOD - dynamicF(A, B-1, V)) % MOD;
ll term3 = (ll)(B+V)*dynamicF(A, B, V) % MOD;
return (term1 + term2 + term3) % MOD;
}
int main() {
precompute();
int len, queries;
string initSeq;
cin >> len >> queries >> initSeq;
vector<State> states;
int gap[2]={0}, baseVal=0;
auto adjust = [&](int idx, int mult) {
if(initSeq[idx]=='?') gap[idx&1] += mult;
else baseVal += ((initSeq[idx]=='b')^(idx&1)) ? mult : -mult;
};
for(int i=0; i<len; i++) adjust(i,1);
for(int i=0; i<=queries; i++) {
if(i) {
int idx; char c;
cin >> idx >> c;
adjust(idx-1, -1);
initSeq[idx-1] = c;
adjust(idx-1,1);
}
int targetV = (baseVal + gap[0] - gap[1])/2;
states.emplace_back(gap[0], gap[1], targetV);
}
for(auto &s : states) {
int ans = solve(s.paramA, s.paramB, s.paramV);
ans = (ll)ans * invPower2[s.paramA + s.paramB] % MOD;
cout << ans << '\n';
}
}