Bit strings

input/code.cpp: In function 'int main()':
input/code.cpp:104:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &tcs);
                   ^
input/code.cpp:106:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
                 ^

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef __int128 lll;
const lll mod=2097152000007340033;
const lll root=2014907510281342032;
const lll root_pw=1<<20;

lll pot(lll x, lll p){
	if (p==0) return 1;
	if (p%2==0){
		x=pot(x, p/2);
		return (x*x)%mod;
	}
	return (x*pot(x, p-1))%mod;
}

lll inv(lll x){
	return pot(x, mod-2);
}

vector<lll> fft(vector<lll> a, int d){
	lll root_1=inv(root);
	int n=(int)a.size();
	for (int i=1,j=0;i<n;i++){
		int bit=n>>1;
		for (;j>=bit;bit>>=1){
			j-=bit;
		}
		j+=bit;
		if (i<j) swap(a[i], a[j]);
	}
	for (int len=2;len<=n;len<<=1){
		lll wlen=root;
		if (d==-1){
			wlen=root_1;
		}
		for (int i=len;i<root_pw;i<<=1) wlen=(wlen*wlen)%mod;
		for (int i=0;i<n;i+=len){
			lll w=1;
			for (int j=0;j<len/2;j++){
				lll u=a[i+j];
				lll v=(a[i+j+len/2]*w)%mod;
				if (u+v<mod){
					a[i+j]=u+v;
				}
				else{
					a[i+j]=u+v-mod;
				}
				if (u-v>=0){
					a[i+j+len/2]=u-v;
				}
				else{
					a[i+j+len/2]=u-v+mod;
				}
				w=(w*wlen)%mod;
			}
		}
	}
	if (d==-1){
		lll nrev=inv(n);
		for (int i=0;i<n;i++){
			a[i]=(a[i]*nrev)%mod;
		}
	}
	return a;
}

vector<lll> conv(vector<lll> a, vector<lll> b){
	int as=a.size();
	int bs=b.size();
	int n=1;
	while (n<as+bs-1) n*=2;
	vector<lll> aa(n*2);
	vector<lll> bb(n*2);
	for (int i=0;i<as;i++){
		aa[i]=a[i];
	}
	for (int i=0;i<bs;i++){
		bb[i]=b[i];
	}
	aa=fft(aa, 1);
	bb=fft(bb, 1);
	vector<lll> c(2*n);
	for (int i=0;i<2*n;i++){
		c[i]=(aa[i]*bb[i])%mod;
	}
	c=fft(c, -1);
	c.resize(as+bs-1);
	return c;
}

char s[101010];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tcs;
	scanf("%d", &tcs);
	for (int tc=0;tc<tcs;tc++){
		scanf("%s", s);
		/*
		for (int i=0;i<100000;i++){
			s+='1';
		}
		*/
		int n=strlen(s);
		vector<lll> ct(n+1);
		ct[0]=1;
		int t=0;
		ll v0=0;
		ll c0=0;
		for (int i=0;i<n;i++){
			if (s[i]=='1') {
				t++;
				c0=0;
			}
			else{
				c0++;
				v0+=c0;
			}
			ct[t]++;
		}
		vector<lll> lol=ct;
		reverse(lol.begin(), lol.end());
		vector<lll> cv=conv(ct, lol);
		printf("%lld ", v0);
		for (int i=n-1;i>=0;i--){
			printf("%lld ", (ll)cv[i]);
		}
		printf("\n");
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED