CF1359E
DDF_
·
·
题解
题面
有一个长度为 k 的序列，不管他怎么排列变换，对于任意的自然数 x，满足 s=(((x \bmod a_1) \bmod a_2) \bmod \cdots \bmod a_{k}) 为定值。
求序列所有元素不大于 n 且序列元素互不相同的方案数，一个序列通过排列变换得到的序列不算一个新的序列。
题解
题目里给的是 1 \le a_1 < a_2 < \cdots < a_k \le n，我换成了序列元素互不相同，因为一个显然的结论：当序列为如上的形式时，s=x \bmod a_1，s 只由 a_1 决定。而要证明这个序列的合法性，肯定要倒过来，n \ge a_{k} > a_{k-1} > a_{k-2} > \cdots > a_1 \ge 1，这时候 s 就会受到数组中其他数的影响了。
然后把上面两种情况取一下，要有当序列倒过来时 s=x \bmod a_k。
猜结论环节。先猜一下所有数都是 a_{k} 的倍数，然后把 a_k=2 和 a_k=3 代入发现还真行（考试时到这一步就可以打代码了）。
但是这里是题解，所以我要证明（呜呜呜）。设 p=a_k，t=x \bmod p，然后有一个正整数 i，令 l=x \bmod (p \times i)，b=l \bmod p，则要证明 b =t。
证完了看怎么构造数组。应该构造为固定第一个数，后面均为其倍数且互不相同。设这个数为 $g$，则在 $[1,n]$ 范围内，有 $\lfloor \frac{n}{g}\rfloor -1$ 个 $g$ 的倍数（除了 $g$），除开第一个位置以外，有 $k-1$ 个位置，然后排列变换后的不算多出来的方案。所以对于一个数 $g$，贡献值为 $\lfloor \frac{n}{g}\rfloor -1 \choose k-1$，然后枚举 $g$ 即可。注意 $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;
}
```