#include <cstdio>
template<typename T>inline T read(void) {
    register bool f = true;
    register T x = 0;
    register char ch = std::getchar();

    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = false;

        ch = std::getchar();
    }

    while (ch >= '0' && ch <= '9')
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = std::getchar();

    return f == true ? x : ~x + 1;
}
template<typename T>inline void write(register T x) {
    if (x < 0)
        std::putchar('-'), x = ~x + 1;

    if (x > 9)
        write(x / 10);

    std::putchar(x % 10 ^ 48);
}
#define ll long long
const int N = 25, mod = 998244353;
ll C[N][N], val[N], LCM[1 << 20], siz[1 << 20], sum[1 << 20], P[N];
inline ll plus(ll x, ll y) {
    return x + y > mod ? (x + y - mod) : (x + y);
}
inline ll Mul(ll x, ll y) {
    return (ll)x * y % mod;
}
inline ll minus(ll x, ll y) {
    return x < y ? (x - y + mod) : (x - y);
}
inline void FWT_OR(int ALL) {
    for (int len = 2, k = 1; len <= ALL; k = len, len <<= 1)
        for (int i = 0; i < ALL; i += len)
            for (int j = 0; j < k; ++j)
                sum[i + j + k] = plus(sum[i + j + k], sum[i + j]);
}
inline void init(int n) {
    C[0][0] = 1;

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= i; ++j)
            if (!j)
                C[i][j] = 1;
            else
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
inline ll gcd(ll a, ll b) {
    if (b)
        while ((a %= b) && (b %= a));

    return a + b;
}
inline ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}
inline ll Pow(ll a, ll b) {
    ll ans = 1;

    while (b) {
        if (b & 0x1)
            ans = Mul(ans, a);

        b >>= 1, a = Mul(a, a);
    }

    return ans;
}
inline ll min(ll a, ll b) {
    return a < b ? a : b;
}
int main() {
    ll n = read<ll>();
    int m = read<int>();

    for (int i = 1; i <= m; ++i)
        val[i] = read<ll>();

    int ALL = 1 << m;
    init(m);

    for (int i = 0; i <= m; ++i) {
        P[i] = ((i & 3) == 0);

        for (int j = 0; j < i; ++j)
            P[i] = minus(P[i], Mul(C[i][j], P[j]));
    }

    LCM[0] = 1;

    for (int S = 0; S < ALL; ++S) {
        int pos;

        if (S) {
            siz[S] = siz[S >> 1] + (S & 1);

            for (int i = 1; i <= m; ++i)
                if (S & (1 << i - 1)) {
                    pos = i;
                    break;
                }

            LCM[S] = min(lcm(LCM[S ^ (1 << pos - 1)], val[pos]), n + 1);
        }

        sum[S] = Mul(P[siz[S]], n / LCM[S]);
    }

    FWT_OR(ALL);
    ll ans = 0;

    for (int S = 0; S < ALL; ++S)
        ans = plus(ans, sum[S]);

    ans = Mul(ans, Pow(Pow(2, m), mod - 2));
    write(ans);
    return 0;
}

灯的颜色变换与红灯个数期望问题 题解

算法标签

期望线性性质、组合数递推、FWT（OR变换）、数论（GCD/LCM）、模逆元、子集枚举、费马小定理

题目分析

核心问题

给定 $n$ 盏初始为红色的灯、$m$ 个操作（每个操作对 $x_i$ 的倍数灯进行颜色变换），随机选取操作子集执行后，求最终红灯个数的期望值（对 998244353 取模）。颜色变换规则为：红→绿→蓝→黄→红（4次循环）。

关键矛盾与破局点

1. 规模矛盾：$n$ 可达 $10^9$，无法枚举每盏灯；$m$ 仅≤20，可通过子集枚举突破（总子集数 $2^{20}=1048576$，完全可控）。
2. 期望计算矛盾：直接计算所有灯的联合状态概率复杂，利用期望线性性质拆解为“单灯为红灯的概率之和”，简化问题。
3. 操作次数与颜色的关系：灯为红灯的充要条件是被操作次数 ≡ 0 mod 4，因此核心是计算每盏灯满足该条件的概率。

核心数学结论

1. 期望线性性质：设 $X_k$ 为灯 $k$ 是红灯的指示变量（1 表示是，0 表示否），则总期望 $E[X] = \sum_{k=1}^n E[X_k] = \sum_{k=1}^n P(k$ 为红灯$)$。
2. 操作次数的本质：灯 $k$ 被操作的次数 = 选中的操作中满足 $x_i \mid k$（$x_i$ 整除 $k$）的个数，记为 $t_k$。
3. 概率转化：$P(k$ 为红灯$) = \frac{\text{使 } t_k \equiv 0 \mod 4 \text{ 的操作子集数}}{2^m}$（总子集数为 $2^m$，等概率选取）。

核心思路

1. 问题转化：总期望 = $\frac{1}{2^m} \times \sum_{k=1}^n f(k)$，其中 $f(k)$ 是使 $t_k \equiv 0 \mod 4$ 的操作子集数。核心目标变为计算 $\sum_{k=1}^n f(k)$。
2. 子集贡献建模：对每个操作子集 $S$，定义：
   • $siz[S]$：子集 $S$ 包含的操作数（即 $|S|$）。
   • $LCM[S]$：子集 $S$ 中所有 $x_i$ 的最小公倍数（若 $LCM[S] > n$，则无灯被该子集影响）。
   • $cnt[S]$：被 $S$ 中所有 $x_i$ 整除的灯的数量（即 $n // LCM[S]$，这些灯的 $t_k$ 至少包含 $siz[S]$ 的贡献）。
3. 组合数和递推：用 $P[s]$ 表示“$s$ 个操作中选 $t$ 个，且 $t \equiv 0 \mod 4$ 的选法数”，通过递推计算 $P[s]$。
4. FWT_OR 合并贡献：利用 OR 变换的 Zeta 性质，将子集的分散贡献合并为所有灯的总贡献 $\sum_{k=1}^n f(k)$。
5. 模逆元修正：乘以 $2^m$ 的模逆元，得到最终期望。

关键技术解析

1. 组合数和 $P[s]$ 的递推计算

定义与意义

$P[s] = \sum_{t \equiv 0 \mod 4} \binom{s}{t}$，表示 $s$ 个操作中选 $t$ 个（$t$ 满足循环条件）的选法数。

递推推导

利用组合数递推性质 $\binom{s}{t} = \binom{s-1}{t} + \binom{s-1}{t-1}$，对 $P[s]$ 求和可得：

$$P[s] = \sum_{t \equiv 0 \mod 4} \left( \binom{s-1}{t} + \binom{s-1}{t-1} \right) = P[s-1] + K[s-1] $$

其中 $K[s-1]$ 是 $\sum_{t \equiv 0 \mod 4} \binom{s-1}{t-1} = \sum_{t' \equiv 3 \mod 4} \binom{s-1}{t'}$（令 $t'=t-1$）。

通过联立 $P, Q, R, K$（分别对应 $t \equiv 0,1,2,3 \mod4$ 的组合数和）的递推方程，最终化简得到代码中的递推式：

$$P[s] = \begin{cases} 1 & s=0 \\ \left( [s \equiv 0 \mod4] - \sum_{j=0}^{s-1} \binom{s}{j} P[j] \right) \mod mod & s>0 \end{cases}$$

其中 $[condition]$ 是指示函数（条件成立为 1，否则为 0）。

2. 子集 LCM 计算与灯数统计

核心逻辑

对每个操作子集 $S$，其影响的灯是所有 $LCM[S]$ 的倍数（因 $LCM[S]$ 是子集内所有 $x_i$ 的公倍数，能被 $LCM[S]$ 整除的灯必能被所有 $x_i$ 整除）。

高效计算

• 子集拆分：将 $S$ 拆分为 $S' = S \setminus \{pos\}$（$pos$ 是 $S$ 中任意一个操作），则 $LCM[S] = \text{LCM}(LCM[S'], x_{pos})$。
• 边界处理：若 $LCM[S] > n$，则 $cnt[S] = n // LCM[S] = 0$，无需后续计算，故代码中用 $\min(\text{LCM}(...), n+1)$ 截断。

3. FWT_OR 变换的作用

变换目标

将“子集 $S$ 的贡献 $P[siz[S]] \times cnt[S]$”转化为“所有包含 $S$ 的超集 $T$ 的总贡献”，本质是计算 Zeta 变换：

$$\text{sum}[S] \leftarrow \sum_{T \supseteq S} \text{sum}[T] $$

该变换可高效合并所有灯的 $f(k)$ 之和——灯 $k$ 对应的操作子集是 $T_k = \{i \mid x_i \mid k\}$，其贡献 $f(k)$ 恰好是所有 $S \subseteq T_k$ 的 $\text{sum}[S]$ 之和，通过 FWT_OR 可一次性完成所有灯的贡献累加。

变换实现

代码中通过三层循环完成：

1. 按块长度 $len$（2 的幂）迭代，$k = len/2$。
2. 对每个块，将前半部分 $a[i..i+k-1]$ 的贡献叠加到后半部分 $b[i+k..i+len-1]$，实现“超集贡献合并”。

4. 模逆元与最终期望计算

总子集数的逆元

因总操作子集数为 $2^m$，最终期望需除以 $2^m$，模运算中除法等价于乘以逆元。由费马小定理（$mod$ 是质数），$2^m$ 的逆元为 $Pow(2^m, mod-2) \mod mod$。

结果合并

FWT_OR 变换后，所有 $\text{sum}[S]$ 之和即为 $\sum_{k=1}^n f(k)$，乘以逆元后得到最终期望。

代码解析（分模块）

1. 输入输出与工具函数

// 快速读入（处理正负，避免溢出）
template<typename T>inline T read(void) { ... }
// 快速输出（递归处理高位，避免溢出）
template<typename T>inline void write(register T x) { ... }
// 模运算工具（确保结果在 [0, mod) 范围内）
inline ll plus(ll x, ll y) { ... } // 模加法
inline ll minus(ll x, ll y) { ... } // 模减法
inline ll Mul(ll x, ll y) { ... } // 模乘法
// 数论工具
inline ll gcd(ll a, ll b) { ... } // 欧几里得算法求GCD
inline ll lcm(ll a, ll b) { ... } // 利用GCD求LCM
inline ll Pow(ll a, ll b) { ... } // 快速幂（求逆元用）

2. 组合数与 P 数组初始化

init(m); // 初始化组合数 C[n][m]
// 计算 P 数组
for (int i = 0; i <= m; ++i) {
    P[i] = ((i & 3) == 0); // 指示函数 [i≡0 mod4]
    for (int j = 0; j < i; ++j)
        P[i] = minus(P[i], Mul(C[i][j], P[j])); // 递推减去过量贡献
}

3. 子集枚举与 LCM、sum 数组计算

int ALL = 1 << m;
LCM[0] = 1; // 空集LCM为1（所有数的公倍数）
for (int S = 0; S < ALL; ++S) {
    if (S) {
        siz[S] = siz[S >> 1] + (S & 1); // 统计子集大小（二进制1的个数）
        // 找到S中任意一个操作pos
        for (int i = 1; i <= m; ++i)
            if (S & (1 << i - 1)) { pos = i; break; }
        // 计算当前子集的LCM并截断
        LCM[S] = min(lcm(LCM[S ^ (1 << pos - 1)], val[pos]), n + 1);
    }
    // 子集S的贡献：P[子集大小] * 受影响的灯数
    sum[S] = Mul(P[siz[S]], n / LCM[S]);
}

4. FWT_OR 变换与结果计算

FWT_OR(ALL); // 执行OR变换合并贡献
ll ans = 0;
for (int S = 0; S < ALL; ++S)
    ans = plus(ans, sum[S]); // 累加所有贡献得到sum_{k=1}^n f(k)
// 乘以2^m的逆元得到期望
ans = Mul(ans, Pow(Pow(2, m), mod - 2));
write(ans);

复杂度分析

步骤	时间复杂度	说明
组合数与 P 数组初始化	$O(m^2)$	$m≤20$，$20^2=400$ 可忽略
子集枚举与 LCM 计算	$O(m \times 2^m)$	每个子集遍历 $m$ 位找pos，$2^20×20≈2e7$
FWT_OR 变换		变换复杂度为 $O(2^m \log 2^m) = O(m×2^m)$
结果合并与逆元计算	$O(2^m + \log m)$	累加子集贡献+快速幂求逆元

总时间复杂度：$O(m×2^m)$，对于 $m=20$ 完全可控（运算量约 $2e7$）。
空间复杂度：$O(2^m)$，存储 LCM、siz、sum 数组（$1e6$ 元素，约 8MB）。

关键注意事项

1. LCM 溢出处理：计算 $\text{LCM}(a,b)$ 时先除后乘（$a/gcd(a,b)×b$），避免 $a×b$ 溢出（因 $n≤1e9$，截断后 LCM 最大为 $1e9+1$）。
2. 模运算符号：minus 函数确保减法结果非负，避免出现负模值。
3. 空集贡献：空集 $S=0$ 对应“不选任何操作”，其 LCM=1，影响所有 $n$ 盏灯，$P[0]=1$（0次操作满足红灯条件），贡献为 $1×n$，是基础贡献。