题目大意：给你一串有n（n<=75）个0或1组成的串，让你划最多n+1条分割线，第一条分割线的前面和最后一条分割线的后面

不算一段。设剩下的段里面的最大值为max，若1-max都在这些段里面出现过则算一个有效划分，问你总共有多少有效划分，

答案对1e9+7取模。

 

写的时候感觉是个dp，单就是想不出来，看了题解说是状态压缩dp，把出现过哪些数字当做状态，这样才写出来的QAQ。

 

思路：因为n<=75，我们列一下，最大值肯定不会超过20，这样我们就能状态压缩了。

dp[ i ][ j ]表示，最后一条划分线在第 i 个数后面，状态为 j 的划分数。这样我们就可以枚举划分的第一个数，

再枚举这个段的长度k，如果这个段对应的十进制的值为w，那么状态转移方程为 dp[ i + k -1 ] [ j | ( 1 << ( w - 1 ) ) ]+=dp[ i - 1 ][ j ]；

 

#include
      
       #define ll long longusing namespace std;const int N=80;const int M=20;const ll mod=1e9+7;int dp[N][(1<
       
        >n;    for(int i=1;i<=n;i++) scanf("%1d",&a[i]);    for(int i=0;i<=n;i++) dp[i][0]=1;    for(int i=1;i<=n;i++)    {        for(int j=0;j
        
         n) break;                int w=work(i,i+k,k+1);                if(w>20) break;//这里不判断会RE                if(w>=1) dp[i+k][j|(1<<(w-1))]=(dp[i+k][j|(1<<(w-1))]+dp[i-1][j])%mod;            }        }    }    int ans=0;    for(int i=1;i<=n;i++)    {        int now=1;        int p=0;        for(int j=1;j<=20;j++)        {            p+=now;            ans=(ans+dp[i][p])%mod;            now*=2;        }    }    cout<
         
          <