Tony102's Blog - 线性筛
type: channel
link: https://tony102.com/index.php/tag/%E7%BA%BF%E6%80%A7%E7%AD%9B/
items: CF895C Square Subsets
items: Luogu6280 [USACO20OPEN]Exercise G

CF895C Square Subsets
type: item
date: 2021-08-25T21:58:00+08:00
description: LinkSol一个完全平方数分解质因数之后每个质因子都出现偶数次一看 $a_i \leq 70$，质因子特别少，直接变成水题。用一个 bitset 之类的二进制数的第 $i$ 位表示第 $i$ 个质因子是否出现过。插到线性基中，两个数相乘就是线性基中的元素异或起来。最终的答案就是记线性基中的数 $cnt$，$ans = 2^{n - cnt} - 1$Code#include <bits/stdc++.h> using namespace std; typedef long long LL; const int SIZE = 1e5 + 5; const LL mod = 1e9 + 7; int n, tot; int isnPri[SIZE], pri[SIZE], bit[SIZE], a[SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; void insert(int x) { for (int i = 19; i; -- i) { if ((1 << i) & x) { if (!bit[i]) { bit[i] = x; break; } x ^= bit[i]; } } } LL qPow(LL a, LL b) { LL ans = 1ll; for ( ; b; b >>= 1, a = a * a % mod) { if (b & 1) ans = ans * a % mod; } return ans % mod; } int main() { // freopen("code.in", "r", stdin); n = read(); int mx = 0; for (int i = 1; i <= n; ++ i) a[i] = read(), mx = std::max(mx, a[i]); isnPri[1] = 1; for (int i = 2; i <= mx; ++ i) { if (!isnPri[i]) pri[++ tot] = i; for (int j = 1; j <= tot && i * pri[j] <= mx; ++ j) { isnPri[i * pri[j]] = 1; if (i % pri[j] == 0) break; } } for (int i = 1; i <= n; ++ i) { int x = a[i], num = 0, opt = 0; for (int j = 1; j <= tot; ++ j) { if (x % pri[j]) continue; opt = 0; for ( ; !(x % pri[j]); opt ^= 1, x /= pri[j]); num |= (opt << j); } insert(num); } int cnt = 0; for (int i = 1; i <= 19; ++ i) { if (bit[i]) ++ cnt; } printf("%lld\n", qPow(2ll, n - cnt) - 1ll); return 0; }

Luogu6280 [USACO20OPEN]Exercise G
type: item
date: 2021-05-28T09:28:00+08:00
description: LinkSol感觉题面写的不是很清楚,原以为是翻译的问题,结果发现是英文原题面就写的很垃圾.给 Benjamin Qi 倒一杯卡布奇诺个人理解困难的地方在于样例解释 $0$ 步的位置, 但是反过来一想如果按照我的想法(初始排列和 $A$ 一模一样) 的话那么答案就都是 $0$ 了.首先可以猜一波东西, 要确定两个排列,一个是原排列(也就是初始位置的排列) 和 $A$ 排列(位置每次从 $i$ 变到 $A_i$) 是比较麻烦的. 先猜想应该答案跟原排列没有什么关系, 测试一下发现是对的.也就是说, 影响答案的只有这个 $A$ 排列.再来观察 $A$ 排列每次是怎么影响每一个数的位置的.比如说现在有原排列 1 2 3 4 5 和 $A$ 排列 2 3 4 5 1. 你可以发现每一个位置的改变就像一个环.每一个数位置都会在这个环中持续地改变.那么要使这个排列变回原来的排列,应当是变化中所有环有一次正好同时变完一个周期时就回到了原排列.形式话地,我们记变化过程中所有环的长度为 $c_i$ ,那么首先 $\sum c_i = n$ . 再者,有 $lcm_{c_i} = k$ 解释一下为什么是 $lcm_{c_i}$ . 最简单形式的 $k$ 肯定可以被表示为 $k = \prod c_i$ , 假如 $\exist\ gcd(c_i, c_j) > 1$ , 那么 $k \div gcd(c_i,c_j)$ 肯定可以变得更小, 也就是有更小的 $c_i$ 满足. 所以就是 $lcm_{c_i}$根据算数基本定理, $lcm$ 就是取唯一分解后相同质数的最高次幂的乘积.现在就是要对 $n$ 进行分解,计算有多少中这样的分解.(这就是P4161) 并且同时计算一下和.那么设 $f_{i,j}$ 表示前 $i$ 个质数和为 $j$ 的答案就可以了吧.转移的时候把当先选中的质数给它乘上去就可以了.肉眼可见 $f_i$ 的状态只会由 $f_{i-1}$ 转移过来.直接滚掉一维就可以了吧Code#include <bits/stdc++.h> #define int long long using namespace std; const int SIZE = 5e4 + 5; int n, mod; int f[SIZE], isPrime[SIZE], p[SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; signed main() { // freopen("code.in", "r", stdin); int tot = 0; n = read(), mod = read(), isPrime[1] = 1; for (int i = 2; i <= n; ++ i) { if (!isPrime[i]) p[++ tot] = i; for (int j = 1; i * p[j] <= n; ++ j) { isPrime[i * p[j]] = 1; if (i % p[j] == 0) break; } } f[0] = 1; for (int i = 1; i <= tot; ++ i) { for (int j = n; j >= p[i]; -- j) { for (int k = p[i]; k <= j; k *= p[i]) f[j] = (f[j] + f[j - k] * k % mod) % mod; } } int ans = 0; for (int i = 0; i <= n; ++ i) ans = (ans + f[i]) % mod; printf("%lld\n", ans % mod); return 0; }