fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. typedef long long ll;
  4.  
  5. using namespace std;
  6. const int N = 55;
  7. int test_no = 0; 
  8. int n;
  9. int dp[N][N];
  10. int vis[N][N]; 
  11. string s; 
  12. vector<ll> pref; 
  13. vector<ll> suf; 
  14. ll M = 1e9 + 7; 
  15.  
  16. ll solve(int l, int r){
  17. if(l >= r) return 1ll; 
  18. if(l == (r - 2)) return 1ll;
  19. if(vis[l][r]== test_no) 
  20.     return dp[l][r]; 
  21. vis[l][r] = test_no; 
  22.  
  23. ll ans = 1ll; 
  24. //cout<<" -> "<<l<<" "<<r<<endl;
  25. for(int i = l + 1; i < r ; i++){
  26.       for(int j = (r - 1); j > i ; j--){
  27.             ll suml = pref[i] - pref[l]; 
  28.             ll sumr = suf[j] - suf[r]; 
  29.             if(suml == sumr) ans = (ans + solve(i,j))%M; 
  30.       }
  31. }
  32. //cout<<"for : "<<l<<" "<<r<<" ans: "<<ans<<endl;
  33. return dp[l][r] = ans; 
  34. }
  35. int main() {
  36. 	ios_base::sync_with_stdio(false);
  37. 	cin.tie(NULL); cout.tie(NULL);
  38.  
  39.  
  40. 	memset(dp,-1,sizeof(dp));
  41. 	int t; cin>>t; 
  42.     while(t--){
  43.        test_no++; 
  44.        cin>>s; n = s.length(); 
  45.        pref.clear(); pref.resize(n+2,0); 
  46.        suf.clear(); suf.resize(n+2,0); 
  47.        for(int i = 1 ; i <=n; i++) 
  48.           pref[i] = pref[i- 1] + (s[i-1] - '0'); 
  49.        pref[n+1] = pref[n]; 
  50.        for(int i = n; i>=1;i--) 
  51.            suf[i] = suf[i + 1] + (s[i - 1] - '0'); 
  52.        suf[0] = suf[1]; 
  53.        cout<<solve(0, n + 1)<<endl; 
  54.     }
  55.  
  56. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4
1001
00
0110
1
stdout
copy 
8
2
4
1
https://ideone.com/gs2oAd
language:
C++ (gcc 8.3)
created:
4 seconds ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!