给定一个序列 \(a\)，长度为 \(n\)。试求有多少 \(1\) 到 \(n\) 的排列 \(p_i\)，满足对于任意的 \(2\le i\le n\) 有 \(a_{p_{i-1}}\times a_{p_i}\) 不为完全平方数，答案对 \(10^9+7\) 取模。
\(n \le 300,a_i \le 10^9\).
连续……不是很连续 段dp。
首先考虑什么时候有限制“\(a_{p_{i-1}}\times a_{p_i}\) 为完全平方数”。
我们设 \(a^2 = b\times c,b = p\times x^2, c =q\times y^2\)，其中 \(p,q\) 无平方因子。则有 $ p\times q$ = \left(\frac a {xy}\right)^2$。由于 \(p,q\) 无平方因子，因此若 \(p\times q\) 为完全平方数，则唯一的可能就是 \(p=q\)。
因此我们预先筛出 \(\le \sqrt n\) 的质数，把每个数的平方因子除去，问题就转化成了不能有相邻两个数相同的排列数量。
考虑一个插入dp。
枚举当前插入的数是哪个数，再枚举插入的位置，就可以开始分类讨论了。
- 插入数和一侧的数相同
- 插入数和两侧的数相同
- 插入数和两侧的数都不同，两侧的数彼此不同
- 插入数和两侧的数都不同，两侧的数彼此相同
然后开始设dp数组。
设 \(f[i][j][k]\) 为插入了 \(i\) 个数，已经有 \(j\) 对相同的数，\(k\) 对是由和当前插入数相同的数产生的的方案数。
设当前数插入前已经插入了 \(x\) 个和当前数相同的数，开始转移：
- \(f[i][j][k] = f[i[j][k] + f[i-1][j-1][k-1] \times (2(x - 2(k-1)) + 2(k-1))\)
- \(f[i][j][k] = f[i[j][k] + f[i-1][j-1][k-1] \times (k-1)\)
- \(f[i][j][k] = f[i[j][k] + f[i-1][j][k] \times (i-(2x-k)-(j-k))\)
- \(f[i][j][k] = f[i[j][k] + f[i-1][j+1][k] \times (j-k+1)\)
然后转移就完了。记得压一维，但不压似乎也没问题。
时间复杂度 \(O(n^3)\)。
code
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define rep(i, a, b) for (register int(i) = (a); (i) <= (b); ++(i))
#define pre(i, a, b) for (register int(i) = (a); (i) >= (b); --(i))
const int N = 3e2 + 10;
int n, a[N], tmp, mod = 1e9 + 7, f[2][N][N];
int prime[1000005], cnt;
bool vis[1000005];
void sieve(int bnd) {
rep(i,2,bnd) {
if (!vis[i]) prime[++cnt] = i;
rep(j,1,cnt) {
if (i * prime[j] > bnd) break;
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n; rep(i,1,n) cin >> a[i], tmp = max(tmp, a[i]);
sieve(sqrt(tmp) + 10);
rep(i,1,cnt) prime[i] = prime[i] * prime[i];
rep(i,1,n) rep(j,1,cnt) while (a[i] % prime[j] == 0) a[i] /= prime[j];
sort(a+1, a+1+n);
f[0][0][0] = 1; tmp = 0;
rep(i,1,n) {
int ptr = i & 1, ztr = ptr ^ 1;
memset(f[ptr], 0, sizeof f[ptr]);
if (a[i] != a[i-1]) {
rep(j,0,i) {
rep(k,1,tmp) {
f[ztr][j][0] = (f[ztr][j][k] + f[ztr][j][0]) % mod;
f[ztr][j][k] = 0;
}
}
tmp = 0;
}
rep(j,0,i) rep(k,0,min(tmp,j)) {
if (j > 0 and k > 0) f[ptr][j][k] = (f[ptr][j][k] + 1ll * f[ztr][j-1][k-1] * ((tmp << 1) - k + 1)) % mod;
f[ptr][j][k] = (f[ptr][j][k] + 1ll * f[ztr][j+1][k] * (j + 1 - k)) % mod;
f[ptr][j][k] = (f[ptr][j][k] + 1ll * f[ztr][j][k] * (i - ((tmp << 1) - k) - (j - k))) % mod;
} tmp++;
} cout << f[n & 1][0][0] << endl;
}
[能不能再给力一点啊？]
题面相同。
\(n \le 5000,a_i \le 10^9\).
容斥题。
为方便，设 \(s_i\) 为除去平方因子后第 \(i\) 大的数出现了多少次。
为方便，首先进行无标号计数，最后乘入 \(\prod (s_i!)\) 即可。
于是问题转化成了有颜色无标号小球排列计数，需要相邻小球颜色不同。这就比较的典。
我们考虑一个容斥。首先设有 \(b\) 段长度大于 \(1\) 的相同颜色段，然后我们把这些段缩成一个小球。设第 \(i\) 种颜色被缩成的小球数是 \(t_i\)（\(\sum t_i = b\)），则有
\((n-b)!\) 是当前缩完后的序列的总可能性，然后我们得除去那些已经在一个连续段内的排列情况。这是分子。分母考虑对连续段做一下插板法使得计数的序列都满足不会再缩起来的情况。
先不考虑 \((n-b)!\)，最后得到答案时乘进去就行。套路地设 \(f_{i,j}\) 为前 \(i\) 个数值，\(b=j\) 时的答案。定义 \(n < m\) 时 \(\binom{n}{m} =0\)，\(n < 0\) 时 \(n! = 0\)，我们有转移
\[f_{i,j} = \sum_{k=0}^j f_{i-1,j-k} \times \frac{\binom{s_i-1}{k}}{(s_i - k)!} \]记得得到答案时乘进去该乘的阶乘。
code
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define rep(i, a, b) for (register int(i) = (a); (i) <= (b); ++(i))
#define pre(i, a, b) for (register int(i) = (a); (i) >= (b); --(i))
const int N = 300 + 10;
int n, ptr, ztr, a[N], s[N], tmp, jc[N], inv[N], mod = 1e9 + 7, f[2][N];
int prime[1000005], cnt;
bool vis[1000005];
void sieve(int bnd) {
rep(i,2,bnd) {
if (!vis[i]) prime[++cnt] = i;
rep(j,1,cnt) {
if (i * prime[j] > bnd) break;
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
int qp(int a, int b) {
int ret = 1;
while (b) {
if (b & 1) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
} return ret;
}
int C(int n, int m) { if (n < m) return 0; return 1ll * jc[n] * inv[m] % mod * inv[n-m] % mod; }
int main() {
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n; rep(i,1,n) cin >> a[i], tmp = max(tmp, a[i]);
sieve(sqrt(tmp) + 10);
rep(i,1,cnt) prime[i] = prime[i] * prime[i];
rep(i,1,n) rep(j,1,cnt) while (a[i] % prime[j] == 0) a[i] /= prime[j];
sort(a+1, a+1+n);
tmp = 0; cnt = 0;
jc[0] = inv[0] = 1;
rep(i,1,n) jc[i] = 1ll * jc[i-1] * i % mod;
inv[n] = qp(jc[n], mod - 2);
pre(i,n-1,1) inv[i] = 1ll * inv[i+1] * (i+1) % mod;
rep(i,1,n) if (a[i] != a[i-1]) ++ s[++cnt]; else ++ s[cnt];
f[0][0] = 1;
rep(i,1,cnt) {
tmp += s[i] - 1;
ptr = i & 1, ztr = ptr ^ 1;
memset(f[ptr], 0, (tmp + 1) << 2);
rep(j,0,tmp) {
rep(k,0,min(s[i], j)) {
f[ptr][j] = (f[ptr][j] + 1ll * f[ztr][j-k] * C(s[i] - 1, k) % mod * inv[s[i] - k]) % mod;
}
}
}
int ans = 0; ptr = cnt & 1;
rep(i,0,tmp)
if (i & 1) ans = (ans + 1ll * (mod - 1) * jc[n - i] % mod * f[ptr][i]) % mod;
else ans = (ans + 1ll * jc[n - i] % mod * f[ptr][i]) % mod;
rep(i,1,cnt) ans = 1ll * ans * jc[s[i]] % mod;
cout << ans << endl;
}
[能不能再给力一点啊？]
题面相同。
\(n \le 10^5,a_i \le 10^9\).
考虑构造两个生成函数 \(F_k\) 与 \(G_k\)。
\[F_k(x) = \sum_{i=0}f_{k,i} x^i \]\[G_k(x) = \sum_{i=0}^{s_k} \frac{\binom{s_k-1}{i}}{(s_k - i)!}x^i \]则我们能发现 \(F_k = F_{k-1} \times G_k\)。而 \(F_0 = 1\)。
则我们有答案即为
通过分治NTT得到最右边那个多项式的系数，然后算出来就行了。注意最后乘进去一个阶乘。
[代码还没有，等我学会任意模数分治NTT再说]
标签：prime,tmp,社论,int,rep,cnt,times,22.10 From： https://www.cnblogs.com/joke3579/p/editorial221009.html