CF1466H Finding satisfactory solutions

这题厉害了！

先考虑已知 \(b\) 如何求合法的 \(a\)。由于是排列，就想和置换环扯上关系。考虑将 \(i\) 与 \(i\) 最喜欢的物品连边，形成内向基环森林，直觉告诉我们这个环一定要直接选，事实也就是如此，否则选择 \(S = circle\) 即可满足不合法条件。这样，每次确定一个环并删去，那么就会形成合法的 \(a\)。

现在变成有 \(a\) 计数 \(b\) 了。把置换环抠出来，令环上点为白边，每个点向比环上点更喜欢的点连黑边，那么合法等价于不存在包含黑边的环。

由于 \(n\) 很小，考虑状压 DP。转移考虑一层层连黑边，每次枚举新加进来的环，容斥一下有

\[f_S = \sum_{T} (-1)^{|T| + 1} f_{S - T} w_{S - T, T}
\]

其中 \(w_{S,T}\) 表示由 \(T\) 向 \(S\) 连黑边的方案数，显然可以先算出一个点连向 \(S\) 的方案数然后乘起来。

枚举向 \(S\) 连了多少条边，有

\[w_{S, x} = \sum_{i=1}^{|S|} \binom{|S|}{i} i! (n-i-1)!
\]

这个可以 \(O(n^2)\) 预处理。复杂度瓶颈就在于 DP。观察一下状态数，发现好像比较小，实际上最大为 \(1440\)。假设状态数为 \(S\)，随便实现一下可以做到 \(O(nS^2)\)，很轻松就能通过。

#include <cstdio>

namespace IO {

  #define isdigit(x) (x >= '0' && x <= '9')

  template<typename T>

  inline void read(T &x) {

    x = 0; char ch = getchar(); int f = 0;

    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;

    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';

    if(f) x = -x;

  }

  template<typename T>

  inline void write(T x) {

    if(x < 0) putchar('-'), x = -x;

    if(x > 9) write(x / 10);

    putchar(x % 10 + '0');

  }

  #undef isdigit

}

using namespace IO;

const int N = 110;

const int M = 1500;

int n, a[N], vis[N], cnt[N];

int w[N][N], binom[N][N], fac[N];

int f[M], sz[M], m, subs;

const int P = 1e9 + 7;

inline void add(int &x, int y) {if((x += y) >= P) x -= P;}

inline void sub(int &x, int y) {if((x -= y) < 0) x += P;}

inline void encode(int *num, int &x) {

  x = 0;

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

    x = x * (cnt[i] + 1) + num[i];

}

inline void decode(int x, int *num) {

  for(int i = n; i >= 1; --i)

    num[i] = x % (cnt[i] + 1), x /= (cnt[i] + 1);

}

void prework() {

  encode(cnt, m);

  fac[0] = 1;

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

    fac[i] = 1ll * fac[i - 1] * i % P;

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

    binom[i][0] = 1;

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

    for(int j = 1; j <= n; ++j)

      add(binom[i][j] = binom[i - 1][j], binom[i - 1][j - 1]);

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

    w[i][0] = 1;

    for(int j = 0; j <= i; ++j)

      add(w[i][1], 1ll * binom[i][j] * fac[j] % P * fac[n - j - 1] % P);

    for(int j = 2; j <= n; ++j)

      w[i][j] = 1ll * w[i][j - 1] * w[i][1] % P;

  }

  static int s[N];

  for(int i = 1; i <= m; ++i) {

    decode(i, s);

    int cnt = 0;

    for(int j = 1; j <= n; ++j)

      cnt += s[j] * j;

    sz[i] = cnt;

  }

}

int main() {

  read(n);

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

    read(a[i]);

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

    if(vis[i]) continue;

    int x = i, siz = 0;

    do {

      vis[x] = 1, ++siz;

      x = a[x];

    }while(x != i);

    ++cnt[siz];

  }

  prework();

  static int s[N], t[N];

  f[0] = 1;

  for(int i = 0; i <= m; ++i) {

    decode(i, s);

    for(int j = 1; j <= i; ++j) {

      decode(j, t);

      int flag = 0;

      int mul = 1, sum = 0;

      for(int k = 1; k <= n; ++k) {

        if(t[k] > s[k]) flag = 1;

        mul = mul * binom[s[k]][t[k]] % P;

        sum += t[k];

      }

      if(flag) continue;

      if(sum & 1) add(f[i], 1ll * mul * f[i - j] % P * w[sz[i] - sz[j]][sz[j]] % P);

      else sub(f[i], 1ll * mul * f[i - j] % P * w[sz[i] - sz[j]][sz[j]] % P);

    }

  }

  printf("%d\n",f[m]);

  return 0;

}

巴特西

CF1466H Finding satisfactory solutions

CF1466H Finding satisfactory solutions

最新文章

热门文章