你的 k 和 t 有什么区别吗？
by zenglu @ 2022-07-06 17:28:50
好像计数有错吧。$z$和$y$都可以重复用的。
by sleepy_coconut_sheep @ 2022-07-06 18:16:29
而且应该会超时吧
by sleepy_coconut_sheep @ 2022-07-06 18:20:01
@[Orange1015](/user/565378)
首先，我理解dfs(k,t)表示s匹配到了t，f匹配到了k，所以应该是$f[k]$，而不是$f[t]$
第13行有问题
> if(s[i]!=f[t]) continue;
其次，这个方法是$O(n^3)$的，应该过不了所有数据。
by barbatoss @ 2022-07-06 18:21:37
个人认为可以记下 $z$ 的数量，遇到 $y$ 时加上前面 $z$ 的组合数目。~~我先去试一试（逃~~
by sleepy_coconut_sheep @ 2022-07-06 18:23:17
@[barbatoss](/user/104155) Orz
by sleepy_coconut_sheep @ 2022-07-06 18:24:01
@[Fat_Panda](/user/623442) 这个是最好写的方法，应该是对的，我想到的是$dp$，$f_{i,0/1/2}$表示，s匹配到前$i$个，分别匹配了"z","zz","zzy"的数量
by barbatoss @ 2022-07-06 18:26:08
```cpp
#include<cstdio>
using namespace std;
long long ans, t;
char ch;
signed main()
{
while (scanf (" %c", &ch) != EOF)
if (ch == 'z')
t++;
else if (ch == 'y')
ans += t * (t - 1) / 2;
printf ("%lld", ans);
return 0;
}
```
by sleepy_coconut_sheep @ 2022-07-06 18:27:38
@[barbatoss](/user/104155) 应该也可以吧。~~我试试~~
by sleepy_coconut_sheep @ 2022-07-06 18:29:39
```cpp
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 1e6 + 5;
char s[N];
long long f[3];
signed main()
{
scanf ("%s", s);
int len = strlen(s);
for (int i = 0;i < len; i++)
if (s[i] == 'z')
{
f[1] += f[0];
f[0]++;
}
else if (s[i] == 'y')
f[2] += f[1];
printf ("%lld", f[2]);
return 0;
}
```
by sleepy_coconut_sheep @ 2022-07-06 18:34:27