tupc2024_o Twin Contests
题意
给定正整数 \(n\)，对于每个 \(i\in [1,n]\)，求出：
有多少长度为 \(n\) 的排列 \(p\)，满足 \(\forall j\in [1,n]\) 且 \(j\neq i\)，都有 \(i\times p_i < j\times p_j\)。
\(n\le 5\times 10^5\)。
题解
知识点：排列组合。
不错的组合数学。
先考虑一个子问题：
给定整数 \(s\)，求出有多少长度为 \(n\) 的排列 \(p\)，满足 \(\forall i\in [1,n]\)，都有 \(i\times p_i\ge s\)。
把上述问题答案记为 \(A(s)\)。
注意到有一个不同，这个问题是大于等于号，而原问题是大于号，这没什么特别的，纯粹是因为这样写好推式子。
将限制进行移项得到 \(p_i\ge \frac{s}{i}\)，所以排列的第 \(i\) 项必须 \(\ge \frac{s}{i}\)，这个限制随着 \(i\) 的增加会越来越松。
记满足 \(d\in [1,n]\) 且 \(d\ge \frac{s}{i}\) 的正整数 \(d\) 个数为 \(g(i,s)\)。
可以尝试推理一下 \(g(i,s)\) 的表达式：
那么可以得到 \(\displaystyle A(s)=\prod_{i=1}^{n} (g(i,s)-i+1)=\prod_{i=1}^{n} (n-\lfloor \frac{s-1}{i}\rfloor-i+1)\)，由于限制随着 \(i\) 的增加会越来越松，先为 \(i\) 小的选后为 \(i\) 大的选，这样是不会数漏的。
容易发现一个关键结论，排列中最小的 \(i\times p_i\le n\)，稍微放缩一下，当 \(i=1\) 时，就有 \(p_i\le n\) 了。
记 \(ans_i\) 为 \(i\times p_i\) 最小的答案。
上面的结论很好地限定了 \(i\times p_i\) 的范围，那么考虑枚举 \(i\times p_i\)。
则 \(\displaystyle ans_i=\sum_{s=1}^n [i|s]\frac{A(s+1)}{g(i,s+1)-i+1}\)。
为什么是 \(s+1\)，因为题目的限制是严格大于，而这里设定的都是大于等于。
除以 \(g(i,s+1)-i+1\)，表示第 \(i\) 项不参与选定，要去掉这里贡献的方案数，因为在这里直接钦定了 \(p_i\) 为 \(\frac{s}{i}\)。
仔细思考可能会有一些疑问，为什么直接除去就是对的呢？如果所钦定的 \(p_i\) 是 \(p_1\sim p_{i-1}\) 也能选的呢？那不应该在他们那里的选法贡献减去 \(1\) 吗？
实际上是不会有这种情况的，因为传入的参数是 \(s+1\)，有 \(\forall j\in[1,i),p_j > \frac{s}{j}\)，而钦定的 \(p_i\) 是 \(\frac{s}{i}<\frac{s}{j}\)，前面的数是无论如何也没机会取到的，所以不存在上面的问题。
对于每个 \(s\in[1,n+1]\)，暴力计算 \(A(s)\)，就可以得到一个 \(O(n^2)\) 的做法，考虑优化。
\(A(s)\) 和 \(g(s,i)\) 有关，观察到随着 \(i\) 的增加，\(g(s,i)\) 相较 \(i-1\) 发生了变化，当且仅当 \(i|s\)，其他情况直接继承 \(i-1\) 的值即可。
所以总变化次数是 \(O(\displaystyle\sum_{i=1}^n \frac{n}{i})=O(n\log n)\) 的。
那就考虑用一个筛法状物，筛出每个 \(s\in [1,n+1]\) 的约数，那么 \(A(s)\) 相对 \(A(s-1)\) 只有他的约数所对应的 \(g(i,s)\) 发生变化。
那就可以做到 \(O(n \log n)\) 的时间复杂度。
#include<bits/stdc++.h>
using namespace std;#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()#define N 502507
#define int long longconst int mod=998244353;int n,iv[N],a[N];
vector<int>e[N];inline int inv(int a){int ans=1,b=mod-2;while(b){if(b&1){ans=ans*a%mod;}a=a*a%mod;b>>=1;}return ans;
}inline void init(int lim){rep(i,1,lim){int j=1;while(j*i<=lim){e[j*i].pb(i);j++;}}
}signed main(){// freopen(".in","r",stdin);// freopen(".out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;if(n==1){cout<<1;return 0;}rep(i,0,n){iv[i]=inv(i);}init(5e5+10);a[1]=1;rep(i,1,n){a[1]=a[1]*(n-i+1)%mod;}rep(i,2,n+1){a[i]=a[i-1];for(int x:e[i-1]){a[i]=a[i]*iv[n-(i-2)/x-x+1]%mod*(n-(i-1)/x-x+1)%mod;}}rep(i,1,n){int s=i,ans=0;while(s<=n){ans=(ans+a[s+1]*iv[n-s/i-i+1]%mod)%mod;s+=i;}cout<<ans<<"\n";}return 0;
}