#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10, mod = 998244353;
const int G = 3, W = 911660635, inv4 = 748683265;
int n, fac[N], inv[N], f[N], a[N];
int C(int n, int m) {
    return (n < m || m < 0) ? 0 : 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main() {
    fac[0] = fac[1] = inv[0] = inv[1] = 1;

    for (int i = 2; i < N; i++)
        fac[i] = 1ll * fac[i - 1] * i % mod, inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;

    for (int i = 2; i < N; i++)
        inv[i] = 1ll * inv[i] * inv[i - 1] % mod;

    cin >> n;
    f[n] = 2;

    for (int i = n; i; i--)
        f[i - 1] = 1ll * f[i] * f[i] % mod;

    for (int i = 0; i <= n; i++)
        f[i] = 1ll * (f[i] - 1) * C(n, i) % mod;

    for (int i = 0, w = 1; i < 4; i++, w = 1ll * w * W % mod)
        for (int j = 0, res = 1; j <= n; j++)
            a[j] = (a[j] + res) % mod, res = 1ll * res * (w - 1) % mod;

    int ans = 1;

    for (int i = 0; i <= n; i++)
        ans = (1ll * ans + 1ll * f[i] * a[i] % mod * inv4) % mod;

    cout << ans << "\n";
    return 0;
}

世界之力与技能选择问题 题解

算法标签

组合数学、容斥原理、单位根反演、预处理（阶乘/逆元）、递推、快速幂

题目分析

核心问题

给定 $n$ 种世界之力，每种技能对应世界之力的一个子集（共 $2^n$ 种技能）。统计所有技能使用情况（子集族）的个数，要求所有选中技能的交集大小为 4 的倍数（空族的交集大小定义为 0，符合条件），答案对 998244353 取模。

关键矛盾与破局点

1. 规模矛盾：$n$ 可达 $10^7$，无法枚举所有子集或子集族，需推导数学公式并通过 $O(n)$ 预处理实现高效计算。
2. 计数难点：直接统计“交集大小为 4 的倍数”的子集族，需同时处理“交集恰好为 $k$”的计数和“$k$ 是 4 的倍数”的筛选，需结合容斥原理和单位根反演。
3. 指数运算难点：涉及 $2^{2^m}$ 这类双重指数运算，无法直接用快速幂计算，需通过递推实现 $O(n)$ 预处理。

核心数学基础

1. 子集族与交集：子集族 $F$ 的交集 $\cap F$ 是所有子集中的公共元素集合；空族的交集大小为 0（符合 4 的倍数条件）。
2. 容斥原理：计算“交集恰好为 $k$”的子集族数，需用容斥剔除“交集包含更多元素”的情况。
3. 单位根反演：对于模 4 的筛选，利用 4 次单位根的性质，将“求和仅保留 4 的倍数项”转化为对生成函数在单位根处的值求和，公式为：$$\sum_{k \equiv 0 \pmod{4}} g(k) = \frac{1}{4} \sum_{j=0}^{3} \omega^{-jk} G(\omega^j) $$其中 $\omega$ 是模 998244353 的 4 次单位根，$G(x)$ 是 $g(k)$ 的生成函数。

核心思路

1. 计数公式推导：

   • 设 $f(k)$ 为“交集大小恰好为 $k$”的子集族数，通过容斥原理可得：$$f(k) = \binom{n}{k} \sum_{s=0}^{n-k} (-1)^s \binom{n-k}{s} 2^{2^{(n-k)-s}} $$解释：选择 $k$ 个公共元素（$\binom{n}{k}$），剩余 $n-k$ 个元素组成集合 $Y$，子集族需满足“交集仅为 $k$ 个元素”（等价于 $Y$ 的子集族交集为空），后者通过容斥计算为 $\sum_{s=0}^{n-k} (-1)^s \binom{n-k}{s} 2^{2^{(n-k)-s}}$。
   • 目标答案为 $\sum_{k \equiv 0 \pmod{4}} f(k)$，结合单位根反演简化求和。

2. 预处理优化：

   • 阶乘与逆元：预处理 $\binom{n}{k}$ 所需的阶乘 $fac[k]$ 和阶乘逆元 $inv[k]$，支持 $O(1)$ 计算组合数。
   • 双重指数递推：通过递推计算 $2^{2^m}$（记为 $pow2[m]$），利用 $2^{2^m} = (2^{2^{m-1}})^2$ 实现 $O(n)$ 预处理。

3. 单位根反演筛选：

   • 构造生成函数 $G(x) = \sum_{k=0}^n f(k) x^k$，计算 $G(\omega^j)$（$j=0,1,2,3$）并代入单位根反演公式，得到目标和。

算法步骤

步骤 1：预处理阶乘与逆元

• 阶乘 $fac[k]$：$fac[0] = 1$，$fac[k] = fac[k-1] \times k \mod mod$（$1 \leq k \leq n$），存储 $k!$ 的模值。
• 阶乘逆元 $inv[k]$：先用快速幂求 $inv[n] = pow(fac[n], mod-2, mod)$，再递推 $inv[k-1] = inv[k] \times k \mod mod$（$n \geq k \geq 1$），支持 $O(1)$ 计算 $\binom{n}{k} = fac[n] \times inv[k] \times inv[n-k] \mod mod$。

步骤 2：递推计算双重指数 $2^{2^m}$

• 定义 $f[i] = 2^{2^{n-i}}$（$i$ 从 $0$ 到 $n$），递推关系为：
  • 初始值：$f[n] = 2 = 2^{2^0}$（对应 $m=0$，$2^{2^0}=2$）。
  • 递推式：$f[i-1] = f[i]^2 \mod mod$（因 $2^{2^m} = (2^{2^{m-1}})^2$）。

步骤 3：容斥修正计算中间项

• 对每个 $i$（对应公共元素个数 $i$），计算容斥修正后的项：$$f[i] = (f[i] - 1) \times \binom{n}{i} \mod mod$$ 其中 $(f[i]-1)$ 是容斥中“非空子集族”的修正（避免重复计数），$\binom{n}{i}$ 是选择 $i$ 个公共元素的组合数。

步骤 4：单位根反演预处理生成函数值

• 初始化 4 次单位根相关参数：$\omega = 3^{(mod-1)/4} \mod mod$（原根 3 构造 4 次单位根），$W$ 是 $\omega$ 的逆元（代码中 $W=911660635$），$inv4=748683265$ 是 4 的模逆元。
• 计算生成函数在单位根处的贡献数组 $a$：
  • 对每个单位根幂次 $\omega^j$（$j=0,1,2,3$），计算 $(ω^j - 1)^k$ 并累加至 $a[k]$，即 $a[k] = \sum_{j=0}^3 (ω^j - 1)^k \mod mod$。

步骤 5：计算最终答案

• 初始答案 $ans=1$（对应空族的情况）。
• 代入单位根反演公式，累加贡献：$$ans = \left( ans + \sum_{k=0}^n f[k] \times a[k] \times inv4 \mod mod \right) \mod mod $$
• 输出 $ans$（确保结果非负）。

代码解析

核心工具函数与预处理

const int N = 1e7 + 10, mod = 998244353;
const int G = 3, W = 911660635, inv4 = 748683265; // W是4次单位根逆元，inv4是4的逆元
int n, fac[N], inv[N], f[N], a[N];

// 计算组合数C(n,m)
int C(int n, int m) {
    return (n < m || m < 0) ? 0 : 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}

// 预处理阶乘与逆元
fac[0] = fac[1] = inv[0] = inv[1] = 1;
for (int i = 2; i < N; i++) {
    fac[i] = 1ll * fac[i - 1] * i % mod; // 阶乘
    inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod; // 逆元递推（费马小定理优化）
}
for (int i = 2; i < N; i++) {
    inv[i] = 1ll * inv[i] * inv[i - 1] % mod; // 转换为阶乘逆元
}

• 阶乘逆元递推：先通过“模逆元递推公式”计算单个元素的逆元，再累积得到阶乘逆元，避免重复调用快速幂，提升效率。

双重指数递推与容斥修正

cin >> n;
f[n] = 2; // 初始值：f[n] = 2^(2^0) = 2
for (int i = n; i; i--) {
    f[i - 1] = 1ll * f[i] * f[i] % mod; // 递推：f[i-1] = (f[i])^2 = 2^(2^(n-(i-1)))
}
for (int i = 0; i <= n; i++) {
    f[i] = 1ll * (f[i] - 1) * C(n, i) % mod; // 容斥修正：(2^(2^m)-1)*C(n,i)
}

• 双重指数递推：利用平方关系避免直接计算 $2^{2^m}$，时间复杂度 $O(n)$，适配 $n=1e7$。
• 容斥修正：$(f[i]-1)$ 对应“非空子集族”，乘以组合数 $C(n,i)$ 得到“交集至少为 $i$ 个元素”的容斥项。

单位根贡献计算（a数组）

for (int i = 0, w = 1; i < 4; i++, w = 1ll * w * W % mod) { // 遍历4次单位根幂次
    for (int j = 0, res = 1; j <= n; j++) {
        a[j] = (a[j] + res) % mod; // 累加(ω^i - 1)^j
        res = 1ll * res * (w - 1) % mod; // 递推(ω^i - 1)^j = (ω^i - 1)^(j-1) * (ω^i - 1)
    }
}

• 核心逻辑：$a[j] = \sum_{k=0}^3 (ω^k - 1)^j$，为单位根反演提供生成函数在单位根处的取值。

最终答案计算

int ans = 1; // 初始值：空族的情况（交集大小0，符合条件）
for (int i = 0; i <= n; i++) {
    ans = (1ll * ans + 1ll * f[i] * a[i] % mod * inv4) % mod; // 单位根反演求和
}
cout << ans << "\n";

• 单位根反演应用：$\sum_{i≡0 mod4} f[i] = \frac{1}{4} \sum_{i=0}^n f[i] \times a[i]$，乘以 $inv4$ 实现除法模运算。
• 空族处理：初始 $ans=1$ 单独计数空族，避免容斥项遗漏。

复杂度分析

总复杂度：$O(n)$ 时间 + $O(n)$ 空间，完全适配 $n=1e7$ 的数据规模（内存占用约 240MB，可控）。

关键注意事项

1. 模运算符号处理：所有减法操作需加 $mod$ 再取模，避免负数值（如代码中 $(f[i]-1)$ 已隐含模运算，因 $f[i] < mod$）。
2. 单位根选择：$W$ 是 4 次单位根的逆元，需确保 $\omega^4 \equiv 1 \mod mod$，验证：$W^4 = 911660635^4 \mod 998244353 = 1$。
3. 双重指数递推正确性：$f[i] = 2^{2^{n-i}}$ 的递推关系需严格遵循平方规则，初始值 $f[n] = 2$ 不可错。
4. 空族计数：初始 $ans=1$ 对应“不选任何技能”的情况，若遗漏会导致样例输出少 1（如样例 $n=2$ 会输出 10 而非 11）。

样例验证（n=2）

1. 预处理：$fac=[1,1,2]$，$inv=[1,1,499122177]$。
2. 双重指数递推：$f[2]=2$，$f[1]=4$，$f[0]=16$。
3. 容斥修正：$f[0]=(16-1)*1=15$，$f[1]=(4-1)*2=6$，$f[2]=(2-1)*1=1$。
4. a数组计算：$a[0]=4$，$a[1]=998244349$（即 -4），$a[2]=4$。
5. 答案计算：$ans=1 + (15*4 + 6*(-4) + 1*4)*inv4 = 1 + (60-24+4)/4 = 1 + 40/4 = 11$，与样例一致。