正題

題目鏈接:https://www.luogu.com.cn/problem/P6672

---

題目大意

長(zhǎng)度為$m$的序列$a$，有$n$個(gè)數(shù)字不是$0$，其他$m?n$個(gè)是$0$。要求重排后有多少方案滿足
$$?x,\sum _{i=1}^x{a}_i\ge i$$
其中$m={\sum }_{i=1}^n{a}_i$

$1\le n\le 40,1\le a_i\le 10^5$

---

解題思路

具體數(shù)學(xué)P301頁有一個(gè)$Reney$引理（雖然我還沒看到）：
假設(shè)一個(gè)整數(shù)序列何為$1$，那么它的所有循環(huán)位移中有且僅有一個(gè)滿足所有的前綴和為$+1$

然后考慮這題，都減去一的話就是要求都為非負(fù)了，而且所有數(shù)的和為$0$。

怎么轉(zhuǎn)換成上面那種情況，加一個(gè)進(jìn)去$1$的話不是很行，因?yàn)橛泻芏嗾龜?shù)所以我們不能保證這個(gè)$1$排在最前面。

反著考慮，把所有數(shù)取反再加一個(gè)$1$的話就可以了，因?yàn)檫@樣正數(shù)就只有$1$了。

所以的話它的圓排列個(gè)數(shù)就是$m!$個(gè)了，但是多了一個(gè)$?1$我們要減去這個(gè)$?1$的影響，其實(shí)就是多塞一個(gè)$?1$進(jìn)去的話，就是多了$m?n+1$個(gè)了。所以答案就是
$$\frac{m!}{m?n+1}$$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll P=998244353; ll n,m,ans; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } signed main() {scanf("%lld",&n);for(ll i=1;i<=n;i++){ll x;scanf("%lld",&x);m+=x;}ans=1;for(ll i=1;i<=m;i++)ans=ans*i%P;printf("%lld\n",ans*power(m-n+1,P-2)%P);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P6672-[清华集训2016]你的生命已如风中残烛【结论】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。