CodeForces - 1609E
这种使得整个串不包含子串’abc’的题目，发现可以用线段树维护
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
#define lson now<<1
#define rson now<<1|1
struct seg
{int a,b,c;int ab,bc,abc;
}tr[maxn<<2];
int n,q;
char s[maxn];
void pushup(int now)
{tr[now].a=tr[lson].a+tr[rson].a;tr[now].b=tr[lson].b+tr[rson].b;tr[now].c=tr[lson].c+tr[rson].c;tr[now].ab=min(tr[lson].a+tr[rson].ab,tr[lson].ab+tr[rson].b);tr[now].bc=min(tr[lson].b+tr[rson].bc,tr[lson].bc+tr[rson].c);tr[now].abc=min(tr[lson].a+tr[rson].abc,min(tr[lson].ab+tr[rson].bc,tr[lson].abc+tr[rson].c));
}
void build(int now,int l,int r)
{if(l==r){if(s[l]=='a') tr[now].a=1;if(s[l]=='b') tr[now].b=1;if(s[l]=='c') tr[now].c=1;return;}int mid=l+r>>1;build(now<<1,l,mid);build(now<<1|1,mid+1,r);pushup(now);
}
void change(int now,int l,int r,int pos,char cc)
{if(l==r){tr[now].a=tr[now].b=tr[now].c=0;if(cc=='a') tr[now].a=1;if(cc=='b') tr[now].b=1;if(cc=='c') tr[now].c=1;return;}int mid=l+r>>1;if(pos<=mid) change(lson,l,mid,pos,cc);else change(rson,mid+1,r,pos,cc);pushup(now);
}
int main()
{freopen("a.in","r",stdin);freopen("a.out","w",stdout);scanf("%d%d",&n,&q);scanf("%s",s+1);build(1,1,n);while(q--){int x; char cc;scanf("%d %c",&x,&cc);change(1,1,n,x,cc);printf("%d\n",tr[1].abc);// change(1,1,n,x,s[x]);}return 0;
}
AtCoder - arc061_d
#include<bits/stdc++.h>
using namespace std;
const int maxn=9e5+5;
typedef long long ll;
const ll mod=1e9+7;
int n,m,k;
ll pw[maxn],fac[maxn],inv[maxn],ifac[maxn];
ll C(ll x,ll y)
{return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}
int main()
{freopen("a.in","r",stdin);freopen("a.out","w",stdout);scanf("%d%d%d",&n,&m,&k);pw[0]=1,fac[0]=inv[0]=ifac[0]=inv[1]=1;for(int i=1;i<maxn;i++){pw[i]=pw[i-1]*3%mod;fac[i]=fac[i-1]*i%mod;if(i>1) inv[i]=(mod-mod/i)*inv[mod%i]%mod;ifac[i]=ifac[i-1]*inv[i]%mod;}ll ans=0;ll tmp;// cerr<<C(1,1);for(int i=0;i<=k+m;i++){ll res=C(n+i-1,i)*pw[m+k-i]%mod;// cerr<<res;if(!i) tmp=1;else{tmp=tmp*2%mod;if(i>m) tmp=(tmp+mod-C(i-1,m))%mod;if(i>k) tmp=(tmp+mod-C(i-1,i-k-1))%mod; }// cerr<<tmp; ans=(ans+res*tmp)%mod;}printf("%lld\n",ans);return 0;
}
CodeForces - 1734F
容易发现这种构造方式得到的串的0/1取决于二进制表示下1的个数的奇偶性，奇数个就是1，偶数个就是0
那么问题转换为从0开始和从n开始的m个数，有多少二进制下1的个数的奇偶性不同，然后就数位dp即可
注意使用1<<w的时候，如果w是大于31记得改成1ll！！！！！！
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[62][2][2][2];
ll dp(ll n,ll m)
{m--;memset(f,0,sizeof(f));f[0][0][0][0]=1;for(int w=1;w<=61;w++){int v=0;if(n&(1ll<<w-1)) v=1;int one=0;if(m&(1ll<<w-1)) one=1;for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)for(int lim=0;lim<=1;lim++)for(int k=0;k<=1;k++){ int val=k^j^v; // 这一位是选择的0/1 和之前是否进位 以及相加的这一位是否是1int s=i^val^k; // 是否有奇数个int jw=(k+j+v>=2)?1:0;int limm=(k<one || (k==one && !lim))?0:1;f[w][s][jw][limm]+=f[w-1][i][j][lim];}}return f[61][1][0][0];
}
int main()
{freopen("a.in","r",stdin);freopen("a.out","w",stdout);int T; scanf("%d",&T);while(T--){ll n,m; scanf("%lld%lld",&n,&m);printf("%lld\n",dp(n,m));}return 0;
}
