題目鏈接

https://codeforces.com/contest/1188/problem/E

題解

我們可以發(fā)現(xiàn)，題目要求數(shù)的目標(biāo)狀態(tài)的個(gè)數(shù)，實(shí)際上就是在數(shù)操作序列（指每個(gè)氣球操作的次數(shù)構(gòu)成的序列，第 \(i\) 個(gè)顏色操作 \(b_i\) 次）的個(gè)數(shù)。可以發(fā)現(xiàn)如果給定了操作序列，每次一定是操作那個(gè)剩下的 \(a_i\) 最小的。那么對(duì)于一個(gè)合法序列 \(b\)，將其每個(gè)元素減去 \(1\) 后一定合法，且得到的序列不變。那么我們可以通過(guò)強(qiáng)制至少一個(gè) \(b_i=0\) 來(lái)保證不算重。
然后我就卡住了。。。。。手動(dòng)再見(jiàn)
考慮每種顏色對(duì)序列合法的限制，就是對(duì)每個(gè) \(i\)，前 \(a_i+mk+1 (m=0,1,2,...)\) 次操作至少要有一次操作 \(i\). 那么從小到大枚舉操作總數(shù) \(s\) (\(0\le s\le \max a_i\))，我們可以得到某些必須進(jìn)行的操作，剩余的操作分配給 \(k\) 種顏色，使用插板法計(jì)算。為了保證存在 \(b_i=0\)，再減去強(qiáng)制給每個(gè)未出現(xiàn)限制的 \(b_i\) 都 \(+1\) 的方案數(shù)。
時(shí)間復(fù)雜度 \(O(k+\max a_i)\).

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define iter iterator #define riter reversed_iterator #define y1 Lorem_ipsum_dolor using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int mxN = 1e6; const int P = 998244353; llong fact[mxN*2+3],facti[mxN*2+3]; int a[mxN+3]; int cnt[mxN+3],cnt2[mxN+3]; int n,mx;llong quickpow(llong x,llong y) {llong cur = x,ret = 1ll;for(int i=0; y; i++){if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}cur = cur*cur%P;}return ret; } llong comb(llong x,llong y) {return x<0||y<0||x<y?0ll:fact[x]*facti[y]%P*facti[x-y]%P;}void updsum(llong &x,const llong y) {x = x+y>=P?x+y-P:x+y;}void initfact(int n) {fact[0] = 1ll; for(int i=1; i<=n; i++) fact[i] = fact[i-1]*i%P;facti[n] = quickpow(fact[n],P-2); for(int i=n-1; i>=0; i--) facti[i] = facti[i+1]*(i+1ll)%P; }int main() {initfact(mxN*2);n = read();for(int i=1; i<=n; i++) a[i] = read(),mx = max(mx,a[i]);for(int i=1; i<=n; i++){for(int j=a[i]+1; j<=mx; j+=n) {cnt[j]++;} cnt2[a[i]+1]++;}llong ans = 0ll;for(int i=0,j=0,k=n; i<=mx; i++,j++){j-=cnt[i],k-=cnt2[i]; // printf("i=%d j=%d k=%d\n",i,j,k);if(j<0) break;llong tmp = comb(j+n-1,n-1);updsum(ans,tmp);if(j-k>=0){llong tmp = comb(j-k+n-1,n-1);updsum(ans,P-tmp);}}printf("%I64d\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces 1188E Problem from Red Panda (计数)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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