AGC027E ABBreviate
19135 ワード
AGC 027E
文字列s s sがあり、「a」と「b」からなる.
次のことができます.は、1つの「aa」を「b」に変更する. は、1つの「bb」を「a」に変更する.
このように形成された本質的に異なる文字列の個数を聞く.
n ≤ 1 0 5 n\le 10^5 n≤105
正解まであと一歩.
ループに従って、まず、1つの文字列t t t tを列挙し、s s s操作で得られるか否かを判定する方法を考慮する.
まず、単一の文字がどの文字列で操作できるかを手に入れてみましょう.
もしこの文字がa a aであれば.それはc c c回操作され,c n t b≡−c(m o d 3)cnt_b\equiv -c\pmod 3 cntb≡−c(mod3).
まとめてみれば証明できる.
しかし、この条件は十分ではありません.そこで、この文字列は少なくとも1対の隣接する同じ文字を持っている.これを見つけてからで十分です.
判定問題に戻る.現在t i t_についてi tiは、[x,x+c][x,x+c][x,x+c][x,x+c]の区間に一致させる.では、c n t b[x,x+c]+c≡0(m o d 3)cnt_を満たすb[x,x+c]+c\equiv 0\pmod 3 cntb[x,x+c]+c≡0(mod3)
この判定方法をカウントするには,必ずこの判定の過程を一意にしなければならない.
推測してみてください.この条件を満たす最小のc c cを見つけて、過去に直接一致します.
この条件のみを考慮して、同じ条件を満たすcそこでそのままマッチングし続け、最後の特殊処理(残りの区間にマッチング)をします.
しかし、この結論だけを考慮すると、同じ隣接する文字があるという条件を満たさない可能性があります.これは最後の区間でしか現れません.前の区間はできるだけ小さい長さを選んでいるので、
そこで、まず特判は必ず完全に異なる文字が交互になっている場合、残りの場合は直接各文字に最小区間をマッチングし、このようにDPをします.
文字列s s sがあり、「a」と「b」からなる.
次のことができます.
このように形成された本質的に異なる文字列の個数を聞く.
n ≤ 1 0 5 n\le 10^5 n≤105
正解まであと一歩.
ループに従って、まず、1つの文字列t t t tを列挙し、s s s操作で得られるか否かを判定する方法を考慮する.
まず、単一の文字がどの文字列で操作できるかを手に入れてみましょう.
もしこの文字がa a aであれば.それはc c c回操作され,c n t b≡−c(m o d 3)cnt_b\equiv -c\pmod 3 cntb≡−c(mod3).
まとめてみれば証明できる.
しかし、この条件は十分ではありません.そこで、この文字列は少なくとも1対の隣接する同じ文字を持っている.これを見つけてからで十分です.
判定問題に戻る.現在t i t_についてi tiは、[x,x+c][x,x+c][x,x+c][x,x+c]の区間に一致させる.では、c n t b[x,x+c]+c≡0(m o d 3)cnt_を満たすb[x,x+c]+c\equiv 0\pmod 3 cntb[x,x+c]+c≡0(mod3)
この判定方法をカウントするには,必ずこの判定の過程を一意にしなければならない.
推測してみてください.この条件を満たす最小のc c cを見つけて、過去に直接一致します.
この条件のみを考慮して、同じ条件を満たすc
しかし、この結論だけを考慮すると、同じ隣接する文字があるという条件を満たさない可能性があります.これは最後の区間でしか現れません.前の区間はできるだけ小さい長さを選んでいるので、
aでababaのような形の区間をマッチングするよりも、aをマッチングするほうがいいです.だから最後の区間だけを考える必要があります.最後の区間がababaになると仮定し、その前に最も右側のaまたはbb(つまりa/bb+abab...ab+ababaになる)を見つけ、a a a b→a、b b b a b→b aabto a、bbabto bb aab→a、bbab→bbのため、abがいくつか消え、最後の影響は最後の区間がaしか残っていないことである.そこで、まず特判は必ず完全に異なる文字が交互になっている場合、残りの場合は直接各文字に最小区間をマッチングし、このようにDPをします.
using namespace std;
#include
");
return 0;
}
for (int i=1;i<=n;++i){
sum[i][0]=sum[i-1][0]+(s[i]==0);
sum[i][1]=sum[i-1][1]+(s[i]==1);
}
nxt[n+1][0][0]=nxt[n+1][0][1]=nxt[n+1][0][2]=
nxt[n+1][1][0]=nxt[n+1][1][1]=nxt[n+1][1][2]=n+1;
for (int i=n;i>=1;--i){
memcpy(nxt[i],nxt[i+1],sizeof nxt[i]);
nxt[i][0][(sum[i][0]+i)%3]=i;
nxt[i][1][(sum[i][1]+i)%3]=i;
}
f[0]=1;
ll ans=0;
for (int i=0;i<n;++i)
for (int c=0;c<2;++c){
int d=(sum[i][c^1]+i+1)%3,j=nxt[i+1][c^1][d];
if (j<=n)
(f[j]+=f[i])%=mo;
if ((sum[n][c^1]+n)%3==(sum[i][c^1]+i+1)%3)
(ans+=f[i])%=mo;
}
printf("%lld
",ans);
return 0;
}