fork(11) download 
  1. #include "bits/stdc++.h"
  2. #define ll long long
  3. using namespace std;
  4. #define check(x)                cerr << #x << ": " << x << endl;
  5. #define print(ans)              cout << ans << endl;
  6. int main(){
  7.   ios_base::sync_with_stdio(false);
  8.   cin.tie(NULL);
  9.   int t;
  10.   cin >> t;
  11.   while(t--){
  12. 	  int n;
  13. 	  const int mod = 1e9 + 7;
  14. 	  cin >> n;
  15. 	  string s;
  16. 	  cin >> s;
  17. 	  int dp[n+2];
  18. 	  int last1 = -1 , last0 = -1;
  19. 	  memset(dp,0,sizeof dp);
  20. 	  dp[0] = 1;
  21. 	  for(int i = 1;i<=n;i++){
  22. 	    int x = (s[i-1] - '0');
  23. 	    dp[i] = (dp[i-1] * 2)%mod;
  24. 	    if(x){
  25. 	      if(last1 != -1)
  26. 	        dp[i] -= dp[last1 - 1];
  27. 	        dp[i] = (dp[i] + mod)%mod;
  28. 	      last1 = i;
  29. 	    } else {
  30. 	      if(last0 != -1){
  31. 	        dp[i] -= dp[last0 - 1];
  32. 	        dp[i] = (dp[i] + mod)%mod;
  33. 	      } else {
  34. 	        dp[i] -= 1;
  35. 	        dp[i] = (dp[i] + mod)%mod;
  36. 	      }
  37. 	      last0 = i;
  38. 	    }
  39. 	  }
  40. 	  if(last0==-1)
  41. 	  {
  42. 	  	dp[n] -= 1;
  43. 	  	dp[n] += mod;
  44. 	  	dp[n] %= mod;
  45. 	  }
  46. 	  cout << dp[n]<<endl;
  47.  
  48.   }
  49.   cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << "\n";
  50.   return 0;
  51. }
Success #stdin #stdout #stderr 0s 5572KB
comments (?)
stdin 
1
4
1111
stdout 
4
stderr 
time taken : 0.004096 secs
https://ideone.com/qfiJt3
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

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!