Newton 恒等式
stripe_python · · 算法·理论
设现有
取初等对称多项式
通俗来说,
Newton 恒等式指出
下面给出组合意义证明。
将右侧式子化为
其中
我们构造若干配对,将贡献尽可能抵消。
-
若
j \in S ,配对(i,S,j) \leftrightarrow (i+1,S\setminus \{j\},j) 。权值a_j^i\prod_{k \in S} a_k=a_j^{i+1}\prod_{k \in S\setminus \{j\}} a_k 而符号
(-1)^{i-1}+(-1)^{i}=0 成对抵消。 -
若
j \notin S \land i\ge 2 ,配对(i,S,j) \leftrightarrow (i-1, S \cup\{j\},j) 。同理权值不变,符号抵消。
当且仅当
任取
得证。
一个 trivial 的应用是,维护
-
$$ 2\sum_{i<j} a_ia_j=\left(\sum_{i=1}^n a_i\right)^2-\sum_{i=1}^n a_i^2 $$ -
$$ 3\sum_{i<j<k} a_ia_ja_k=\left(e_2-\sum_{i=1}^n a_i^2\right)\sum_{i=1}^n a_i+\sum_{i=1}^n a_i^3 $$
一般地,已知
使用分治 NTT 可做到
下面给出一个神奇的应用,做法来自 xueshengyi 大神。
维护
n 个集合S_1\sim S_n ,支持q 次操作:
给定
l,r,x ,对i \in [l,r] 令S_i \gets S_i \cup \{x\} 。保证操作前x 不被包含。给定
l,r,x ,对i \in [l,r] 令S_i \gets S_i \setminus\{x\} 。保证操作前x 被包含。给定
u,v ,判定S_u 与S_v 的包含关系,保证\textcolor{red}{\left||S_u|-|S_v|\right| \le k} 。具体地,你需要判断
S_u =S_v 或S_u \subsetneq S_v 或S_v \subsetneq S_u 或其他。
取大质数
令
上式给出
不妨设
必然是
实际检验时,我们声称
开
const int N = 2e6 + 5;
int n, q, k;
umap<i64, mint> mp;
mint h(i64 x) {
if (mp.find(x) != mp.end()) return mp[x];
return mp[x] = rand64();
}
template <class mint>
struct BIT {
mint *a;
void init() {
a = new mint[n + 5];
memset(a, 0, sizeof(mint) * (n+5));
}
void add(int x, mint c) {
for (; x <= n; x += lowbit(x)) a[x] += c;
}
void add(int l, int r, mint c) {
add(l, c), add(r+1, -c);
}
mint ask(int x) {
mint res = 0;
for (; x >= 1; x -= lowbit(x)) res += a[x];
return res;
}
};
BIT<int> S;
BIT<mint> T[32];
mint inv[40], p[40], e[40];
bool check(int x, int y, int n) {
// y is subset of x
for (int i = 1; i <= n+1; i++)
p[i] = T[i].ask(x) - T[i].ask(y);
fill(e + 1, e + n + 2, 0), e[0] = 1;
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= k; i++) {
if (i & 1) e[k] += e[k-i] * p[i];
else e[k] -= e[k-i] * p[i];
}
e[k] *= inv[k];
}
mint res = 0;
for (int i = 1; i <= n; i++)
if (i & 1) res += e[i] * p[n+1-i];
else res -= e[i] * p[n+1-i];
return res == p[n+1];
}
void _main() {
cin >> n >> q >> k; S.init();
for (int i = 1; i <= k+1; i++) inv[i] = ~mint(i), T[i].init();
for (i64 op, l, r, x, y; q--; ) {
cin >> op;
if (op == 1) {
cin >> l >> r >> x;
S.add(l, r, 1);
mint h0 = h(x), hi = h0;
for (int i = 1; i <= k+1; i++, hi *= h0)
T[i].add(l, r, hi);
} else if (op == 2) {
cin >> l >> r >> x;
S.add(l, r, -1);
mint h0 = h(x), hi = h0;
for (int i = 1; i <= k+1; i++, hi *= h0)
T[i].add(l, r, -hi);
} else {
cin >> x >> y;
int w = 4, s1 = S.ask(x), s2 = S.ask(y);
if (s1 == s2 && T[1].ask(x) == T[1].ask(y)) w = 3;
else if (s1 < s2 && check(y, x, s2 - s1)) w = 2;
else if (s1 > s2 && check(x, y, s1 - s2)) w = 1;
cout << w << '\n';
}
}
}