P10034 题解（2023 激励计划评分 7）

· · 题解

P10034 「Cfz Round 3」Circle 题解

对于一个排列 p，我们连边 i\to p_i，则其构成了若干个环。f_{p,k}(i) 的含义即为：从 i 开始走 k 步到达的点。

题目限制可以等价描述为：使所有满足 S_i=\texttt{1} 的点都位于一个大小为 l 的因数的环上。

注意到如果存在方案，则必然存在一种使所有环的大小都为质数的方案（否则我们就可以把其中大小不是质数的环拆成若干个大小为质数的环而不影响合法性）。

考虑把 l 的所有 \le n 的质因数弄出来，其最多只有 15 个。环的大小只可能是这几种。

观察一下最终方案长啥样：其有 k 个节点在大小为 l 的质因数的环上，n-k 个节点单独成一环（这些节点中不应有 S_i=\texttt{1} 的点），有约束条件 c\le k\le n,k\ne n-1（其中 c 是 S 中 \texttt{1} 的数量）。

跑一遍完全背包即可判断可行性并得到一个可行的 k，记录一下转移路径即可还原出方案。

需要特判 l=0，代码有点难写。

#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

const int kN = 5e5 + 1, kC = 16;

int tt, n, ans[kN], d[kN], id[kN], c;
bool f[kC][kN], p[kC][kN], ip[kN];
vector<int> tp, pl;
string s;
LL l;

bool S() {
  pl.assign(1, 0);
  for (int i : tp) {
    if (i > n) {
      break;
    }
    if (l % i == 0) {
      pl.push_back(i);
    }
  }
  int m = pl.size() - 1;
  f[0][0] = 1;
  for (int i = 1; i <= m; ++i) {
    for (int j = 0; j <= n; ++j) {
      f[i][j] = 0;
      if (f[i - 1][j]) {
        f[i][j] = 1, p[i][j] = 0;
      } else if (j >= pl[i] && f[i][j - pl[i]]) {
        f[i][j] = 1, p[i][j] = 1;
      }
    }
  }
  int k = c;
  for (; k <= n && (k == n - 1 || !f[m][k]); ++k) {
  }
  if (k > n) {
    return 0;
  }
  int x = 1;
  for (int i = m; i >= 1; --i) {
    for (; p[i][k]; k -= pl[i]) {
      int _x = x;
      for (int j = pl[i] - 1; j--; ++x) {
        ans[x] = x + 1;
      }
      ans[x++] = _x;
    }
  }
  if (x < n) {
    ans[n] = x;
    for (; x < n; ++x) {
      ans[x] = x + 1;
    }
  }
  return 1;
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  for (int i = 2; i < kN; ++i) {
    if (!ip[i]) {
      tp.push_back(i);
    }
    for (int j : tp) {
      int k = i * j;
      if (k >= kN) {
        break;
      }
      ip[k] = 1;
      if (i % j == 0) {
        break;
      }
    }
  }
  for (cin >> tt; tt--;) {
    cin >> n >> l >> s;
    s = "#" + s;
    int m = 0;
    for (int i = 1; i <= n; ++i) {
      if (s[i] == '1') {
        id[d[i] = ++m] = i;
      }
    }
    c = m;
    if (!l) {
      for (int i = 2; i <= n; ++i) {
        cout << i << ' ';
      }
      cout << 1 << '\n';
      continue;
    }
    for (int i = 1; i <= n; ++i) {
      if (s[i] == '0') {
        id[d[i] = ++m] = i;
      }
    }
    if (S()) {
      for (int i = 1; i <= n; ++i) {
        cout << id[ans[d[i]]] << ' ';
      }
    } else {
      cout << -1;
    }
    cout << '\n';
  }
  return 0;
}