专栏文章

CF1359E

DDDF_
CF1359E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minhvtjn
此快照首次捕获于
2025/12/02 02:40
3 个月前
此快照最后确认于
2025/12/02 02:40
3 个月前
查看原文

题面

有一个长度为 kk 的序列，不管他怎么排列变换，对于任意的自然数 xx，满足 s=(((x mod a1) mod a2) mod ⋯ mod ak)s=(((x \bmod a_1) \bmod a_2) \bmod \cdots \bmod a_{k}) 为定值。
求序列所有元素不大于 nn 且序列元素互不相同的方案数，一个序列通过排列变换得到的序列不算一个新的序列。

题解

题目里给的是 1≤a1<a2<⋯<ak≤n1 \le a_1 < a_2 < \cdots < a_k \le n，我换成了序列元素互不相同，因为一个显然的结论：当序列为如上的形式时，s=x mod a1s=x \bmod a_1，ss 只由 a1a_1 决定。而要证明这个序列的合法性，肯定要倒过来，n≥ak>ak−1>ak−2>⋯>a1≥1n \ge a_{k} > a_{k-1} > a_{k-2} > \cdots > a_1 \ge 1，这时候 ss 就会受到数组中其他数的影响了。
然后把上面两种情况取一下，要有当序列倒过来时 s=x mod aks=x \bmod a_k。
猜结论环节。先猜一下所有数都是 aka_{k} 的倍数，然后把 ak=2a_k=2 和 ak=3a_k=3 代入发现还真行（考试时到这一步就可以打代码了）。
但是这里是题解，所以我要证明（呜呜呜）。设 p=akp=a_k，t=x mod pt=x \bmod p，然后有一个正整数 ii，令 l=x mod (p×i)l=x \bmod (p \times i)，b=l mod pb=l \bmod p，则要证明 b=tb =t。
t=x mod pt=x \bmod p，则 n1×p+t=xn_1 \times p + t = x，同理 n2×(p×i)+l=xn_2 \times (p \times i)+l=x，n3×p+b=ln_3 \times p +b=l，则 (n2×i+n3)×p+b=x(n_2 \times i+n_3) \times p+b=x，所以 b=tb=t。
证完了看怎么构造数组。应该构造为固定第一个数，后面均为其倍数且互不相同。设这个数为 gg，则在 [1,n][1,n] 范围内，有 ⌊ng⌋−1\lfloor \frac{n}{g}\rfloor -1 个 gg 的倍数（除了 gg），除开第一个位置以外，有 k−1k-1 个位置，然后排列变换后的不算多出来的方案。所以对于一个数 gg，贡献值为 (⌊ng⌋−1k−1)\lfloor \frac{n}{g}\rfloor -1 \choose k-1，然后枚举 gg 即可。注意 g≤⌊nk⌋g \le \lfloor \frac{n}{k} \rfloor（你甚至可以用整除分块，但我测下来发现运行时间没多大差别）。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll p=998244353;
const int N=5e5+5;
ll n,k,fac[N],inv[N],ans;
ll power(ll a,ll b) {
	ll res=1;
	while(b) {
		if(b&1) res=res*a%p;
		a=a*a%p,b>>=1;
	}
	return res;
}
ll C(ll x,ll y) {
	return fac[x]*inv[y]%p*inv[x-y]%p;
}
int main() {
	scanf("%lld%lld",&n,&k);
	fac[0]=inv[0]=1ll;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%p,inv[i]=power(fac[i],p-2);
	for(int l=1,r;l<=n/k;l=r+1) {
		r=min(n/(n/l),n/k);
		ans+=(r-l+1)*C(n/l-1,k-1);
	}
	/*
	上面是整除分块。这个等效于下面的代码：
	for(int i=1;i<=n/k;i++) ans+=C(n/i-1,k-1);
	*/ 
	printf("%lld",ans%p);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...