Guest User

Untitled

a guest
May 10th, 2020
222
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. const ll MOD = 1e9 + 7;
  6. const int MAXN = 1100;
  7.  
  8. int N;
  9. string S;
  10. int cv[MAXN];
  11. vector <int> nswap[MAXN];
  12. int cbad;
  13.  
  14. void sswap (int x)
  15. {
  16.     // swap x, x + 1)
  17.     if (cv[x] + (int) S[x] == (int) '1')
  18.         cbad--;
  19.     if (cv[x+1] + (int) S[x+1] == (int) '1')
  20.         cbad--;
  21.     swap (cv[x], cv[x+1]);
  22.     if (cv[x] + (int) S[x] == (int) '1')
  23.         cbad++;
  24.     if (cv[x+1] + (int) S[x+1] == (int) '1')
  25.         cbad++;
  26. }
  27.  
  28. ll figure (int n1)
  29. {
  30.     for (int i = 0; i < N; i++)
  31.     {
  32.         cv[i] = 0;
  33.         nswap[i].clear();
  34.     }
  35.     int n0 = N - n1;
  36.     // 1s are +n0, 0s are -n1
  37.  
  38.     int cs = 0;
  39.     for (int i = 0; i < S.length(); i++)
  40.     {
  41.         if (cs + n0 < N)
  42.         {
  43.             cv[i] = 1;
  44.             cs += n0;
  45.         }
  46.         else
  47.         {
  48.             cv[i] = 0;
  49.             cs -= n1;
  50.         }
  51.         nswap[cs].push_back(i);
  52.     }
  53.  
  54.     cbad = 0;
  55.     for (int i = 0; i < N; i++)
  56.     {
  57.         if (cv[i] + (int) S[i] == (int) '1')
  58.             cbad++;
  59.     }
  60.  
  61.     int res = 0;
  62.     if (!cbad) res++;
  63.     for (int i = N - 1; i > 0; i--)
  64.     {
  65.         if (!nswap[i].size()) continue;
  66.         for (int j : nswap[i])
  67.             sswap (j);
  68.         if (!cbad) res++;
  69.     }
  70.     return res;
  71. }
  72.  
  73. void gogo()
  74. {
  75.     cin >> S;
  76.     N = S.length();
  77.  
  78.     ll ans = 0;
  79.     bool b0 = true, b1 = true;
  80.     for (int i = 0; i < N; i++)
  81.     {
  82.         if (S[i] == '0') b1 = false;
  83.         if (S[i] == '1') b0 = false;
  84.     }
  85.     if (b0) ans++;
  86.     if (b1) ans++;
  87.  
  88.     for (int i = 1; i < N; i++)
  89.         ans = (ans + figure (i)) % MOD;
  90.     cout << ans << "\n";
  91. }
  92.  
  93. int main()
  94. {
  95.     ios_base::sync_with_stdio(0);
  96.  
  97.     int T; cin >> T;
  98.     for (int t = 0; t < T; t++)
  99.     {
  100.         gogo();
  101.     }
  102. }
RAW Paste Data