T1.doughnut
Aloisia有很多很多甜甜圈。有一天，她在地上画了n+1个格子，想从第1个格子跳到第n+1个格子。规则是，Aloisia每到一个格子，都会放一个甜甜圈在里面。在第i个格子时，如果当前甜甜圈的数量是偶数，那么她会跳到第i+1个格子；否则她会跳到第Pi个格子（1≤Pi≤i)。若她到达了第n+1个格子，则立即结束。Aloisia想知道，她要跳多少次才能到达终点。答案对1000000007取模。
注意到向后跳只能跳一步，且Pi<i。
并且在到达一个新的格子时，前面的格子必定是偶数。
我们可以设 表示刚刚跳到第i个格子的步数。
那么跳到一个新的格子，肯定先会被弹飞到Pi。
可以用 表示从 回来的步数。
最后加上1表示从i跳到i+1。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
const int mod=1e9+7,N=1000009;
int p[N],n,ans[N];
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&p[i]);
for(int i=1;i<=n;i++)
{
ans[i+1]=(ans[i]+1+ans[i]-ans[p[i]]+1+mod)%mod;
if(ans[i+1]<0) ans[i+1]+=mod;
}
printf("%lld",ans[n+1]);
return 0;
}
没开longlong 100->20
T2.Pudding
Harry得到了一个字符串。
他想让Aloisia找出其中包含的(0w0)子序列有多少个。（注意0是数字，不是字母O）
为了提高难度，Harry提出他可以随时修改一个或一段字符，询问区间内的(0w0)子序列个数。
答案对4294967296取模。如果答对了的话，他就请Aloisia喝布丁奶茶。
请你帮帮Aloisia。
考虑维护(0w0)的每个子串，（,(0,0w,(0w0,(0w0),0w0),w0),0),)。
我们可以记录 表示从i到j的(0w0)的子串。
由于是区间操作，我们考虑线段树。
区间修改可以打标记覆盖。
重点在down和update。
下放标记时，把所有子节点的f置0，再赋值为标记点->区间长度。
build的时候同理。
update时，考虑跨区间的合并贡献。
类似区间dp的方式，能够贡献父亲的 。
(0w0)可以直接相加合并。
在query的时候，可以利用线段树从左到右遍历的性质。
记录ans为最终答案，同时在遍历过程中用新节点更新自己。
也就是所有新来的节点都能和之前的ans作为贡献。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define ls (x<<1)
#define rs (x<<1|1)
#define int long long
#define out puts("Debug")
const int N=50009,mod=4294967296;
char s[N],op[4];
int n,m,sum[N],ans[6][6];
struct Node
{
int f[8][8];
char tag;
} tr[N<<2];
inline void down(int x,int l,int r)
{
memset(tr[ls].f,0,sizeof tr[ls].f);
memset(tr[rs].f,0,sizeof tr[rs].f);
int mid=(l+r)>>1;
char c=tr[x].tag;
tr[ls].tag=tr[rs].tag=c;
if(c=='(') tr[ls].f[1][1]=mid-l+1;
if(c=='0') tr[ls].f[2][2]=tr[ls].f[4][4]=mid-l+1;
if(c=='w') tr[ls].f[3][3]=mid-l+1;
if(c==')') tr[ls].f[5][5]=mid-l+1;
if(c=='(') tr[rs].f[1][1]=r-mid;
if(c=='0') tr[rs].f[2][2]=tr[rs].f[4][4]=r-mid;
if(c=='w') tr[rs].f[3][3]=r-mid;
if(c==')') tr[rs].f[5][5]=r-mid;
tr[x].tag=0;
}
inline void update(int x)
{
// memset(tr[x].f,0,sizeof tr[x].f);
for(int i=1;i<=5;i++)
for(int j=i;j<=5;j++)
{
tr[x].f[i][j]=(tr[ls].f[i][j]+tr[rs].f[i][j])%mod;
for(int k=i;k<j;k++)
tr[x].f[i][j]=(tr[x].f[i][j]+tr[ls].f[i][k]*tr[rs].f[k+1][j]%mod)%mod;
}
}
inline void build(int x,int l,int r)
{
if(l==r)
{
if(s[l]=='(') tr[x].f[1][1]=1;
if(s[l]=='0') tr[x].f[2][2]=tr[x].f[4][4]=1;
if(s[l]=='w') tr[x].f[3][3]=1;
if(s[l]==')') tr[x].f[5][5]=1;
tr[x].tag=0;
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
update(x);
}
inline void change(int x,int l,int r,int L,int R,char c)
{
if(L<=l&&r<=R)
{
tr[x].tag=c;
memset(tr[x].f,0,sizeof tr[x].f);
if(c=='(') tr[x].f[1][1]=r-l+1;
if(c=='0') tr[x].f[2][2]=tr[x].f[4][4]=r-l+1;
if(c=='w') tr[x].f[3][3]=r-l+1;
if(c==')') tr[x].f[5][5]=r-l+1;
return;
}
if(tr[x].tag!=0) down(x,l,r);
int mid=(l+r)>>1;
if(L<=mid) change(ls,l,mid,L,R,c);
if(R>mid) change(rs,mid+1,r,L,R,c);
update(x);
}
inline void query(int x,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
int tmp[8][8];
for(int i=1;i<=5;i++)
for(int j=i;j<=5;j++)
{
tmp[i][j]=(ans[i][j]+tr[x].f[i][j])%mod;
for(int k=i;k<j;k++)
tmp[i][j]=(tmp[i][j]+ans[i][k]*tr[x].f[k+1][j]%mod)%mod;
}
for(int i=1;i<=5;i++)
for(int j=i;j<=5;j++)
ans[i][j]=tmp[i][j];//tmp辅助转移
return;
}
int mid=(l+r)>>1;
if(tr[x].tag!=0) down(x,l,r);
if(L<=mid) query(ls,l,mid,L,R);
if(R>mid) query(rs,mid+1,r,L,R);
return;
}
signed main()
{
scanf("%lld%lld",&n,&m);
scanf("%s",s+1);
build(1,1,n);
while(m--)
{
int x,y,z;
char ch;
scanf("%s",op+1);
scanf("%lld",&x);
if(op[1]=='A')
{
cin>>ch;
change(1,1,n,x,x,ch);
}
if(op[1]=='B')
{
scanf("%lld",&y);
cin>>ch;
change(1,1,n,x,y,ch);
}
if(op[1]=='C')
{
scanf("%lld",&y);
memset(ans,0,sizeof ans);
query(1,1,n,x,y);
printf("%lld\n",ans[1][5]);
}
}
return 0;
}
T3.Tiramisu
Aloisia买了一份提拉米苏。在吃之前，她决定思考一个问题来增加仪式感。她随机出一个01串和一个正整数k，然后询问自己m次：每次给出一个区间，可以进行若干次操作，选出区间内任一个长度为k的子区间取反，求最少多少次操作可以把区间全变成0。每次询问独立。
考虑对原序列异或差分，这样可以 进行区间减。
注意到，差分的操作端点，在 的意义下是相等的。
这样可以通过维护剩余系下每个数的操作次数的前缀和来计算。
无解的情况：区间中简化剩余系的次数总和为奇数，可以采用哈希 计算。
同时注意边界，维护d，c为b数组在原序列作为端点的次数。
记住差分是 。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll unsigned long long
const int N=2000009;
int n,k,m,a[N],b[N],sum[N],has[N],Has[N],c[N],d[N];
char s[N];
ll H=23333;
inline ll Hash()
{
return H^=H<<13,H^=H>>17,H^=H<<5;
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
scanf("%d%d%d",&n,&k,&m);
scanf("%s",s+1);
for(int i=0;i<k;i++) has[i]=Hash();
for(int i=1;i<=n;i++)
{
a[i]=s[i]-'0';
Has[i]=Has[i-1];
sum[i]=sum[i-1];
int group=i%k;
if(a[i]^a[i-1])
{
Has[i]^=has[group];
sum[i]-=b[group];
b[group]=i/k-b[group];
sum[i]+=b[group];
}
c[i]=b[(i+1)%k];
d[i]=b[i%k];
}
while(m--)
{
int l,r,ans=0;
bool y=true;
scanf("%d%d",&l,&r);
if(Has[l]^Has[r]^(a[l]*has[l%k])^(a[r]*has[(r+1)%k])) {puts("-1");continue;}
ans=sum[r]-sum[l];
if(a[r]) ans+=(r+1)/k-2*c[r];
if(a[l]) ans+=2*d[l]-l/k;
printf("%d\n",ans);
}
return 0;
}