original: http://codeforces.com/problemset/problem/757/D
question:
Give you a 01 string, you need to select a substring, and next, divide the substring into segments. Every segment is converted to its corresponding decimal number.
Define the maximum to be “X”. A division is considered legal If and only if all numbers are positive and every number in [ 1 , X ] [1,X] [1,X] appear once at least.
Please print the total number of legal divisions of all substrings.
analyze:
We could consider state compression. Let d p [ i ] [ j ] dp[i][j] dp[i][j] be the number that end at i i i and state is j j j.
Let value in [ l , r ] [l,r] [l,r] is v v v, so we can do: d p [ l − 1 ] [ S ] → d p [ r ] [ S ∣ ( 1 < < v − 1 ) ] dp[l-1][S]\to dp[r][S|(1<<v-1)] dp[l−1][S]→dp[r][S∣(1<<v−1)]
#include<bits/stdc++.h> using namespace std; #define LL long long const int mod=1e9+7; const int maxn=(1<<20)+5; char x[100]; int dp[100][maxn]; int val[100][100]; int main(){ int n;scanf("%d",&n); scanf("%s",x+1); for(int len=1;len<=n;len++){ for(int i=1;i+len-1<=n;i++){ if(len==1){ val[i][i]=x[i]-'0'; } else{ val[i][i+len-1]=val[i][i+len-2]*2+x[i+len-1]-'0'; } } } memset(dp,0,sizeof dp); for(int i=0;i<n;i++){ dp[i][0]=(dp[i][0]+1)%mod; for(int j=0;j<(1<<20)-1;j++){ if(dp[i][j]==0)continue; for(int k=i+1;k<=n;k++){ if(val[i+1][k]==0)continue; if(val[i+1][k]>20)break; dp[k][j|(1<<(val[i+1][k]-1))]+=dp[i][j]; dp[k][j|(1<<(val[i+1][k]-1))]%=mod; } } } LL ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=20;j++){ if(dp[i][(1<<j)-1]>0) ans=(ans+dp[i][(1<<j)-1])%mod; } } printf("%lld\n",ans); }