All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Given a string S consisting of only 1s and 0s, find the number of substrings which start and end both in 1.
In this problem, a substring is defined as a sequence of continuous characters Si, Si+1, ..., Sj where 1 ≤ i ≤ j ≤ N.
First line contains T, the number of testcases. Each testcase consists of N(the length of string) in one line and string in second line.
For each testcase, print the required answer in one line.
- 1 ≤ T ≤ 105
- 1 ≤ N ≤ 105
- Sum of N over all testcases ≤ 105
Input: 2 4 1111 5 10001 Output: 10 3
#test1: All substrings satisfy.
#test2: Three substrings S[1,1], S[5,5] and S[1,5] satisfy.
|Tags||ad-hoc, cakewalk, darkshadows, july14|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.