Codeforce 294 C. Shaass and Lights 解析(思維、組合)

今天我們來看看CF294C
題目連結

題目
給你$n$個燈泡，其中$m$個已經點亮。每次你可以點亮一個旁邊有亮燈泡的燈泡，求有多少方法可以點亮所有燈泡。

前言

這題的想法真的很酷炫

想法

把每個連續沒亮燈泡的區域當成一種元素(也就是說:暗暗暗亮暗暗暗亮暗暗暗，這種情況就看成$AAABBBCCC$)，如此一來重複排列的可能性是$\frac{9!}{3!3!3!}$，而只要區段不是接壤頭或接壤尾，其中長度為$k$的沒亮燈泡區段其中有$k-1$次都有兩種選擇，因此答案只要再乘上$2$的若干次方即可。

程式碼:

const int _n=1010;  
int t,n,m,a[_n],fac[_n],inv[_n],c;  
VI cnt;  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n>>m;rep(i,0,m){cin>>t;a[t]=1;}  
  a[n+1]=1;rep(i,1,n+2){  
    if(a[i]==1 and c)cnt.pb(c),c=0;  
    if(a[i]==0)c++;  
  }c=0;if(a[1]==0)c+=cnt[0]-1;if(a[n]==0)c+=cnt.back()-1;  
  fac[0]=1;rep(i,1,n+1)fac[i]=1ll*fac[i-1]*i%mod;  
  inv[n]=powmod(fac[n],mod-2);per(i,0,n)inv[i]=1ll*inv[i+1]*(i+1)%mod;  
  ll ans=fac[n-m];rep(i,0,SZ(cnt))ans=ans*inv[cnt[i]]%mod;  
  ans=ans*powmod(2,n-m-SZ(cnt)-c)%mod;cout<<ans<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission