CF1559E 题解

这是 CF1559 E 的题解。

数学白痴看了好久题解才懂/kk

题目给出三个限制条件:

  1. 对所有 \(i\in [1,n]\),\(a_i\in [l_i,r_i]\)。
  2. \(\sum\limits_{i=1}^n a_i\le m\)。
  3. \(\gcd(a_1,a_2,\dots,a_n)=1\)。

如果只有前两个条件,我们可以轻松写出如下转移方程:

\[f_{i,j}=\sum\limits_{k=l_i}^{r_i} f_{i-1,j-k} \]

这个转移是 \(O(nm^2)\) 的,我们用前缀和优化,记

\[s_{i,j}=\sum\limits_{k=0}^j f_{i,k} \]

那么有

\[f_{i,j}=s_{i-1,j-l_i}-s_{i-1,j-r_i-1} \]

这个转移是 \(O(nm)\) 的。

现在加上第三个条件。容易想到用容斥去做,设

\[F(x)=\sum\limits_{a_1=l_1}^{r_1}\sum\limits_{a_2=l_2}^{r_2}...\sum\limits_{a_n=l_n}^{r_n}[\gcd(a_1,a_2,...,a_n)=x]\left[\sum\limits_{i}a_i \le m\right] \]

\(F(x)\) 即 \(\gcd(a_1,a_2,\dots,a_n)=x\) 的方案数。那么答案为 \(F(1)\)。但这个式子难以计算,这里需要一步转化:

\[G(x)=\sum\limits_{a_1=l_1}^{r_1}\sum\limits_{a_2=l_2}^{r_2}...\sum\limits_{a_n=l_n}^{r_n}[x\mid\gcd(a_1,a_2,...,a_n)]\left[\sum\limits_{i}a_i \le m\right] \]

那么 \(G(x)=\sum\limits_{d=1}^{\lfloor\frac{m}{x}\rfloor} F(dx)\)

我们先求 \(G(x)\),枚举 \(a_i\) 时强制其为 \(x\) 的倍数即可。为了使转移连续,干脆直接枚举 \(a_i\) 是 \(x\) 的几倍,那么对于 \(G(x)\),背包的容量降为 \(\left\lfloor\dfrac{m}{x}\right\rfloor\),时间复杂度变为调和级数。

根据 \(G(x)=\sum\limits_{d=1}^{\lfloor\frac{m}{x}\rfloor} F(dx)\) ,得到 \(F(x)=G(x)-\sum\limits_{d=2}^{\lfloor\frac{m}{x}\rfloor} F(dx)\)。

因此我们倒序枚举 \(x\),用背包求 \(G(x)\),从而求得 \(F(x)\),最终得到 \(F(1)\)。

以下是代码详解:

#include<bits/stdc++.h>
using namespace std;
bool MB1;

typedef long long ll;
const ll P=998244353;
const int M=55,N=1e5+5;

int n,m,l[M],r[M];
ll f[M][N],ans[N];

bool MB2;
int main()
{
//    printf("%.2lfMB\n",(&MB2-&MB1)/1024.0/1024.0);
	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&l[i],&r[i]);
	for(int g=m;g>0;g--)
	/*
	枚举 G(x) 中的 x
	其实可以从 m/n 开始枚举,我还不太明白为啥 
	*/
	{
		int up=(m-1+g)/g;
		
		/*最多的倍数向上取整*/
		
		for(int i=0;i<=n;i++)
			for(int j=0;j<=up;j++)
			{
				if(i==0)f[i][j]=1;
				else f[i][j]=0;
			}
		/*
		其实只有 f[0][0]=1
		但是这里把前缀和和转移合并到一起
		由于前缀和,i=0都是1 
		*/
		for(int i=1;i<=n;i++)
		{
			int L=(l[i]-1+g)/g,R=r[i]/g;
			/*L:最小倍数 R:最大倍数*/
			for(int j=L;j<=up;j++)
			{
				/*从总倍数处转移来*/ 
				int ok_l=max(0,j-R),ok_r=j-L;
				/*
				对应前缀和优化后的
				*/
				if(ok_l>ok_r)f[i][j]=0;
				else
				{
					f[i][j]=f[i-1][ok_r];
					if(ok_l)f[i][j]=(f[i][j]-f[i-1][ok_l-1]+P)%P;
					/*
					f[i][j]=s[i-1][j-L]-s[i-1][j-R-1] 
					但 j-R-1 可能 <0 注意判掉 
					*/
				}
			}
			for(int j=max(1,L);j<=up;j++)
				f[i][j]=(f[i][j]+f[i][j-1])%P;
			/*
			前缀和累加。 
			*/
		}
		ans[g]=f[n][m/g];
		for(int i=(g<<1);i<=m;i+=g)
			ans[g]=(ans[g]-ans[i]+P)%P;
		/*
		ans数组即 F(x) 数组 
		*/
	}
	printf("%lld",ans[1]);
    return 0;
}
/*
2 82949
3069 17191
63122 72590
*/

本篇题解参考了 Qiaoqia 的 CF1559E 题解HoshizoraZ 的 CF1559E 题解

上一篇:洛谷 P5400 - [CTS2019]随机立方体(组合数学+二项式反演)


下一篇:limits.conf 配置不生效问题排查