251213 数学专题
称一个集合序列 \(S_{1\sim n}\) 是合法的，当且仅当 \(\forall i,S_i\in [1,m]\) 且 \(\forall i\in[1,n-1]\)，\(|S_i\oplus S_{i+1}|=1\)。称该集合序列的价值为 \(\prod_{i=1}^{m}\sum_{j=1}^{n}[i\in S_j]\)。问所有合法序列的价值和。
如果我们钦定了 \(i\in [1,n-1]\) 的 \(D_i=S_i\oplus S_{i+1}\)，那么整个序列就只和 \(S_1\) 有关了。发现对于一个数字 \(i\)，\(i\in S_1\) 和 \(i\notin S_1\) 两种情况下 \(i\) 在整个序列中的的出现次数加起来等于 \(n\)。因此答案为 \(n^mm^{n-1}\)。
简单拆贡献即可。
将贡献拆到：对每个 \(i\) 求出 \(c_i\) 表示操作后 \(\ge i\) 的数字有 \(c_i\) 个。然后发现 \(c_i\) 一旦到达 \(n-x\) 就不会再改变了，然后枚举这些操作一共有多少个令 \(c_i\) 加一，然后贡献形如一个组合数乘以两个幂。
拆幂：
\[
f^k(S)=\sum_{i=0}^{k}\begin{Bmatrix}k\\i\end{Bmatrix}\binom{f(S)}{i}i!
\]
对每个子树求出 \(g_i=\sum_{S}{\binom{f(S)}{i}}\)，转移形如一个卷积，但可以使用树上背包分析到 \(O(nk)\)。
首先容斥，然后用一个组合数钦定 \(k\) 个极大值的坐标，然后再用一个阶乘钦定 \(k\) 个极大值的相对大小关系。然后对于其它每个非极大值坐标，找到控制它的值最小的极大值，然后形如一个树的拓扑序计数。
考虑 \(k=1\) 怎么做。在钦定 \(a\) 构成的集合后，注意到
\[
\sum_{P\in perm(1\sim n)}\frac{1}{\prod_{i}\sum_{j=1}^ia_{p(j)}}=\frac{1}{\prod_{i}a_i}
\]
证明仍然考虑树的拓扑序，枚举排列相当于枚举了 \(n\) 棵子树的相对关系，相当于它们没有关系，也即 \(n\) 棵树构成的森林。
考虑 \(k=2\) 怎么做。发现式子中会多出一个 \(a_j\) 并钦定 \(p_1=j\)。但这样就不能直接使用拓扑序刻画了（是一个 DAG）。容斥哪些数在 \(a_j\) 前面：
\[
\begin{align*}
&\sum_{j=1}^{n}\sum_{S}\sum_{P\in perm}[\forall S_i,~p^{-1}_{S_i}<p^{-1}_{j}]\frac{a_j}{\prod s_i}\\
=~&\frac{1}{(\sum a_i)!}\sum_{j=1}^{n}a_j\sum_{S}\frac{(sum+a_j)!}{(\prod_{i\in S}a_i)(sum+a_j)}\frac{(\sum a-sum-a_j)!}{\prod_{i\notin S,i\ne j}a_i}(-1)^{|S|}\binom{\sum a}{sum+a_j}\\
=~&\sum_{j=1}^{n}a_j^2\sum_{S}\frac{(-1)^{|S|}}{(\prod a_i)(sum+a_j)}
\end{align*}
\]
这样就和顺序无关了，于是设计一个 \(O(n^2m^2)\) 的 dp 即可。
如果存在一个全体都没有点亮的置换环，或者不小心熄灭了一个自环，那么就失败了。不难发现所有瞎猜的方法失败的概率都是相同的，因此不妨从前往后依次考虑每个灯。
那么能成功当且仅当在遇到第一个自环之前就已经点亮所有点了。枚举第一个自环出现在哪里，记为 \(t\)，由此将序列分为三段：\([1,t),[t,A],(A,n]\)，然后限制形如第一段不能有自环，第三段的每个点都必须能通过置换环走到第一段的某个点。对第一段的自环进行容斥，之后将第三段的点插入第一段，再将第二段的点任意排列或插入之前的置换环。时间复杂度 \(O(A^2+N)\)。
给定 \(n,p,k\)，保证 \(k\) 是不超过 \(1048576\) 的 \(2\) 的次幂。询问
\[
\sum_{i=0}^n\binom{n}{i}p^{i}\left\lfloor\frac{i}{k}\right\rfloor \bmod 998244353
\]
注意到
\[
\left\lfloor\frac{i}{k}\right\rfloor=\sum_{j=0}^{i}[k\mid j]-1
\]
然后进行单位根反演，并代入原式：
\[
\left\lfloor\frac{i}{k}\right\rfloor=\bigg(\frac{1}{k}\sum_{j=0}^{i}\sum_{t=0}^{k-1}w_{k}^{tj}\bigg)-1\\
\begin{align*}
\sum_{i=0}^n\binom{n}{i}p^{i}\left\lfloor\frac{i}{k} \right\rfloor&=\sum_{i=0}^n\binom{n}{i}p^{i}\bigg(\bigg(\frac{1}{k}\sum_{j=0}^{i}\sum_{t=0}^{k-1}w_{k}^{tj}\bigg)-1\bigg)\\
&=\frac{1}{k}\sum_{i=0}^n\binom{n}{i}p^{i}\sum_{j=0}^{i}\sum_{t=0}^{k-1}w_{k}^{tj}-\sum_{i=0}^{n}\binom{n}{i}p^i\\
&=\bigg(\frac{1}{k}\sum_{i=0}^n\binom{n}{i}p^{i}\sum_{j=0}^{i}\sum_{t=0}^{k-1}w_{k}^{tj}\bigg)-(p+1)^{n}
\end{align*}
\]
前面那坨：
\[
\begin{align*}
\frac{1}{k}\sum_{i=0}^n\binom{n}{i}p^{i}\sum_{j=0}^{i}\sum_{t=0}^{k-1}w_{k}^{tj}&=\frac{1}{k}\sum_{i=0}^n\binom{n}{i}p^{i}\sum_{t=0}^{k-1}\sum_{j=0}^{i}w_{k}^{tj}\\
&=\frac{1}{k}\sum_{i=0}^n\binom{n}{i}p^{i}\sum_{t=1}^{k-1}\frac{1-w_{k}^{t(i+1)}}{1-w_{k}^{t}}+\frac{1}{k}\sum_{i=0}^{n}\binom{n}{i}ip^i\\
&=\frac{1}{k}\sum_{t=1}^{k-1}\frac{1}{1-w_{k}^{t}}\sum_{i=0}^n\binom{n}{i}p^{i}(1-w_{k}^{t(i+1)})+\frac{np}{k}(p+1)^{n-1}\\
&=\frac{1}{k}\sum_{t=1}^{k-1}\frac{1}{1-w_{k}^{t}}\bigg((p+1)^n-w_k^{t}(pw_k^t+1)^n\bigg)
\end{align*}
\]
然后直接计算即可。模 \(998244353\) 的单位根可以由原根 \(3\) 计算得到。
设每个点的实际度数为 \(d_u\)，那么答案可以写成：
\[
\sum_{E}\prod_{u=1}^{n}\Big[4\mid(d_u-c_u)\Big]
\]
单位根反演：
\[
\begin{align*}
\sum_{E}\prod_{u=1}^{n}\frac{1}{4}\sum_{i=0}^{3}w_{4}^{i(d_u-c_u)}&=\sum_{\{x_1,x_2,x_3\cdots x_n\},~x_i\in\{1,-1,i,-i\}}\sum_{E}\prod_{u=1}^{n}\frac{1}{4}x_u^{-c_u}x_u^{d_u}\\
&=\sum_{\{x_1,x_2,x_3\cdots x_n\}}\prod_{u=1}^{n}\frac{1}{4}x_u^{-c_u}\prod_{i<j}\frac{1+x_ix_j}{2}
\end{align*}
\]
发现 \(\{x_i\}\) 需要满足一些很苛刻的条件，才满足 \(1+x_ix_j\ne 0\)。具体来讲，\(1\) 和 \(-1\) 不能同时存在，\(i\) 和 \(-i\) 各只能出现最多一次。于是剩下的情况很少，瞎做一下就可以。
至于给定的模数下，\(-1\) 可能不存在二次剩余。因此使用扩域记录实部和虚部即可。
代码
| #include<iostream>
#define ll long long
using namespace std;
int MOD, m1, hf, mhf;
struct comp {
int a, b;
inline comp() : a(0), b(0) {}
inline comp(int _a, int _b) : a(_a % MOD), b(_b % MOD) {}
inline comp(ll _a, ll _b) : a(_a % MOD), b(_b % MOD) {}
inline comp operator+(const comp &oth) const { return comp(a + oth.a, b + oth.b); }
inline comp &operator+=(const comp &oth) { return *this = *this + oth; }
inline comp operator-(const comp &oth) const { return comp(a - oth.a + MOD, b - oth.b + MOD); }
inline comp operator-() const { return comp(MOD - a, MOD - b); }
inline comp operator*(const comp &oth) const { return comp((ll)a * oth.a - (ll)b * oth.b % MOD + MOD, (ll)a * oth.b + (ll)b * oth.a); }
inline comp operator*(int x) const { return comp((ll)a * x, (ll)b * x); }
};
inline comp qpow(comp a, int b) {
comp res(1, 0);
while(b) {
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
inline int qpow(int a, int b) {
int res = 1;
while(b) {
if(b & 1) res = (ll)res * a % MOD;
a = (ll)a * a % MOD;
b >>= 1;
}
return res;
}
int T;
int n, a[4];
comp ans;
int main() {
cin >> T >> MOD;
m1 = MOD - 1, hf = qpow(2, MOD - 2), mhf = MOD - hf;
while(T--) {
cin >> n >> a[0] >> a[1] >> a[2] >> a[3];
if((a[1] + 2 * a[2] + 3 * a[3]) & 1) { cout << "0\n"; continue; }
if(n == 2) {
if(a[1] == 2) cout << hf << '\n';
else if(a[0] == 2) cout << hf << '\n';
else cout << "0\n";
continue;
}
ans = comp(0, 0);
ans += comp(1, 0);
for(int t = 0; t < 4; t++) {
ans += qpow(comp(0, m1), t) * qpow(comp(hf, hf), n - 1) * a[t];
ans += qpow(comp(0, 1), t) * qpow(comp(hf, mhf), n - 1) * a[t];
}
for(int t1 = 0; t1 < 4; t1++) {
for(int t2 = 0; t2 < 4; t2++) {
ans += qpow(comp(0, m1), t1) * qpow(comp(0, 1), t2) * qpow(comp(hf, hf) * comp(hf, mhf), n - 2) * ((ll)a[t1] * (a[t2] - (t1 == t2) + MOD) % MOD);
}
}
int res = 2 * ans.a;
if(ans.b) throw;
res = (ll)res * qpow(qpow(4, MOD - 2), n) % MOD;
cout << res << '\n';
}
return 0;
}
|
对于一个固定的 \(a\)，我们有贪心策略：尽可能往大选。因此对于一个 \(b\) 序列，如果它往上走一步，就说明没有被堵住，有 \(m-1\) 种情况；否则就说明被堵住了，只有一种情况。另外，如果 \(b\) 达到了 \(m\)，那么后面直接走到 \(m\) 上面就没事了。
因此对不合法的 \(b\) 进行计数：考虑两条直线 \(y=-1\) 和 \(y=m\)，那么 \(b\) 必须在碰到 \(y=m\) 之前碰到 \(y=-1\)。碰到之后 \(a\) 就可以随便选，这也恰好等于 \(b\) 的路径贡献之和。
因此枚举 \(b_n\) 的值，那么路径的权值积就已经确定。在碰到 \(y=m\) 之前碰到 \(y=-1\) 是一个经典的反射容斥问题，时间复杂度是 \(O(\frac{n}{m})\) 的，可以根号分治通过 easy version。考虑如何做到线性，发现对于一个 \(b_n\)，能产生贡献的路径终点形如上下两个公差为 \(2m+2\) 的等差数列。因此可以离线下来扫一遍值域做完了。
代码
| #include<iostream>
#include<cmath>
#define int long long
using namespace std;
const int MOD = 998244353;
const int N = 2e6 + 10;
inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }
int T, n, m, b0, p;
int L, R, ans;
int inv[N], fact[N], ifact[N];
inline int C(int a, int b) {
return fact[a] * ifact[a - b] % MOD * ifact[b] % MOD;
}
int d[4 * N], s[2 * N];
inline void insert(int x, int v) {
if(x < b0 - n) return;
add(s[(x % p + p) % p], v);
if(x + p <= R) add(d[x + p - L], MOD - v);
if(2 * m - x <= R) add(d[2 * m - x - L], MOD - v);
}
inline void clear() {
ans = 0;
for(int i = b0 - n - L; i <= n + b0 - L; i++) d[i] = s[i % p] = 0;
}
signed main() {
inv[1] = fact[0] = ifact[0] = 1;
for(int i = 2; i < N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
for(int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
for(int i = 1; i < N; i++) ifact[i] = ifact[i - 1] * inv[i] % MOD;
cin >> T;
while(T--) {
cin >> n >> m >> b0;
p = 2 * m + 2;
int tmp = 1;
for(int i = 1; i <= n; i++) tmp = tmp * m % MOD;
if(b0 >= m) { cout << tmp << '\n'; continue; }
L = floor((double)(b0 - n) / p) * p;
R = ceil((double)(b0 + n) / p) * p;
clear();
for(int i = b0 - n, sum = 1; i <= b0 + n; i += 2, sum = sum * (m - 1) % MOD) {
if(i <= -1) insert(i, sum);
else insert(-2 - i, sum);
}
for(int i = b0 - n - L; i <= n + b0 - L; i += 2) {
add(s[i % p], d[i]);
int x = i + L;
if(b0 - n <= x && x <= n + b0) {
int t = (n - b0 + x) >> 1;
add(ans, s[i % p] * C(n, t) % MOD);
}
}
cout << (tmp - ans + MOD) % MOD << '\n';
}
return 0;
}
|