P6298 齿轮题解

Rose ·

更新时间:2024-11-15

· 972 次阅读

博客园同步

原题链接

简要题意：

求在 nnn 个数中选 kkk 个数使其 gcd⁡\gcdgcd 分别为 111 ~ mmm 的个数。m=max⁡i=1naim = \max_{i=1}^n a_im=maxi=1nai.

这是某洛谷月赛的 T2\text{T2}T2，有一定思维难度。

子任务 111

子任务 111 ：n≤10n \leq 10n≤10，m≤106m \leq 10^6m≤106，k≤10k \leq 10k≤10

暴力枚举 kkk 个数记录 gcd\text{gcd}gcd 即可。

时间复杂度：O(Cnklog⁡Cnk)O(C_n^k \log C_n^k)O(CnklogCnk).

实际得分：10pts10pts10pts.

子任务 222

子任务 222：n,m,k≤103n,m,k \leq 10^3n,m,k≤103.

给一些简单 dp\text{dp}dp 乱搞的部分分。

子任务 333

子任务 333：n≤106n \leq 10^6n≤106，m≤103m \leq 10^3m≤103，k≤2k \leq 2k≤2.

预处理两两 gcd⁡\gcdgcd. 但不是 O(n2log⁡m)O(n^2 \log m)O(n2logm) 的那种，而是预处理所有 ≤103\leq 10^3≤103 的数的个数记为 fff，在 fff 上两两匹配 gcd⁡\gcdgcd 记录个数即可。

时间复杂度：O(m2log⁡m)O(m^2 \log m)O(m2logm).

实际得分：5pts5pts5pts.

子任务 444

子任务 444：n,m≤106n,m \leq 10^6n,m≤106，k≤1k \leq 1k≤1

这是个送分的子任务，统计每个数出现的次数即可。

时间复杂度：O(n)O(n)O(n).

实际得分：5pts5pts5pts.

子任务 555

子任务 555：n,m≤106n,m \leq 10^6n,m≤106，k≤2k \leq 2k≤2.

似乎不能暴力统计两两 gcd⁡\gcdgcd 了。所以这个子任务想要解决必须写正解，如果你会乱搞可以试一试。

子任务 111 ~ 666

对于 100%100 \%100% 的数据，n,m≤106n,m \leq 10^6n,m≤106,1≤k≤n1 \leq k \leq n1≤k≤n.

我们需要考虑高级的 dp\text{dp}dp 方式。

用 gig_igi 表示选出 kkk 个数，其 gcd\text{gcd}gcd 为 iii 的倍数 的个数。这里我们要考虑容斥，不是很简单的样子。

gi=C∑j=1n[i∣aj]kg_i = C_{\sum_{j=1}^n [i | a_j]}^kgi=C∑j=1n[i∣aj]k

因为在所有是 iii 的倍数中选 kkk 个用组合，但是不完全正确，因为 gig_igi 很有能计算重复，所以我们用容斥计算，把所有的 gj(i∣j and i≠j)g_j (i | j \space \space \text{and} \space \space i \not = j)gj(i∣j and i=j) 全部减掉，然后对它们的和进行组合。

如何计算组合呢？我们可以预处理 阶乘逆元 然后 O(1)O(1)O(1) 回答。

时间复杂度：O(n+m)+∑i=1mO(⌊mi⌋)=O(n+mlog⁡m)O(n + m) + \sum_{i=1}^m O \big(\lfloor \frac{m}{i} \rfloor \big) = O(n + m \log m)O(n+m)+∑i=1mO(⌊im⌋)=O(n+mlogm).

实际得分：100pts100pts100pts.

#pragma GCC optimize(2)
#include
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int N=1e6+1;
inline int read(){char ch=getchar();int f=1;while(ch'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
ll f[N],inv[N],invf[N];
ll g[N]; int t[N],n,m,k;
inline ll calc(int x,int y) {
	return x<y?0:(f[x]*invf[y]%MOD*invf[x-y]%MOD);
}  //组合
int main(){
	n=read(),m=read(),k=read();
	f[0]=invf[0]=1;
	for(int i=1;i<=n;i++) {
		inv[i]=(i==1)?1:(inv[MOD%i]*(MOD-MOD/i)%MOD);
		f[i]=f[i-1]*i%MOD; invf[i]=invf[i-1]*inv[i]%MOD; //处理逆元，阶乘逆元
		t[read()]++; //记录桶
	} for(int i=m;i;i--) {
		int cnt=0; //记录和
		for(int j=1;i*j<=m;j++) cnt+=t[i*j],g[i]=(g[i]-g[i*j]+MOD)%MOD; //容斥减掉 , 统计和
		g[i]=((g[i]+calc(cnt,k))%MOD+MOD)%MOD; //和的组合
	} for(int i=1;i<=m;i++) printf("%lld ",g[i]);
	return 0;
}

作者：bifanwen

齿轮 p6

1024 个赞