ABC236Ex Distinct Multiples 做题记录

给定 $n,m$ 和一个长 $n$ 的序列 $a_i$，求满足以下条件的长 $n$ 的序列 $b$ 的个数

• $1\le b_i\le m$；
• $b_i$ 两两不同；
• $b_i$ 可以被 $a_i$ 整除；

对 $998244353$ 取模。

$1\le n\le 16$，$1\le a_i\le m\le 10^{18}$。

若 $b_i=b_j$ 则连接无向边 $(i,j)$，则两两不同的限制相当于图中没有边。

考虑容斥，设 $dp_S$ 为 $i\in S$ 的 $b_i$ 的方案数。钦定某些点在同一个连通块，不难发现相同大小的连通块的容斥系数是相同的。不妨设大小为 $n$ 的连通块的容斥系数为 $f_n$，则有转移：

$dp_S=\sum\limits_{T\subseteq S,\min\{T\}=\min\{S\}}f_{|T|}\left\lfloor\frac{m}{\text{lcm}\{a_i|i\in T\}}\right\rfloor dp_{S-T}$

考虑 $f_n$ 需要满足的条件，设 $g_n$ 表示所有 $n$ 个点的无向图的容斥系数的总和，那么枚举图中边的个数，有：

$\begin{aligned} g_n&=\sum\limits_{i=0}^{\frac{n(n-1)}{2}}\binom{\frac{n(n-1)}{2}}{i}(-1)^i\\ &=\sum\limits_{i=0}^{\frac{n(n-1)}{2}}\binom{\frac{n(n-1)}{2}}{i}(-1)^i1^{n-i}\\ &=[n=0]+[n=1] \end{aligned}$

而枚举 $n$ 所在的连通块大小，有：

$\begin{aligned} g_n&=\sum\limits_{i=1}^{n}\binom{n-1}{i-1}f_{i}g_{n-i}\\ &=f_n+(n-1)f_{n-1} \end{aligned}$

而 $g_1=f_1=1$。

所以有：

$f_{n}=\begin{cases} 1&n=1\\ -(n-1)f_{n-1}&n>1 \end{cases}$

那么 $f_n=(-1)^{n-1}(n-1)!$。

那么直接 dp 即可，时间复杂度 $O(3^n)$，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int S=20,BS=1<<16,p=998244353;

int n;
ll m,a[S];
ll lcm[BS];
int f[S],dp[BS];

#define popc __builtin_popcount

inline ll gcd(ll x,ll y)
{
	if(x==0||y==0) return x+y;
	ll t=x%y;
	while(t!=0) x=y,y=t,t=x%y;
	return y;
}

inline ll getlcm(int st)
{
	ll res=1;
	for(int i=1;i<=n;i++)
	{
		if(st>>i-1&1)
		{
			ll g=gcd(res,a[i]);
			res/=g;
			if(res>m/a[i]) res=m+1;
			else res*=a[i];
		}
	}
	return res;
}

int main()
{
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=0;i<(1<<n);i++) lcm[i]=getlcm(i);
	f[1]=1;
	for(int i=2;i<=n;i++) f[i]=p-1ll*(i-1)*f[i-1]%p;
	dp[0]=1;
	for(int i=1;i<(1<<n);i++)
	{
		for(int j=i;j>0;j=(j-1)&i)
		{
			if((i&-i)!=(j&-j)) continue;
			dp[i]=(dp[i]+1ll*f[popc(j)]*((m/lcm[j])%p)%p*dp[i^j]%p)%p;
		}
	}
	printf("%d\n",dp[(1<<n)-1]);
	return 0;
}