R13
T1
显然，可以将其转换成其中一个字符串全为0。
同时，不难发现第一个位置第一个区间可以改，而改了之后第一个区间就不能再改了，所以能影响到第二个的位置第二个区间。以此类推
模拟即可。
点击查看代码#include
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1e6+5;
int d[maxn];
signed main()
{freopen("seq.in","r",stdin);freopen("seq.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n,k;cin>>n>>k;string s,t;cin>>s>>t;s=" "+s,t=" "+t;int lst=0;for(int i=1;i<=n+1;i++){int cur=i<=n?(s[i]^t[i]):0;d[i]=cur^lst,lst=cur;}int ans=0;for(int r=1;r<=min(k,n+1);r++){int cnt=0,q1=0;for(int q=r;q<=n+1;q+=k)if(d[q]){cnt++;if(cnt&1) q1=q;else ans+=(q-q1)/k;}if(cnt&1){cout<<-1<<'\n';return 0;}}cout<T2
显然，你得先弄清楚题目给的函数应该怎么算
显然，可以用贪心解决
对于求和的内容可以容斥。
即在题目给的条件下，从高往低去填数。
这样就类似一个数位dp。只需要算对应的长度就行了，然后对于条件至多只有8个，所以就。所以说就是 \(2^8\) 种情况
点击查看代码#include
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
using namespace std;
const int maxn=5e5+5,mod=998244353;
int L;
vector l,r,x,y;
int pw[maxn];
int lowN[maxn],lowM[maxn];
int dp[2][2][2],ndp[2][2][2];
int minus1(vector &v)
{int i=L;while(i&&!v[i]) v[i]=1,i--;if(!i) return 0;v[i]=0;return 1;
}
int G(vector &hin,vector &him)
{int cur=0;for(int pos=0;pos<=L;pos++){lowN[pos]=(cur+1)%mod;if(pos=0;pos--){int bN=hin[L-pos],bM=him[L-pos];memset(ndp,0,sizeof(ndp));for(int tA=0;tA<=1;tA++)for(int tB=0;tB<=1;tB++)for(int oc=0;oc<=1;oc++){int ways=dp[tA][tB][oc];if(!ways) continue;for(int bi=0;bi<=1;bi++){if(tA&&bi>bN) continue;for(int bj=0;bj<=1;bj++){if(tB&&bj>bM) continue;int val,noc;if(oc) val=1,noc=1;else if((bi & bj)==0) val=bi^bj,noc=0;else val=1,noc=1;int ntA=(tA&&bi==bN),ntB=(tB&&bj==bM);int wi=ntA?lowN[pos]:pw[pos];int wj=ntB?lowM[pos]:pw[pos];if(val){int add=ways*wi%mod*wj%mod*pw[pos]%mod;ans+=add;if(ans>=mod) ans-=mod;}ndp[ntA][ntB][noc]=(ndp[ntA][ntB][noc]+ways)%mod;}}}memcpy(dp,ndp,sizeof(dp));}return ans;
}signed main()
{freopen("xor.in","r",stdin); freopen("xor.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>L;string s0,s1,s2,s3;cin>>s0>>s1>>s2>>s3;s0=" "+s0,s1=" "+s1,s2=" "+s2,s3=" "+s3;l.assign(L+2,0),r.assign(L+2,0),x.assign(L+2,0),y.assign(L+2,0);for(int i=1;i<=L;i++) l[i]=s0[i]-'0',r[i]=s1[i]-'0',x[i]=s2[i]-'0',y[i]=s3[i]-'0';pw[0] = 1;for(int i=1;i<=L;i++) pw[i] = pw[i-1]*2%mod;int okL=minus1(l),okX=minus1(x);int ans=G(r, y);if(okL) ans=(ans-G(l,y)+mod)%mod;if(okX) ans=(ans-G(r,x)+mod)%mod;if(okL&&okX) ans=(ans+G(l,x))%mod;cout<