P7435 簡單的排列計數
推歌：Terrasphere
首先沒推過很多大式子的看到題面會暈，不過沒事我們可以它翻譯成可讀題面。
對于一個排列 \({\pi_n}\)，定義其一個逆序對為 \(1\le i<j\le n\) 且 \(\pi_i>\pi_j\) 的二元組 \((i,j)\)，逆序對 \((i,j)\) 的權值為 \(\pi_i\)，排列的權值為所有逆序對權值之積，如果沒有逆序對則為 \(1\)。
給定正整數 \(n,k\)，對于每個 \(0\le m\le k\)，求所有長度為 \(n\)，逆序對數量為 \(m\) 的排列權值之和。
看到這個逆序對可以想到 dp！設 \(dp_{i,j}\) 表示 \(n=i,m=j\) 時的答案。
然后我們考慮轉移時在 \(1\sim i-1\) 中插入 \(i\)，發現對答案的貢獻只和插入的位置有關！所以我們考慮在哪里插入，再乘上多的貢獻，由此得到：
當下標為負時值為 \(0\)。
此時我們發現這個式子就是提高組前兩個題的難度，十分的沒有水平，所以問題肯定不止這么簡單。確實是這樣，因為這個式子是 \(O(nk^2)\) 的，直接運行可以得到 \(13\) 分的高分！
我們開始觀察這個式子，發現是一個卷積，NTT 可以優化，但是啥用沒有。
誒，但是既然想到多項式科技了，那我們可以求一下這一行的 GF？
設第 \(i\) 行的 GF 為 \(F_i(x)\)，根據轉移方程我們有 \(F_i(x)=F_{i-1}(x)\sum_{j=0}^{i-1}i^jx^j\)，看起來還是不怎么優美。
別急！我們發現 \(\sum_{j=0}^{i-1}i^jx^j\) 是一個等比數列求和，這個東西等于 \(\frac{1-i^ix^i}{1-ix}\)。于是最終我們得到了 \(F_i(x)=F_{i-1}(x)\frac{1-i^ix^i}{1-ix}\)，\(F_n(x)=\prod_{i=1}^n\frac{1-i^ix^i}{1-ix}\)，只需要求出這個東西的系數就好了！
但是這個分數很煩人啊！因此直接就是 \(\ln\) 再 \(\exp\) 轉成求和，變成：
我們發現 \(\sum_{i=1}^n\ln(1-i^ix^i)\) 怎么這么熟悉呢？這不是經典背包 P4389 嘛！所以這一部分就變成 \(-\sum_{i=1}^n\sum_{j=1}\frac{(ix)^{ij}}{j}\)，跑一遍調和級數就好了。
接下來開始展開后半部分：
\(B_i\) 為伯努利數第 \(i\) 項，直接求系數即可。
然后 \(\exp\) 一次就回去了，完結撒花！
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int ksm(int a,int q){
int res=1;
while(q){
if(q&1)res=res*a%mod;
a=a*a%mod;
q>>=1;
}
return res;
}
int Ceilb(int x){
while(x&x-1)x+=x&-x;
return x;
}
const int iG=ksm(3,mod-2);
int r[1<<20];
int A[1<<20],B[1<<20],D[1<<20],C[1<<20],E[1<<20];
void init(int n){
int lim=1,l=-1;
while(lim<=n)lim<<=1,l++;
for(int i=1;i<lim;i++)r[i]=(r[i>>1]>>1)|((i&1)<<l);
}
void NTT(int lim,int *a,int opt){
//NTT
}
void mult(int n,int m,int *a_tmp,int *b_tmp,int *ans,int tn=-1){
//ans=a_tmp*b_tmp
}
void INV(int n,int *p,int *ans){
//ans=1/p
}
void ln(int cnt,int *p,int *ans){
//ans=ln(p)
}
void exp(int cnt,int *p,int *ans){
//ans=exp(p)
}
int fac[200005],ifac[200005];
int p1[1<<20],p2[1<<20],p3[1<<20],p4[1<<20];
signed main(){
int n,k;
cin>>k>>n;
fac[0]=1;
for(int i=1;i<=n+1;i++)fac[i]=fac[i-1]*i%mod;
ifac[n+1]=ksm(fac[n+1],mod-2);
for(int i=n+1;i;i--)ifac[i-1]=ifac[i]*i%mod;
for(int i=0;i<=n;i++)p1[i]=ksm(k+1,i+1)*ifac[i+1]%mod,p2[i]=ifac[i+1];
INV(n+1,p2,p3),mult(n+1,n+1,p3,p1,p1);
for(int i=1;i<=n;i++)p1[i]=p1[i]*fac[i-1]%mod;
p1[0]=0;
for(int i=1;i<=min(n,k);i++){
int tmp=ksm(i,i);
int mi=tmp;
for(int j=1;j*i<=n;j++)
p1[i*j]=(p1[i*j]+mod-fac[j-1]*ifac[j]%mod*mi%mod)%mod,mi=mi*tmp%mod;
}
for(int i=n+1;i<=2*n;i++)p1[i]=0;
exp(n+1,p1,p4);
for(int i=0;i<=n;i++)cout<<p4[i]<<' ';
return 0;
}
浙公網安備 33010602011771號