2022牛客国庆集训派对day2 K-number 题解

方法一、

只考虑双零出现时的情况（思维）。

记前缀和对3取模为cur，cur的出现次数 cnt[cur] - 1即为cur越过3的次数。

如2121200 ( cur == 2 ) 有2次越过3，而121200、1200、00共贡献3次，可记 f[cur] 为cur的贡献。显然有 f[cur] = cnt[cur]。

cur == 0 的情况则需要特判， 如12300，f[cur] = 2，实际上3多贡献了一次，ans多加个1即可。

方法二、

考虑动规。

记 f[k][i] 为遍历到 s[k + 1] 时，固定右端的子段和对300取模等于 i 时，对答案的贡献，则有递推式  f[k + 1][(i * 10 + s[k + 1] - '0') % 300] += f[k][i] 。

 根据题意，我们每次只要取 f[k + 1][0] 即可。