题意：给定一个01串，一个有效的n切割定义如下：一个横杠代表一次切割，第一条横杠前面的01串不算，最后一条横杠后面的01串不算，将两个横杠中的01串转化成十进制数字，假设这些数字的最大值是MAX且这些数字囊括了1-MAX的所有数字，则称为一次有效切割。求2~n+1次有效切割的切法。
思路: 由于题目要求包含所有1—MAXN的数字，且n<=75，所以MAXN<=20。另dp[i][j]表示第i位前面有一个横杆且存在j这个状态，接着从第i位开始枚举到第j位为下一个横杆的位置，设这两段横杆之间的数字为p（十进制），则递推式子为
dp[j+1][k|(1<<p-1)]+=dp[i][k]，k为1～（1<<20）的状态。最后把dp[i][(1<<t)-1]（0<=i<=n，1<=t<=20）加起来就可以了。
1 #include <iostream> 2 #include <queue> 3 #include <stack> 4 #include <cstdio> 5 #include <vector> 6 #include <map> 7 #include <set> 8 #include <bitset> 9 #include <algorithm> 10 #include <cmath> 11 #include <cstring> 12 #include <cstdlib> 13 #include <string> 14 #include <sstream> 15 #include <time.h> 16 #define x first 17 #define y second 18 #define pb push_back 19 #define mp make_pair 20 #define lson l,m,rt*2 21 #define rson m+1,r,rt*2+1 22 #define mt(A,B) memset(A,B,sizeof(A)) 23 #define mod 1000000007 24 using namespace std; 25 typedef long long LL; 26 const double PI = acos(-1); 27 const int N=1e5+10; 28 const int inf = 0x3f3f3f3f; 29 const LL INF=0x3f3f3f3f3f3f3f3fLL; 30 int dp[80][(1<<20)+10]; 31 int a[100]; 32 int main() 33 { 34 #ifdef Local 35 freopen("data","r",stdin); 36 #endif 37 int n,p,ans=0; 38 cin>>n; 39 mt(dp,0); 40 for(int i=0;i<n;i++)scanf("%1d",&a[i]); 41 for(int i=0;i<n;i++) 42 { 43 dp[i][0]=1; 44 for(int k=0;k<(1<<20);k++) 45 { 46 if(!dp[i][k])continue; 47 for(int j=i,p=a[i];j<n&&p<=20;j++,p=((p<<1)+a[j])) 48 { 49 if(p)dp[j+1][k|(1<<p-1)]=(dp[j+1][k|(1<<p-1)]+dp[i][k])%mod; 50 } 51 } 52 } 53 for(int i=0;i<=n;i++) 54 { 55 for(int k=1;k<=20;k++) 56 { 57 ans=(ans+dp[i][(1<<k)-1])%mod; 58 } 59 } 60 cout<<ans<<endl; 61 #ifdef Local 62 cerr << "time: " << (LL) clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl; 63 #endif 64 }