10/21
20:49
OI

今 日 C S P 模 拟 题 [FFT][生成函数]

题意:

进行石头剪刀布游戏,给出n个长度为m的串,内容为P,R,SPRRSSP。定义一次战斗,为两个串每个位置比较,分别计算胜利数。两个串可以放在一个集合内,当且仅当任意循环移位一个串并战斗,两个人胜场数都不变。求有多少子集是合法的。n \leq 200000, m \leq 18

题解:

真实的联赛模拟题就是这么朴实无华

考虑三次单位根。比较A,B两串,令R,S,P的权分别为w_3^0,w_3^1,w_3^1w_3^{-0},w_3^{-1},w_3^{-2},那么两个字母的值乘起来,就可以判断输赢。

分别记为f(x),g(x),那么对于第k次输赢,可以得到这个式子:

\sum_{i-j=k}f(i)g(j)

反转g,考虑生成函数。

f(x) = \sum_{i=0}^{m-1} v_a(i) x^i

g(x) = \sum_{i=0}^{m-1} v_b(m-i-1) x^i

做一个循环卷积,就可以得到关于输赢的多项式了。显然如果是可行的,每一项都相等。

循环卷积定理:求循环卷积DFT乘起来就可以。其实很简单,单位根w_n就是模n的。

考虑IDFT的过程其实也是在求点值,如果IDFT后各项相等,那么点值式的每一项都必须是0,即f,g的点值表达式每一项都有a_ib_i=0

gf翻转并求复共轭得到的,显然,如果两式满足要求,f_1,f_2的点值表达式每一项都有a_ib_i=0

观察m的范围,发现很小,暴力做DFT就可以。

然后做一个DP。记录每条字符串DFT后,哪些位不是0。如果一堆串可以放在一起,那么它们必无交集。令f_s表示选中集合或和为sO(3^m)枚举子集DP。显然本题点值表示的第0个数可以不考虑,m降至17,轻松通过。

不乱码的代码点这里

#include <bits/stdc++.h>

const int N = 2e5 + 233, M = 20, S = 17, P = 998244353;
const double PI = std::acos(-1), eps = 1e-9;

int n, m, cnt[(1 << S) + 5];
long long dp[(1 << S) + 5], ans;
char str[M];

inline double dcmp(double x) {
  return std::fabs(x) < eps ? 0 : x > 0 ? 1 : -1;
}

struct complex {
  double x, y;
};

complex operator+(const complex &a, const complex &b) {
  return { a.x + b.x, a.y + b.y };
}

complex operator*(const complex &a, const complex &b) {
  return { a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x };
}

complex f[M], g[M];

inline long long fpow(long long x, int y) {
  long long ret = 1;
  for ( ; y; y >>= 1, x = x * x % P)
    if (y & 1)
      ret = ret * x % P;
  return ret;
}

int main() {
  scanf("%d %d", &n, &m);

  while (n--) {
    scanf("%s", str);

    for (int i = 0; i < M; ++i)
      f[i] = g[i] = { 0, 0 };

    for (int i = 0; i < m; ++i) {
      if (str[i] == 'R')
        f[i] = { std::cos(-2 * 0 * PI / 3), std::sin(-2 * 0 * PI / 3) };
      else if (str[i] == 'S')
        f[i] = { std::cos(-2 * 1 * PI / 3), std::sin(-2 * 1 * PI / 3) };
      else
        f[i] = { std::cos(-2 * 2 * PI / 3), std::sin(-2 * 2 * PI / 3) };
    }

    for (int i = 0; i < m; ++i) {
      complex T = { std::cos(-2 * i * PI / m), std::sin(-2 * i * PI / m) },
        w = { 1, 0 };
      for (int j = 0; j < m; ++j, w = w * T)
        g[i] = g[i] + w * f[j];
    }

    int s = 0;
    for (int i = 1; i < m; ++i)
      if (dcmp(g[i].x) != 0 || dcmp(g[i].y) != 0)
        s |= 1 << (i - 1);
    ++cnt[s];
  }


  dp[0] = 1;
  for (int s1 = 1; s1 < 1 << (m - 1); ++s1)
    if (cnt[s1] > 0) {
      for (int s = ((1 << (m - 1)) - 1) ^ s1, s2 = s; s2; s2 = (s2 - 1) & s)
        dp[s1 | s2] = (dp[s1 | s2] + dp[s2] * cnt[s1]) % P;
      dp[s1] = (dp[s1] + dp[0] * cnt[s1]) % P;
    }

  for (int s = 0; s < 1 << (m - 1); ++s)
    ans = (ans + dp[s]) % P;

  ans = ans * fpow(2, cnt[0]) % P;

  printf("%lld\n", ans);
  return 0;
}