2024.10.7 鮮花
【UNR #3】百鴿籠
花の塔
君が持ってきた漫畫
くれた知らない名前のお花
今日はまだ來ないかな?
初めての感情知ってしまった
窓に飾った絵畫をなぞってひとりで宇宙を旅して
それだけでいいはずだったのに
君の手を握ってしまったら
孤獨を知らないこの街には
もう二度と帰ってくることはできないのでしょう
君が手を差し伸べた 光で影が生まれる
歌って聞かせて この話の続き
連れて行って見たことない星まで
誰の手も聲も屆かない
高く聳え立った塔の上へ
飛ばすフウセンカズラ
僕は君に笑って欲しいんだ
満たされない穴は惰性の會話や澄ましたポーズで
これまでは埋めてきたけど
退屈な日々を蹴散らして
君と二人でこの街中を泳げたら
それはどれだけ素敵なことでしょう?
出したことないほど大きな聲でやっと君に伝わる
歪なくらいがさ きっとちょうどいいね
世界の端と端を結んで
窓に飾った絵畫をなぞってひとりで宇宙を旅して
それだけでも不自由ないけど
僕は選んでみたいの
高鳴る心 謎だらけの空を
安全なループを今、書き換えて!
君の手を握ってしまったら
孤獨を知らないこの街にはもう二度と
帰ってくることはできないのでしょう
いくらでも迷いながら光も影も見に行こう
歌って聞かせてこの話の続き
連れて行って見たことない星まで
世界の端と端を結んで

愿天堂沒有疾病和傷痛
好題。
首先轉化,每次從還有剩余的籠中選實在抽象,考慮可以繼續放進去,只是沒有貢獻。
于是將題面轉化為:給定一個無限長的序列,其元素是每堆鴿籠編號,對于每個 \(i\in[1,n]\),求對于所有 \(j\not=i\),第 \(a_j\) 個 \(j\) 出現在第 \(a_i\) 個 \(i\) 之前的概率(其實是每個 \(i\) 從中選出前 \(a_i\) 個組成鴿籠)。
設當前處理的鴿籠編號為 \(i\)。
考慮容斥,枚舉子集,設 \(f(S)\) 為恰好 \(S\) 的集合出現在 \(a_i\) 之后的概率,\(g(S)\) 為欽定(至少),有。
考慮求 \(g(S)\),設 \(dp_{i,j}\) 表示從 \(S\) 中選到前 \(i\) 個,一共長度為 \(j\) 的方案數,枚舉第 \(i\) 個選 \(k\) 個,背包顯然轉移。
因為是有序的,記得在轉移時乘上 \(\frac{1}{k!}\),乘上 \(j!\),還要記得乘上 \(a_i-1\) 的插板。
有了方案數,概率顯然是 \(\sum\limits_i \frac{dp_{n,i}}{n^i}\)。
這樣已經有了 \(30pts\) 做法。
考慮去掉指數,考慮轉移過程,發現其只和 \(|S|\) 有關,考慮多加一位 \(dp_{l,i,j}\) 表示一共選了 \(l\) 堆籠子,枚舉第 \(l\) 個是否選和選了多少來轉移(相當于是把 \(|S|\) 相同的一起轉移),依然是類似背包轉移。
這里已經是 \(n^6\) 的做法了,但是不好過,考慮經典 trick 可退回背包,可以做到 \(n^5\)。
Code
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
FILE *InFile=stdin,*OutFile=stdout;
#endif
const int N=33,MOD=998244353;
int c[N],n,m,fac[N*N],ivf[N*N],dp[N][N*N];
int Fpw(int a,int b){
int ans=1;
while(b){
if(b&1) ans=1ll*ans*a%MOD;
a=1ll*a*a%MOD,b>>=1;
}
return ans;
}
int Inv(int a){return Fpw(a,MOD-2);}
int C(int a,int b){return 1ll*fac[a]*ivf[b]%MOD*ivf[a-b]%MOD;}
void Del(int i){
for(int l=1;l<=n;++l) for(int j=0;j<=m;++j) for(int k=0;k<=min(j,c[i]-1);++k)
dp[l][j]=(dp[l][j]-1ll*dp[l-1][j-k]*ivf[k]%MOD+MOD)%MOD;
}
void Add(int i){
for(int l=n;l;--l) for(int j=m;j>=0;--j) for(int k=0;k<=min(j,c[i]-1);++k)
dp[l][j]=(dp[l][j]+1ll*dp[l-1][j-k]*ivf[k])%MOD;
}
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n; for(int i=1;i<=n;++i) cin>>c[i],m+=c[i];
fac[0]=1; for(int i=1;i<=m;++i) fac[i]=1ll*fac[i-1]*i%MOD;
ivf[m]=Inv(fac[m]); for(int i=m;i;--i) ivf[i-1]=1ll*ivf[i]*i%MOD;
dp[0][0]=1; for(int i=1;i<=n;++i) Add(i);
for(int nw=1;nw<=n;++nw){
Del(nw); int ans=0;
for(int j=0;j<n;++j){
int tmp=0;
for(int k=0;k<=m-c[nw];++k) tmp=(tmp+1ll*dp[j][k]*fac[k]%MOD*C(c[nw]+k-1,k)%MOD*Inv(Fpw(j+1,k+c[nw]))%MOD)%MOD;
ans=((ans+tmp*((j&1)?-1:1))%MOD+MOD)%MOD;
}
cout<<ans<<' ';
Add(nw);
}
}
圖,話說為什么這么多人喜歡用多個折疊,這個東西可以直接 F12 一鍵展開的 QwQ

本文來自博客園,作者:xrlong,轉載請注明原文鏈接:http://www.rzrgm.cn/xrlong/p/18450573
版權聲明:本作品采用 「署名-非商業性使用-相同方式共享 4.0 國際」許可協議(CC BY-NC-SA 4.0) 進行許可。

浙公網安備 33010602011771號