fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <chrono>
  3. // #include <sys/resource.h>
  4. // #include <ext/pb_ds/assoc_container.hpp>
  5. // #include <ext/pb_ds/tree_policy.hpp>
  6. // using namespace chrono;
  7. // using namespace __gnu_pbds;
  8. using namespace std;
  9.  
  10.  
  11. // Type aliases
  12. using lli = long long int;
  13. using ld = long double;
  14. using ll = long long;
  15. using vlli = vector<lli>;
  16. using vll = vector<ll>;
  17.  
  18. // Macros
  19. #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
  20. #define PRINT_YES cout << "YES\n"
  21. #define PRINT_NO cout << "NO\n"
  22. #define endl "\n"
  23. #define loop(i,t) for (lli i=0;i<t;i++)
  24. #define st(v) sort(v.begin(), v.end())
  25. #define rev(v) reverse(v.begin(), v.end())
  26. #define input(v, n) for (lli i = 0; i < n; ++i) { cin >> v[i]; }
  27. #define DEBUG(x) cerr << #x << ": " << x << endl
  28. #ifndef ONLINE_JUDGE
  29. #define DEBUG_PRINT(x) cerr << #x << ": " << x << endl
  30. #else
  31. #define DEBUG_PRINT(x)
  32. #endif
  33.  
  34. // Constants
  35. const long double PI = 3.141592653589793238L;
  36. const long long MOD = 1e9 + 7;
  37. const long long INF=3e18+20;
  38.  
  39. // Linked List
  40. struct Node{
  41. 	int data;
  42. 	Node* next;
  43.  
  44. 	Node(int data){
  45. 		this->data = data;
  46. 		this->next= nullptr;
  47. 	}
  48. };
  49.  
  50. class LinkedList{
  51.  
  52. private:
  53. 	Node* head;
  54.  
  55. public:
  56. // Function to add a new node to the end of the list
  57. 	void append(int data){
  58. 		Node* newNode= new Node(data);
  59. 		if(head==nullptr){
  60. 			head=newNode;
  61. 		}
  62. 		else{
  63. 			Node* temp=head;
  64. 			while(temp->next != nullptr){
  65. 				temp=temp->next;
  66. 			}
  67. 			temp->next=newNode;
  68. 		}
  69. 	}
  70. // Function to print all nodes in the list
  71. 	void printList(){
  72. 		Node* temp=head;
  73. 		while(temp!=nullptr){
  74. 			cout<<temp->data<<"->";
  75. 			temp=temp->next;
  76. 		}
  77. 		cout<<"Null pointer"<<endl;		
  78. 	}
  79. // Function to delete the entire list and free memory
  80. 	~LinkedList(){
  81. 		Node*current=head;
  82. 		Node*nextNode;
  83. 		while(current!=nullptr){
  84. 			nextNode=current->next;
  85. 			delete current;
  86. 			current=nextNode;
  87. 		}
  88. 		head=nullptr;
  89. 	}
  90. };
  91.  
  92. // Segment Tree
  93. class SegmentTree {
  94.     vector<lli> seg, lazy;
  95.     lli n;
  96.  
  97. public:
  98.     SegmentTree(lli size) : n(size) {
  99.         seg.assign(4 * n + 1, 0);
  100.         lazy.assign(4 * n + 1, 0);
  101.     }
  102.  
  103.     void buildtree(const vector<lli>& arr, lli i, lli low, lli high) {
  104.         if (low == high) {
  105.             seg[i] = arr[low];
  106.             return;
  107.         }
  108.         lli mid = low + (high - low) / 2;
  109.         buildtree(arr, 2 * i + 1, low, mid);
  110.         buildtree(arr, 2 * i + 2, mid + 1, high);
  111.         seg[i] = seg[2 * i + 1] + seg[2 * i + 2];
  112.     }
  113.  
  114.     lli query(lli ind, lli l, lli r, lli low, lli high) {
  115.         if (lazy[ind] != 0) {
  116.             seg[ind] += (high - low + 1) * lazy[ind];
  117.             if (low != high) {
  118.                 lazy[2 * ind + 1] += lazy[ind];
  119.                 lazy[2 * ind + 2] += lazy[ind];
  120.             }
  121.             lazy[ind] = 0;
  122.         }
  123.         if (high < l || low > r) return 0;
  124.         if (high <= r && low >= l) return seg[ind];
  125.         lli mid = low + (high - low) / 2;
  126.         lli left = query(2 * ind + 1, l, r, low, mid);
  127.         lli right = query(2 * ind + 2, l, r, mid + 1, high);
  128.         return left + right;
  129.     }
  130.  
  131.     void update(lli i, lli val, lli low, lli high, lli ind) {
  132.         if (low == high) {
  133.             seg[ind] = val;
  134.             return;
  135.         }
  136.         lli mid = low + (high - low) / 2;
  137.         if (i <= mid) update(i, val, low, mid, 2 * ind + 1);
  138.         else update(i, val, mid + 1, high, 2 * ind + 2);
  139.         seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
  140.     }
  141.  
  142.     void updaterange(lli l, lli r, lli val, lli low, lli high, lli ind) {
  143.         if (lazy[ind] != 0) {
  144.             seg[ind] += (high - low + 1) * lazy[ind];
  145.             if (low != high) {
  146.                 lazy[2 * ind + 1] += lazy[ind];
  147.                 lazy[2 * ind + 2] += lazy[ind];
  148.             }
  149.             lazy[ind] = 0;
  150.         }
  151.         if (high < l || low > r) return;
  152.         if (high <= r && low >= l) {
  153.             seg[ind] += (high - low + 1) * val;
  154.             if (low != high) {
  155.                 lazy[2 * ind + 1] += val;
  156.                 lazy[2 * ind + 2] += val;
  157.             }
  158.             return;
  159.         }
  160.         lli mid = low + (high - low) / 2;
  161.         updaterange(l, r, val, low, mid, 2 * ind + 1);
  162.         updaterange(l, r, val, mid + 1, high, 2 * ind + 2);
  163.         seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
  164.     }
  165. };
  166.  
  167. // Disjoint Set (Union-Find)
  168. class DisjointSet {
  169.     vector<lli> rank, parent, size;
  170.  
  171. public:
  172.     DisjointSet(lli n) : rank(n + 1, 0), parent(n + 1), size(n + 1, 1) {
  173.         iota(parent.begin(), parent.end(), 0);
  174.     }
  175.  
  176.     void UnionByRank(lli x, lli y) {
  177.         lli par_x = FindParent(x), par_y = FindParent(y);
  178.         if (par_x == par_y) return;
  179.         if (rank[par_x] < rank[par_y]) {
  180.             parent[par_x] = par_y;
  181.         } else if (rank[par_y] < rank[par_x]) {
  182.             parent[par_y] = par_x;
  183.         } else {
  184.             parent[par_x] = par_y;
  185.             ++rank[par_y];
  186.         }
  187.     }
  188.  
  189.     void UnionBySize(lli x, lli y) {
  190.         lli par_x = FindParent(x), par_y = FindParent(y);
  191.         if (par_x == par_y) return;
  192.         if (size[par_x] < size[par_y]) {
  193.             parent[par_x] = par_y;
  194.             size[par_y] += size[par_x];
  195.         } else {
  196.             parent[par_y] = par_x;
  197.             size[par_x] += size[par_y];
  198.         }
  199.     }
  200.  
  201.     lli FindParent(lli x) {
  202.         if (parent[x] != x) {
  203.             parent[x] = FindParent(parent[x]); // Path compression
  204.         }
  205.         return parent[x];
  206.     }
  207. };
  208.  
  209. // Fenwick Tree (Binary Indexed Tree)
  210. class FenwickTree {
  211.     std::vector<ll> bit;
  212.     ll n;
  213.  
  214. public:
  215.     FenwickTree(ll size) : n(size), bit(size + 1, 0) {}
  216.  
  217.     void update(ll idx, ll delta) {
  218.         for (++idx; idx <= n; idx += idx & -idx) {
  219.             bit[idx] += delta;
  220.         }
  221.     }
  222.  
  223.     ll prefix_sum(ll idx) {
  224.         ll sum = 0;
  225.         for (++idx; idx > 0; idx -= idx & -idx) {
  226.             sum += bit[idx];
  227.         }
  228.         return sum;
  229.     }
  230.  
  231.     void build(const std::vector<ll>& arr) {
  232.         for (ll i = 0; i < n; ++i) {
  233.             update(i, arr[i]);
  234.         }
  235.     }
  236. };
  237.  
  238.  
  239. // Utility Functions
  240.  
  241. bool sortd(const pair<lli,lli> &a,const pair<int,int> &b){
  242. 	return (a.second > b.second);
  243. }
  244.  
  245. bool sorta(const pair<lli,lli> &a,const pair<int,int> &b){
  246. 	return (a.second < b.second);
  247. }
  248.  
  249. string decToBinary(lli n){
  250. 	string s="";
  251. 	lli i = 0;
  252. 	while (n > 0) {
  253. 		s =to_string(n%2)+s;
  254. 		n = n / 2;
  255. 		i++;}
  256. 	return s;
  257. }
  258.  
  259. bool IsPalindrome(const string& s) {
  260.     lli left = 0, right = s.size() - 1;
  261.     while (left <= right) {
  262.         if (s[left] != s[right]) return false;
  263.         ++left;
  264.         --right;
  265.     }
  266.     return true;
  267. }
  268.  
  269. lli CountChar(const string& s, char c) {
  270.     return count(s.begin(), s.end(), c);
  271. }
  272.  
  273. lli gcd(lli a, lli b) {
  274.     while (b != 0) {
  275.         lli temp = b;
  276.         b = a % b;
  277.         a = temp;
  278.     }
  279.     return a;
  280. }
  281.  
  282. lli lcm(lli a, lli b) {
  283.     return (a / gcd(a, b)) * b;
  284. }
  285.  
  286. bool IsPrime(lli n) {
  287.     if (n <= 1) return false;
  288.     for (lli i = 2; i * i <= n; ++i) {
  289.         if (n % i == 0) return false;
  290.     }
  291.     return true;
  292. }
  293.  
  294. vlli p(100005);
  295.  
  296. void PrimeSieves(vlli &p){
  297. 	for(int i=3;i<=1000000;i+=2) p[i]=1;
  298. 	for(int i=3;i<=1000000;i+=2){
  299. 		if(p[i]==1){
  300. 			for(int j=i*i;j<=1000000;j=j+i){
  301. 				p[j]=0;
  302. 			}
  303. 		}
  304. 	}
  305. 	p[2]=1;
  306. 	p[1]=p[0]=0;
  307. }	
  308.  
  309. lli SumOfvec(const vector<lli>& arr) {
  310.     return accumulate(arr.begin(), arr.end(), 0LL);
  311. }
  312.  
  313. lli count_char(string s,char c){
  314. 	lli cnt=0;
  315. 	for(lli i=0;i<s.size();i++){
  316. 		if(s[i]==c) cnt++;
  317. 	}
  318. 	return cnt;
  319. }
  320.  
  321.  
  322. bool IsVowel(char c) {
  323.     static const unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
  324.     return vowels.count(c) > 0;
  325. }
  326.  
  327. lli HashString(const string& s) {
  328.     static const lli p = 31;
  329.     lli hashValue = 0, pPow = 1;
  330.     for (char ch : s) {
  331.         hashValue = (hashValue + (ch - 'a' + 1) * pPow) % MOD;
  332.         pPow = (pPow * p) % MOD;
  333.     }
  334.     return hashValue;
  335. }
  336.  
  337. vector<vector<lli>> InputTree(lli n) {
  338.     vector<vector<lli>> adjList(n);
  339.     for (lli i = 0; i < n - 1; ++i) {
  340.         lli u, v;
  341.         cin >> u >> v;
  342.         adjList[u].push_back(v);
  343.         adjList[v].push_back(u);
  344.     }
  345.     return adjList;
  346. }
  347.  
  348. vector<ll> calculateZ(string& s) {
  349.     ll n = s.length();
  350.     vector<ll> Z(n, 0);
  351.     ll L = 0, R = 0, K;
  352.  
  353.     for (ll i = 1; i < n; ++i) {
  354.         if (i > R) {
  355.             L = R = i;
  356.             while (R < n && s[R] == s[R - L]) {
  357.                 R++;
  358.             }
  359.             Z[i] = R - L;
  360.             R--;
  361.         } else {
  362.             K = i - L;
  363.             if (Z[K] < R - i + 1) {
  364.                 Z[i] = Z[K];
  365.             } else {
  366.                 L = i;
  367.                 while (R < n && s[R] == s[R - L]) {
  368.                     R++;
  369.                 }
  370.                 Z[i] = R - L;
  371.                 R--;
  372.             }
  373.         }
  374.     }
  375.     return Z;
  376. }
  377.  
  378. string PreProcess_Manacher(string s){
  379. 	string t="#";
  380. 	for(ll i=0;i<s.size();i++){
  381. 		t+=s[i];
  382. 		t+='#';
  383. 	}
  384. 	return t;
  385. }
  386.  
  387. //*********************Code starts*************************//
  388.  
  389. void Solve() 
  390. {
  391. 	string s;
  392.     cin >> s;
  393.  
  394.     ll n = s.size();
  395.     s = " " + s;
  396.  
  397.     vector<ll> p(n + 1, 0);
  398.  
  399.     for (ll i = 1; i <= n; i++)
  400.     {
  401.         p[i] = (s[i] == '1' ? 1 : -1) + p[i - 1];
  402.     }
  403.  
  404.     map<ll, ll> cnt;
  405.     ll res = 0;
  406.  
  407.     for(ll i = 0; i <= n ; i++)
  408.     {
  409.         res = (res + (n - i + 1) * cnt[p[i]]) % MOD;
  410.         cnt[p[i]] = (cnt[p[i]] + (i + 1)) % MOD;
  411.     }
  412.     cout << res << endl;
  413. }
  414.  
  415. int32_t main() {
  416.     FAST_IO;
  417.     #ifndef ONLINE_JUDGE
  418.     freopen("Error.txt", "W", stderr);
  419.     #endif
  420.     lli t=1; 
  421.     cin>>t;
  422.     while(t--) 
  423.     {
  424.         Solve();
  425.     }
  426.     return 0;
  427. }
  428.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Kl4cBR
language:
C++14 (gcc 8.3)
created:
7 days 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!