正題

題目鏈接:http://noip.ybtoj.com.cn/contest/102/problem/4

---

題目大意

求有多少個(gè)長(zhǎng)度為$n$的序列$a$滿足$1\le a_i\le 10$，且可以找到一組$(i,j,k,l)$使得$$(\sum _{p=i}^{j?1}{a}_p=x)\&(\sum _{p=j}^{k?1}{a}_p=y)\&(\sum _{p=k}^l{a}_p=z)$$

---

解題思路

題意轉(zhuǎn)化為有沒有一個(gè)$(i,j,k,l)$使得
$$(\sum _{p=i}^j{a}_p=x)\&(\sum _{p=i}^k{a}_p=x+y)\&(\sum _{p=k}^l{a}_p=x+y+z)$$
考慮狀壓，對(duì)于一個(gè)$i$能被表示在集合中當(dāng)且僅當(dāng)滿足序列中有一個(gè)后綴和$i$使得

• $x<i<y$且集合中有一個(gè)$j=x$
• $y<i<z$且集合中有一個(gè)$j=y$

這樣就保證如果集合中有一個(gè)$z$那么一定有一個(gè)劃分$x$和$y$。

預(yù)處理$g_{s,i}$表示狀態(tài)為$s$時(shí)加入一個(gè)$i$能夠到達(dá)的集合
然后設(shè)$f_{i,s}$表示加入到第$i$個(gè)數(shù)時(shí)到達(dá)集合$s$的方案數(shù)

時(shí)間復(fù)雜度$O(2^{x+y+z}(x+y+z)?10+n{2}^{x+y+z}?10)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll M=1<<18,XJQ=1e9+7; ll n,x,y,z,g[M][11],f[45][M]; signed main() {freopen("poem.in","r",stdin);freopen("poem.out","w",stdout);scanf("%lld%lld%lld%lld",&n,&x,&y,&z);y+=x;z+=y;ll MS=(1<<z);for(ll i=1;i<=MS;i++)for(ll j=1;j<=10;j++){g[i][j]=1;if(i==MS){g[i][j]=MS;continue;}for(ll k=0;k<z;k++){if((i>>k&1)&&k+j<=z&&!(k<x&&k+j>x)&&!(k<y&&k+j>y))g[i][j]|=1<<k+j;if(g[i][j]>MS)g[i][j]=MS;}}f[0][1]=1;for(ll i=0;i<n;i++)for(ll j=1;j<=MS;j++){if(!f[i][j])continue;for(ll k=1;k<=10;k++)(f[i+1][g[j][k]]+=f[i][j])%=XJQ;}printf("%lld",f[n][MS]); }

總結(jié)

以上是生活随笔為你收集整理的YbtOJ#20070-[NOIP2020模拟赛B组Day5]诗人小K【状压dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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