[ABC236Ex] Distinct Multiples 题解

SFsaltyfish / 2024-09-27 / 原文

前言

非常好容斥题，使我的笔旋转。

感觉这道题又让我学到了不少。

确实是没有想过可以把容斥系数都 $\texttt{DP}$ 进去这种方式。

思路

显然正着做不太好做，反着正好有事一堆 $a_i=a_j$ 的限制，说不定会好一点。

故我们考虑容斥。

首先最暴力的一个容斥就是我们对于每一个集合 $S$，里面储存的是这个点对 $(i,j)$ 是否会被钦定为 $a_i=a_j$。（相当于说全集就是 $n\times(n-1)/2$ 个点对）对于每一个 $S$ 的贡献就是 $(-1)^{|S|} \times \prod \lfloor\dfrac{m}{\text{lcm}_{s_i}}\rfloor$。（其中，$s_i$ 表示将这些点对当作边连起来之后，构成的连通块。）

复杂度 $\mathcal{O}(2^{n\times (n-1)/2}\times \log m)$，显然不可过。

我们发现，其实我们本质上在乎的是这个连通块的分配情况，和它对应的容斥系数。

故我们定义 $dp_{s_1,s_2,s_3,...s_k}$ 表示由这些连通块所构成的答案。

假设 $E_i$ 为可以构成 $s_i$ 这个连通块的所有边集。

故 $dp_{s_1,s_2,...s_k}=\prod_{i=1}^{k}\lfloor\dfrac{m}{\text{lcm}_{s_i}}\rfloor\times (\sum (-1)^{|E_i|})$。

观察到对于一个块的任意两个点其实都是可以连边的，故这个 $\sum (-1)^{|E_i|}$ 只与 $s_i$ 的大小有关。

定义 $g_{i,0/1}$ 表示大小为 $i$ 的连通块，可以被大小为奇数/偶数的边集所构成的方案数。

故 $\sum (-1)^{|E_i|}=g_{|s_i|,1}-g_{|s_i|,0}$

对于 $g_{i,0/1}$ 的转移，我们仍然考虑一个容斥转移：

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 998244353;
#define maxn 17
int n;
ll m, a[maxn];
ll Lcm[1 << 16], flg[1 << 16];
ll Gcd(ll x, ll y)
{
    if(x > y) swap(x, y);
    if(x == 0) return y;
    return Gcd(x, y % x);
}
ll fact[maxn];
ll dp[1 << 16];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], Lcm[(1 << i - 1)] = a[i];
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i % mod;
    for (int i = 1; i < (1 << n); ++i)
    {
        if(__builtin_popcount(i) == 1) continue;
        int j = __lg(i);
        if(flg[i - (1 << j)])
        {
            flg[i] = true;
            continue;
        }
        ll gcd = Gcd(Lcm[i - (1 << j)], a[j + 1]);
        if(a[j + 1] * __int128(1) * Lcm[i - (1 << j)] / gcd > m) flg[i] = true;
        else Lcm[i] = Lcm[i - (1 << j)] / gcd * a[j + 1];
    }
    dp[0] = 1;
    for (int i = 1; i < (1 << n); ++i)
    {
        // cout << i << endl;
        int I = i - (i & -i), k = i & -i;
        for (int j = I; ; j = (j - 1) & I)
        {
            if(flg[j + k])
            {
                if(!j) break;
                continue;
            }
            if(Lcm[j + k] > m)
            {
                if(!j) break;
                continue;
            }
            dp[i] += dp[i - j - k] * ((m / Lcm[j + k]) % mod) % mod * fact[__builtin_popcount(j + k) - 1] % mod * ((__builtin_popcount(j + k) & 1) ? 1 : -1);
            dp[i] %= mod, dp[i] += mod, dp[i] %= mod;
            if(!j) break;
        }
    }
    cout << dp[(1 << n) - 1] << endl;
    return 0;
}