【弱省胡策】Round #6 String 解题报告

时间：2023-02-10 15:19:22

感觉这个题好神啊。

首先我们只管 $a = b$ 的情况，那么我们自然就可以把这个串对 $a$ 取模，然后用 KMP 求出能弄出几个其他的 B 串。

具体就是把串先倍长，然后倒过来，然后求 $Next$ 数组，然后从 $2n$ 开始沿着 $Next[]$ 跳，直到跳到 $\le n$ 的时候停止，看哪些位置被跳到了，哪些位置就是合法的。

问题是现在 $a \neq b$ 怎么办。。？

我猜啊，我们可以求出限制是 $a$ 的倍数时，哪些 B 串是合法的，再求出限制是 $b$ 的倍数是，哪些是合法的。

然后只要在一种情况下合法，那么这个 B 串就可以写进来。

至于为什么，我也不知道。反正和暴力拍了拍一直没出错。

然后就做完啦~~~

时间空间复杂度均为 $O(n)$。

 #include <cstdio>

 using namespace std;

 #define N 2000000 + 5

 int n, a, b, A[N], _A[N], Next[N];

 bool Flag[N];

 inline int getint()

 {

     char ch = '\n';

     for (; ch != '-' && (ch > '' || ch < ''); ch = getchar()) ;

     int f = ch == '-' ? - : ;

     int res = ch == '-' ?  : ch - '';

     for (ch = getchar(); ch >= '' && ch <= ''; ch = getchar())

         res = (res << ) + (res << ) + ch - '';

     return res * f;

 }

 inline void Work(int x)

 {

     for (int i = ; i <= n; i ++)

         _A[i] = A[n - i + ] % x;

     for (int i = ; i <= n; i ++)

         _A[i + n] = _A[i];

     int k = , j = ;

     Next[] = ;

     while (j <= (n << ))

     {

         if (!k || _A[k] == _A[j])

             Next[++ j] = ++ k;

         else k = Next[k];

     }

     for (int x = n <<  | ; x > n + ; x = Next[x])

         Flag[(n +  << ) - x] = ;

 }

 inline void Solve()

 {

     n = getint(), a = getint(), b = getint();

     for (int i = ; i <= n; i ++)

     {

         A[i] = getint();

         Flag[i] = ;

     }

     Work(a), Work(b);

     int ans = ;

     for (int i = ; i <= n; i ++)

         if (Flag[i]) ans ++;

     if (ans == ) ans = ;

     printf("%d\n", ans);

 }

 int main()

 {

     for (int _ = getint(); _; _ --)

         Solve();

     return ;

 }

String_Gromah

相关文章