結果
問題 | No.381 名声値を稼ごう Extra |
ユーザー |
![]() |
提出日時 | 2016-01-01 00:55:02 |
言語 | C++11 (gcc 13.3.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 31,509 bytes |
コンパイル時間 | 2,501 ms |
コンパイル使用メモリ | 185,624 KB |
実行使用メモリ | 24,832 KB |
最終ジャッジ日時 | 2024-11-22 11:36:45 |
合計ジャッジ時間 | 5,779 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 RE * 1 |
コンパイルメッセージ
main.cpp: In member function ‘int bigInt::Rshift(int, unsigned int*, int, unsigned int*)’: main.cpp:215:3: warning: no return statement in function returning non-void [-Wreturn-type] 215 | } | ^ main.cpp: In function ‘void reader(double*)’: main.cpp:17:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 17 | void reader(double *x){scanf("%lf",x);} | ~~~~~^~~~~~~~~ main.cpp: In member function ‘bigInt& bigInt::operator*=(unsigned int)’: main.cpp:1001:13: warning: control reaches end of non-void function [-Wreturn-type] 1001 | mulArray(a); | ~~~~~~~~^~~ main.cpp: In member function ‘bigInt& bigInt::operator+=(unsigned int)’: main.cpp:942:3: warning: control reaches end of non-void function [-Wreturn-type] 942 | } | ^
ソースコード
#include<bits/stdc++.h>#include<sys/time.h>using namespace std;#define REP(i,a,b) for(i=a;i<b;i++)#define rep(i,n) REP(i,0,n)#define mygc(c) (c)=getchar_unlocked()#define mypc(c) putchar_unlocked(c)#define ll long long#define ull unsigned llvoid reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}void reader(double *x){scanf("%lf",x);}int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}void writer(double x, char c){printf("%.15f",x);mypc(c);}void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}template<class T> void writerLn(T x){writer(x,'\n');}template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}char memarr[17000000]; void *mem = memarr;#define MD 1000000007int get_inv(ll a, int md){ll t=a,s=md,u=1,v=0,e;while(s){e=t/s;t-=e*s;u-=e*v;swap(t,s);swap(u,v);}if(u<0)u+=md;return u;}struct mint{static unsigned md, W, R, Rinv, mdninv, RR;unsigned val;mint(){}mint(int a){val=mulR(a);}mint(unsigned a){val=mulR(a);}mint(ll a){val=mulR(a);}mint(ull a){val=mulR(a);}void setmod(unsigned m){int i;unsigned t;W=32;md=m;R=(1ULL<<W)%md;RR=(ull)R*R%md;switch(m){case 104857601:Rinv=2560000;mdninv=104857599;break;case998244353:Rinv=232013824;mdninv=998244351;break;case 1000000007:Rinv=518424770;mdninv=2226617417U;break;case 1000000009:Rinv=171601999;mdninv=737024967;break;case 1004535809:Rinv=234947584;mdninv=1004535807;break;case 1007681537:Rinv=236421376;mdninv=1007681535;break;case 1012924417:Rinv=238887936;mdninv=1012924415;break;case 1045430273:Rinv=254466304;mdninv=1045430271;break;case 1051721729:Rinv=257538304;mdninv=1051721727;break;default:Rinv=get_inv(R,md);mdninv=0;t=0;rep(i,W){if(t%2==0)t+=md,mdninv|=(1U<<i);t/=2;}}}unsigned mulR(unsigned a){return(ull)a*R%md;}unsigned mulR(int a){if(a<0)a=a%md+md;return mulR((unsigned)a);}unsigned mulR(ull a){return mulR((unsigned)(a%md));}unsigned mulR(ll a){if(a<0)a=a%md+md;return mulR((unsigned)a);}unsigned reduce(unsigned T){unsigned m=T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;}unsigned reduce(ull T){unsigned m=(unsigned)T*mdninv;unsigned t=(unsigned)((T+(ull)m*md)>>W);if(t>=md)t-=md;return t;}unsigned get(){return reduce(val);}mint&operator+=(mint a){val+=a.val;if(val>=md)val-=md;return*this;}mint&operator-=(mint a){if(val<a.val)val=val+md-a.val;else val-=a.val;return*this;}mint&operator*=(mint a){val=reduce((ull)val*a.val);return*this;}mint&operator/=(mint a){return*this*=a.inverse();}mint operator+(mint a){return mint(*this)+=a;}mint operator-(mint a){return mint(*this)-=a;}mint operator*(mint a){return mint(*this)*=a;}mintoperator/(mint a){return mint(*this)/=a;}mint operator+(int a){return mint(*this)+=mint(a);}mint operator-(int a){return mint(*this)-=mint(a);}mint operator*(int a){return mint(*this)*=mint(a);}mint operator/(int a){return mint(*this)/=mint(a);}mint operator+(ll a){return mint(*this)+=mint(a);}mint operator-(ll a){return mint(*this)-=mint(a);}mint operator*(ll a){return mint(*this)*=mint(a);}mint operator/(ll a){return mint(*this)/=mint(a);}mint operator-(void){mint res;if(val)res.val=md-val;else res.val=0;return res;}operator bool(void){return val!=0;}operator int(void){return get();}operator ll(void){return get();}mint inverse(){int a=val,b=md,u=1,v=0,t;mint r;while(b){t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}if(u<0)u+=md;r.val=(ull)u*RR%md;return r;}mint pw(ull b){mint a(*this),r;r.val=R;while(b){if(b&1)r*=a;b>>=1;a*=a;}return r;}bool operator==(int a){return get()==a;}bool operator!=(int a){return get()!=a;}};unsigned mint::md, mint::W, mint::R, mint::Rinv, mint::mdninv, mint::RR;mint operator+(int a, mint b){return mint(a)+=b;}mint operator-(int a, mint b){return mint(a)-=b;}mint operator*(int a, mint b){return mint(a)*=b;}mint operator/(int a, mint b){return mint(a)/=b;}mint operator+(ll a, mint b){return mint(a)+=b;}mint operator-(ll a, mint b){return mint(a)-=b;}mint operator*(ll a, mint b){return mint(a)*=b;}mintoperator/(ll a, mint b){return mint(a)/=b;}mint mval[10000], minv[10000];void mint_init(int md=MD, mint val[]=mval, int vals=10000, mint inv[]=minv, int invs=10000){int i;val[0].setmod(md);val[0].val=0;REP(i,1,vals){val[i].val=val[i-1].val+mint::R;if(val[i].val >=md)val[i].val-=md;}inv[1].val=1;REP(i,2,invs){inv[i].val=md-((ll)(md/i)*inv[md%i].val%md);}REP(i,1,invs)inv[i].val=(ull)inv[i].val*mint::R%md;}void mfft(int n, mint x[], mint root, void *mem){int i,j,X,Y,Z,s=1;mint I,J,K,a,b,c,d,A,B,C,D,t,*y=(mint*)mem;t=root.pw((mint::md-1)/4*3);root=root.pw((mint::md-1)/n);while(n>2){X=n/4;Y=X+X;Z=X+Y;I.val=mint::R;rep(i,X){J=I*I;K=I*J;rep(j,s)a=x[j+s*i],b=x[j+s*(i+X)],c=x[j+s*(i+Y)],d=x[j+s*(i+Z)],A=a+c,B=a-c,C=b+d,D=(b-d)*t,y[j+s*4*i]=A+C,y[j+s*(4*i+1)]=I*(B-D),y[j+s*(4*i+2)]=J*(A-C),y[j+s*(4*i+3)]=K*(B+D);I*=root;}n/=4;s*=4;root*=root;root*=root;swap(x,y);}if(n==2){rep(i,s)y[i]=x[i]+x[i+s],y[i+s]=x[i]-x[i+s];n/=2;s*=2;root*=root;swap(x,y);}rep(i,s)y[i]=x[i];}void mfftinv(int n, mint x[], mint root, void *mem){int i,j,X,Y,Z,s=1;mint I,J,K,a,b,c,d,A,B,C,D,t,*y=(mint*)mem;root=root.inverse();t=root.pw((mint::md-1)/4);root=root.pw((mint::md-1)/n);while(n>2){X=n/4;Y=X+X;Z=X+Y;I.val=mint::R;rep(i,X){J=I*I;K=I*J;rep(j,s)a=x[j+s*i],b=x[j+s*(i+X)],c=x[j+s*(i+Y)],d=x[j+s*(i+Z)],A=a+c,B=a-c,C=b+d,D=(b-d)*t,y[j+s*4*i]=A+C,y[j+s*(4*i+1)]=I*(B+D),y[j+s*(4*i+2)]=J*(A-C),y[j+s*(4*i+3)]=K*(B-D);I*=root;}n/=4;s*=4;root*=root;root*=root;swap(x,y);}if(n==2){rep(i,s)y[i]=x[i]+x[i+s],y[i+s]=x[i]-x[i+s];n/=2;s*=2;root*=root;swap(x,y);}rep(i,s)y[i]=x[i];}void modconvolution(mint A[], int As, mint B[], int Bs, mint res[], int Rs, void *mem, mint root){int i,n,m;mint*a,*b,r;n=max(As+Bs,Rs);for(m=1;m<n;m*=2);a=(mint*)mem;b=a+m;mem=b+m;rep(i,As)a[i]=A[i];REP(i,As,m)a[i].val=0;rep(i,Bs)b[i]=B[i];REP(i,Bs,m)b[i].val=0;mfft(m,a,root,mem);mfft(m,b,root,mem);rep(i,m)a[i]*=b[i];mfftinv(m,a,root,mem);r=mint(m).inverse();rep(i,Rs)res[i]=a[i]*r;}void modconvolution(mint A[], int As, mint res[], int Rs, void *mem, mint root){int i,n,m;mint*a,r;n=max(2*As, Rs);for(m=1;m<n;m*=2);a=(mint*)mem;mem=a+m;rep(i,As)a[i]=A[i];REP(i,As,m)a[i].val=0;mfft(m,a,root,mem);rep(i,m)a[i]*=a[i];mfftinv(m,a,root,mem);r=mint(m).inverse();rep(i,Rs)res[i]=a[i]*r;}int modconvolutionGetLength(int As, int Bs, int Rs){int n=max(As+Bs,Rs),res;for(res=1;res<n;res*=2);return res;}void modconvolutionPreCalc(mint A[], int As, mint res[], int Rs, void *mem, int root, int domultiply=1){int i,m;mint*a,r;m=Rs;a=(mint*)mem;mem=a+m;rep(i,As)a[i]=A[i];REP(i,As,m)a[i].val=0;mfft(m,a,root,mem);rep(i,Rs)res[i]=a[i];if(domultiply){r=mint(m).inverse();rep(i,Rs)res[i]*=r;}}void modconvolutionWithPreCalc(mint A[], int As, mint B[], int Bs, mint res[], int Rs, void *mem, int root, int domultiply=0){int i,m,r;mint*a,*b;m=As;a=(mint*)mem;b=a+m;mem=b+m;rep(i,As)a[i]=A[i];rep(i,Bs)b[i]=B[i];REP(i,Bs,m)b[i].val=0;mfft(m,b,root,mem);rep(i,m)a[i]*=b[i];mfftinv(m,a,root,mem);rep(i,Rs)res[i]=a[i];if(domultiply){r=mint(m).inverse();rep(i,Rs)res[i]*=r;}}struct bigInt{int sz, mem, sign;unsigned *d;static void *workMemory;static bigInt *writerbase;inline void init(void){mem = 0; d = NULL;set();}inline void init(int x){mem = 0; d = NULL;set(x);}inline void init(unsigned x){mem = 0; d = NULL;set(x);}inline void init(bigInt &x){mem = 0; d = NULL;set(x);}inline void set(void){sz = sign = 0;}inline void set(int x){if(x==0){set();return;}sz = 1;extend(sz);if(x < 0){sign *= -1;d[0] = -((ll)x);} else {sign = 1;d[0] = x;}}inline void set(unsigned x){if(x==0){set();return;}sz = 1;extend(sz);sign = 1;d[0] = x;}inline void set(bigInt &a){int i;sz = a.sz;sign = a.sign;extend(sz);rep(i,sz) d[i] = a[i];}inline unsigned& operator[](int n){return d[n];}inline void extend(int k){if(mem < k){k = max(k+1, mem+mem/2);d = (unsigned*) realloc(d, k*sizeof(unsigned));mem = k;}}inline void *malloc(int k, void *work){d = (unsigned*)work;mem = 2100000000;return d+k;}bool operator==(bigInt &a){int i;if(sign != a.sign || sz != a.sz) return false;rep(i,sz) if(d[i] != a.d[i]) return false;return true;}bool operator<(bigInt &a){if(sign < a.sign) return true;if(sign > a.sign) return false;if(sign==0) return false;if(sign * cmp(sz, d, a.sz, a.d) == -1) return true;return false;}inline int cmp(int as, unsigned a[], int bs, unsigned b[]){if(as > bs) return 1;if(as < bs) return -1;int i;for(i=as-1;i>=0;i--){if(a[i] > b[i]) return 1;if(a[i] < b[i]) return -1;}return 0;}inline int Lshift(int as, unsigned a[], int val, unsigned c[]){int i, cs, d, r;d = val / 32;r = val % 32;if(r){cs = as+d+1;c[cs-1] = 0;for(i=as-1;i>=0;i--){c[i+d+1] |= a[i]>>(32-r);c[i+d] = a[i]<<r;}rep(i,d) c[i] = 0;if(c[cs-1]==0) cs--;} else {for(i=as-1;i>=0;i--) c[i+d] = a[i];rep(i,d) c[i] = 0;cs = as + d;}return cs;}inline int Rshift(int as, unsigned a[], int val, unsigned c[]){}inline int add(int as, unsigned a[], unsigned b, unsigned r[]){int i, rs = as;rep(i,rs) r[i] = a[i];rep(i,rs){if(r[i]+b < r[i]){r[i] += b;b = 1;} else {r[i] += b;b = 0;}}if(b) r[rs++] = b;return rs;}inline int add(int as, unsigned a[], unsigned b){int i;rep(i,as){if(a[i]+b < a[i]){a[i] += b;b = 1;} else {a[i] += b;b = 0;}}if(b) a[as++] = b;return as;}inline int sub(int as, unsigned a[], unsigned b, unsigned r[]){int i, rs = as;rep(i,rs) r[i] = a[i];rep(i,rs){if(r[i] < b){r[i] -= b;b = 1;} else {r[i] -= b;break;}}if(rs && r[rs-1]==0) rs--;return rs;}inline int sub(int as, unsigned a[], unsigned b){int i;rep(i,as){if(a[i] < b){a[i] -= b;b = 1;} else {a[i] -= b;break;}}if(a[as-1]==0) as--;return as;}/* r=a or r=b is allowed */inline int add(int as, unsigned a[], int bs, unsigned b[], unsigned r[], void *work){int i, rs;unsigned *carry = (unsigned*) work;if(as < bs){rs = bs + 1;carry[0] = 0;rep(i,as){carry[i+1] = (a[i]+b[i] < a[i])?1:0;r[i] = a[i] + b[i];}REP(i,as,bs){carry[i+1] = 0;r[i] = b[i];}r[rs-1] = 0;rep(i,rs){if(r[i]+carry[i] < r[i]) carry[i+1]++;r[i] += carry[i];}} else {rs = as + 1;carry[0] = 0;rep(i,bs){carry[i+1] = (a[i]+b[i] < a[i])?1:0;r[i] = a[i] + b[i];}REP(i,bs,as){carry[i+1] = 0;r[i] = a[i];}r[rs-1] = 0;rep(i,rs){if(r[i]+carry[i] < r[i]) carry[i+1]++;r[i] += carry[i];}}if(rs && r[rs-1]==0) rs--;return rs;}inline int add(int as, unsigned a[], int bs, unsigned b[]){int i;unsigned carry;if(as < bs){REP(i,as,bs) a[i] = b[i];swap(bs, as);}carry = 0;rep(i,bs){if(carry){carry = 0;if(a[i]==4294967295U) carry = 1;a[i]++;}if(a[i]+b[i] < a[i]) carry = 1;a[i] += b[i];}while(carry){carry = 0;if(i==as) a[as++] = 0;if(a[i]==4294967295U) carry = 1;a[i]++;i++;}return as;}/* r=a or r=b is allowed */inline int sub(int as, unsigned a[], int bs, unsigned b[], unsigned r[], void *work){int i, rs;unsigned *carry = (unsigned*) work;carry[0] = 0;rs = as;rep(i,bs){if(a[i] < b[i]) carry[i+1] = 1; else carry[i+1] = 0;r[i] = a[i] - b[i];}REP(i,bs,as){carry[i+1] = 0;r[i] = a[i];}rep(i,as){if(r[i] < carry[i]) carry[i+1]++;r[i] -= carry[i];}while(rs && r[rs-1]==0) --rs;return rs;}inline int sub(int as, unsigned a[], int bs, unsigned b[]){int i;unsigned carry = 0;rep(i,bs){if(carry){carry = 0;if(a[i]==0) carry = 1;a[i]--;}if(a[i] < b[i]) carry = 1;a[i] -= b[i];}while(carry){carry = 0;if(a[i]==0) carry = 1;a[i]--;i++;}while(as && a[as-1]==0) as--;return as;}inline int mul(int as, unsigned a[], unsigned b, unsigned r[]){int i;ull tmp = 0;rep(i,as){tmp += (ull)b*(ull)a[i];r[i] = tmp&0xFFFFFFFF;tmp >>= 32;}if(tmp) r[as++] = tmp;return as;}inline unsigned div(int as, unsigned a[], unsigned b, int &ds, unsigned d[]){int i;ull tmp = 0;ds = as;for(i=ds-1;i>=0;i--){tmp = (tmp<<32) + a[i];d[i] = tmp / b;tmp %= b;}if(ds && d[ds-1]==0) ds--;return tmp;}/* r=a is allowed, r=b is not allowed */inline int mulSimple(int as, unsigned a[], int bs, unsigned b[], unsigned r[], void *work){int i, j, st, ed;ull sum, carry, tmp;unsigned *arr = (unsigned*) work;if(as==0 || bs==0) return 0;rep(i,as) arr[i] = a[i];sum = 0;carry = 0;rep(i,as+bs){st = max(0, i-as+1);ed = min(bs, i+1);REP(j,st,ed){tmp = (ull) arr[i-j] * b[j];if(sum+tmp<sum) carry++;sum += tmp;}r[i] = sum&0xFFFFFFFF;sum = (carry<<32)+(sum>>32);carry = 0;}as += bs;if(r[as-1]==0) as--;return as;}/* r=a is allowed, r=b is not allowed, just because this may call mulSimple */inline int mulKaratsuba(int as, unsigned a[], int bs, unsigned b[], unsigned c[], void *work){int i, j, k, ms, d;unsigned *c0, *c1, *c2, *ad, *bd, carry;int a0s, a1s, b0s, b1s, c0s, c1s, c2s, ads, bds, ac, bc, cs;double t1, t2, t3;while(as && a[as-1]==0) as--;while(bs && b[bs-1]==0) bs--;if(as==0 || bs==0) return 0;if((ll)as*bs < 100){return mulSimple(as,a,bs,b,c,work);}ms = max(as, bs);t1 = 1.43e-3 * as * bs;t2 = 2.1e-2 * ms * pow(min(as,bs), 0.6);t3 = 1.9e-1 * ms * pow(log(ms),1.5);if(ms > 480000) t3 = 1e100;if(t1 <= t2 && t1 <= t3) return mulSimple(as,a,bs,b,c,work);if(t3 <= t1 && t3 <= t2) return mulFFT8(as,a,bs,b,c,work);d = (ms+1) / 2;a0s = min(as, d);a1s = as-a0s;b0s = min(bs, d);b1s = bs-b0s;c0 = (unsigned*)work;c2 = c0 + (a0s+b0s);c1 = c2 + (a1s+b1s);ad = c1 + (a0s+b0s+2);bd = ad + a0s;work = bd + b0s;while(a0s && a[a0s-1]==0) a0s--;while(b0s && b[b0s-1]==0) b0s--;c0s = mulKaratsuba(a0s, a, b0s, b, c0, work);c2s = mulKaratsuba(a1s, a+d, b1s, b+d, c2, work);ac = cmp(a1s, a+d, a0s, a);bc = cmp(b1s, b+d, b0s, b);if(ac==0 || bc==0){c1s = 0;c1s = add(c1s, c1, c0s, c0);c1s = add(c1s, c1, c2s, c2);} else {if(ac==1) ads = sub(a1s, a+d, a0s, a, ad, work);else ads = sub(a0s, a, a1s, a+d, ad, work);if(bc==1) bds = sub(b1s, b+d, b0s, b, bd, work);else bds = sub(b0s, b, b1s, b+d, bd, work);c1s = mulKaratsuba(ads, ad, bds, bd, c1, work);if(ac+bc==0){c1s = add(c1s, c1, c0s, c0);c1s = add(c1s, c1, c2s, c2);} else if(ac==1 && bc==1){c1s = sub(c2s, c2, c1s, c1, c1, work);c1s = add(c1s, c1, c0s, c0);} else {c1s = sub(c0s, c0, c1s, c1, c1, work);c1s = add(c1s, c1, c2s, c2);}}cs = as + bs;rep(i,c0s) c[i] = c0[i];REP(i,c0s,d+d) c[i] = 0;rep(i,c2s) c[d+d+i] = c2[i];REP(i,d+d+c2s,cs) c[i] = 0;carry = 0;rep(i,c1s){if(carry){carry = 0;if(c[i+d]==4294967295U) carry = 1;c[i+d]++;}if(c[i+d]+c1[i] < c[i+d]) carry = 1;c[i+d] += c1[i];}while(carry){carry = 0;if(c[i+d]==4294967295U) carry = 1;c[i+d]++;i++;}if(c[cs-1]==0) cs--;return cs;}inline int mulFFT8(int as, unsigned a[], int bs, unsigned b[], unsigned c[], void *work){int i, j, k, aas, bbs, ccs, cs;unsigned md_mem, tmp, t1, t2;mint *aa, *bb, *cc;mint mtmp;aas = as * 8;bbs = bs * 8;ccs = aas+bbs;aa = (mint*)work;bb = aa+aas;cc = bb+bbs;work = cc+ccs;md_mem = mint::md;mtmp.setmod(1004535809U);rep(i,as) rep(k,8) aa[8*i+k] = mint((a[i]>>(4*k))&15U);rep(i,bs) rep(k,8) bb[8*i+k] = mint((b[i]>>(4*k))&15U);modconvolution(aa, aas, bb, bbs, cc, ccs, work, mint(3U));cs = as + bs;rep(i,cs) c[i] = (int)cc[8*i];rep(i,cs){REP(k,1,8){tmp = (int)cc[8*i+k];t1 = tmp << (k*4);t2 = tmp >> (32-k*4);if(t1) for(j=i;;j++){if(c[j] + t1 >= c[j]){ c[j] += t1; break; }c[j] += t1;t1 = 1;}if(t2) for(j=i+1;;j++){if(c[j] + t2 >= c[j]){ c[j] += t2; break; }c[j] += t2;t2 = 1;}}}mtmp.setmod(md_mem);while(cs && c[cs-1]==0) cs--;return cs;}inline void divKaratsuba(int as, unsigned a[], int bs, unsigned b[], int &ds, unsigned d[], int &rs, unsigned r[], void *work){int i, p, s, t, k, shi;int w1s, r1s, bws, w0s, r0s;unsigned cof, *w1, *r1, *bw, *w0, *r0, *aa, *bb;while(as && a[as-1]==0) as--;while(bs && b[bs-1]==0) bs--;assert(bs!=0);k = cmp(bs,b,as,a);if(k==1){ds = 0;rs = as;rep(i,rs) r[i] = a[i];return;}if(bs==1){r[0] = div(as, a, b[0], ds, d);rs = 1;if(!r[0]) rs=0;return;}shi = max(0, as+1 - bs*2) + 1;aa = (unsigned*)work;bb = aa + as+shi+1;work = bb + bs+shi;cof = (1ULL<<32) / (b[bs-1]+1);as = mul(as, a, cof, aa);bs = mul(bs, b, cof, bb);shi = max(0, as - bs*2);if((bs+shi)%2) shi++;if(shi > 0){for(i=as-1;i>=0;i--) aa[i+shi] = aa[i];rep(i,shi) aa[i] = 0;for(i=bs-1;i>=0;i--) bb[i+shi] = bb[i];rep(i,shi) bb[i] = 0;as += shi;bs += shi;}p = bs / 2;s = max(0,as-2*p);w1s = max(0, s-bs+p+1);bws = p + w1s;r1s = max(bs + 1, bws);w0s = r1s-bs+p+1;bws = max(bws, w0s+p);r0s = max(bs+1, bws);w1 = (unsigned*)work;r1 = w1 + w1s;bw = r1 + r1s;w0 = bw + bws;r0 = w0 + w0s;work = r0 + r0s;divKaratsuba(s, aa+2*p, bs-p, bb+p, w1s, w1, r1s, r1, work);if(r1s){rep(i,r1s) r1[i+p] = r1[i];rep(i,p) r1[i] = 0;r1s += p;}s = min(p, as-p);r1s = add(r1s, r1, s, aa+p);bws = mulKaratsuba(p, bb, w1s, w1, bw, work);k = cmp(r1s, r1, bws, bw);while(k==-1){w1s = sub(w1s, w1, 1U);r1s = add(r1s, r1, bs, bb);k = cmp(r1s, r1, bws, bw);}if(k==1){r1s = sub(r1s, r1, bws, bw);} else {r1s = 0;}divKaratsuba(r1s, r1, bs-p, bb+p, w0s, w0, r0s, r0, work);if(r0s){rep(i,r0s) r0[i+p] = r0[i];rep(i,p) r0[i] = 0;r0s += p;}r0s = add(r0s, r0, p, aa);bws = mulKaratsuba(p, bb, w0s, w0, bw, work);k = cmp(r0s, r0, bws, bw);while(k==-1){w0s = sub(w0s, w0, 1U);r0s = add(r0s, r0, bs, bb);k = cmp(r0s, r0, bws, bw);}if(k==1){r0s = sub(r0s, r0, bws, bw);} else {r0s = 0;}ds = 0;if(w1s){ds = w1s + p;rep(i,w1s) d[i+p] = w1[i];rep(i,p) d[i] = 0;}ds = add(ds, d, w0s, w0);rs = max(0, r0s - shi);rep(i,rs) r[i] = r0[i+shi];div(rs, r, cof, rs, r);}// signを無視して c = a+binline void addArray(bigInt &c, bigInt &a, bigInt &b){if((&c)==(&a)) c.sz = add(a.sz, a.d, b.sz, b.d);else if((&c)==(&b)) c.sz = add(b.sz, b.d, a.sz, a.d);else c.sz = add(a.sz, a.d, b.sz, b.d, c.d, workMemory);}// signを無視して c = a-b, 仮定 a >= binline void subArray(bigInt &c, bigInt &a, bigInt &b){if((&c)==(&a)) c.sz = sub(a.sz, a.d, b.sz, b.d);else c.sz = add(a.sz, a.d, b.sz, b.d, c.d, workMemory);}// abs(a) (>,<,=) abs(b) -> (1,-1,0)inline int ArrayCmp(bigInt &a, bigInt &b){return cmp(a.sz, a.d, b.sz, b.d);}bigInt& operator+=(bigInt &a){if(a.sign==0) return *this;if(sign==0){ set(a); return *this; }extend(max(sz, a.sz) + 1);if(sign==a.sign){addArray(*this, *this, a);} else {int k = ArrayCmp(*this, a);if(k==1){subArray(*this, *this, a);}else if(k==-1){subArray(*this, a, *this);sign *= -1;}else{a.sign = a.sz = 0;}}return *this;}bigInt& operator-=(bigInt &a){if(a.sign==0) return *this;if(sign==0){ set(a); sign*=-1; return *this; }extend(max(sz, a.sz) + 1);if(sign!=a.sign){addArray(*this, *this, a);} else {int k = ArrayCmp(*this, a);if(k==1){subArray(*this, *this, a);}else if(k==-1){subArray(*this, a, *this);sign *= -1;}else{a.sign = a.sz = 0;}}return *this;}bigInt& operator*=(bigInt &a){if(sign==0) return *this;if(a.sign==0){ set(); return *this; }extend(sz + a.sz);sign *= a.sign;if(this == &a){int i;unsigned *t = (unsigned*)workMemory;rep(i,sz) t[i] = d[i];sz = mulKaratsuba(sz, d, sz, t, d, t+sz);} else {sz = mulKaratsuba(sz, d, a.sz, a.d, d, workMemory);}return *this;}bigInt& operator/=(bigInt &a){if(sign==0) return *this;assert(a.sz!=0);sign *= a.sign;int dum;unsigned *memory = (unsigned*)workMemory;divKaratsuba(sz, d, a.sz, a.d, sz, d, dum, memory, memory+a.sz);if(sz==0) sign = 0;return *this;}bigInt& operator%=(bigInt &a){if(sign==0) return *this;assert(a.sz!=0);sign *= a.sign;int dum;unsigned *memory = (unsigned*)workMemory;divKaratsuba(sz, d, a.sz, a.d, dum, memory, sz, d, memory+max(0,sz-a.sz+1));if(sz==0) sign = 0;return *this;}void addArray(unsigned val){int i;rep(i,sz){if(d[i]+val < d[i]){d[i] += val;val = 1;} else {d[i] += val;val = 0;break;}}if(val){extend(sz+1);d[sz++] = val;}}void subArray(unsigned val){int i;if(sz==1){if(d[0] < val){sign = -sign;d[0] = val - d[0];} else if(d[0] > val){d[0] -= val;} else {sz = 0;sign = 0;}return;}rep(i,sz){if(d[i] < val){d[i] -= val;val = 1;} else {d[i] -= val;break;}}if(sz && d[sz-1]==0) sz--;}void mulArray(unsigned val){int i;ull tmp = 0;if(val==0){sign = sz = 0;return;}if(val==1){return;}extend(sz+1);rep(i,sz){tmp += (ull)val*(ull)d[i];d[i] = tmp&0xFFFFFFFF;tmp >>= 32;}if(tmp) d[sz++] = tmp;}unsigned divArray(unsigned val){int i;ull tmp = 0;assert(val != 0);if(val==1) return 0;for(i=sz-1;i>=0;i--){tmp = (tmp<<32) + d[i];d[i] = tmp / val;tmp %= val;}if(sz && d[sz-1]==0) sz--;if(sz==0) sign = 0;return tmp;}bigInt& operator+=(int a){int fg;unsigned val;if(a==0) return *this;if(sign==0){set(a);return *this;}if(a < 0) fg = -1, val = -((ll)a);else fg = 1, val = a;if(fg==sign) addArray(val);else subArray(val);}bigInt& operator+=(unsigned a){if(a==0) return *this;if(sign==0){set(a);return *this;}if(sign==1) addArray(a);else subArray(a);}bigInt& operator-=(int a){int fg;unsigned val;if(a==0) return *this;if(sign==0){set(a);sign *= -1;return *this;}if(a < 0) fg = -1, val = -((ll)a);else fg = 1, val = a;if(fg!=sign) addArray(val);else subArray(val);}bigInt& operator-=(unsigned a){if(a==0) return *this;if(sign==0){set(a);sign *= -1;return *this;}if(sign!=1) addArray(a);else subArray(a);}bigInt& operator*=(int a){int fg;unsigned val;if(a==0){sz = sign = 0;return *this;}if(sign==0){return *this;}if(a < 0) val = -((ll)a), sign *= -1;else val = a;mulArray(val);}bigInt& operator*=(unsigned a){if(a==0){sz = sign = 0;return *this;}if(sign==0){return *this;}mulArray(a);}bigInt& operator/=(int a){int fg;unsigned val;assert(a!=0);if(sign==0){return *this;}if(a < 0) val = -((ll)a), sign *= -1;else val = a;divArray(val);}bigInt& operator/=(unsigned a){assert(a!=0);if(sign==0){return *this;}divArray(a);}void add(bigInt &a, bigInt &b){set(a);(*this)+=b;}void sub(bigInt &a, bigInt &b){set(a);(*this)-=b;}void mul(bigInt &a, bigInt &b){set(a);(*this)*=b;}void div(bigInt &a, bigInt &b){set(a);(*this)/=b;}void mod(bigInt &a, bigInt &b){set(a);(*this)%=b;}void divmod(bigInt &a, bigInt &b, bigInt *d, bigInt *r){assert(b.sz!=0);d->extend(a.sz-b.sz+1);r->extend(b.sz);d->sign = r->sign = a.sign*b.sign;divKaratsuba(a.sz, a.d, b.sz, b.d, d->sz, d->d, r->sz, r->d, a.workMemory);if(d->sz==0) d->sign = 0;if(r->sz==0) r->sign = 0;}void reader(int as, unsigned arr[], int &rs, unsigned r[], void *work){int i, ss;unsigned *s;if(as < 300){rs = 1;r[0] = arr[as-1];for(i=as-2;i>=0;i--){rs = mul(rs, r, 1000000000U, r);rs = add(rs, r, arr[i]);}return;}for(i=0;;i++){if(writerbase[i].sz==0){writerbase[i].extend(writerbase[i-1].sz * 2);writerbase[i].sz = mulKaratsuba(writerbase[i-1].sz, writerbase[i-1].d, writerbase[i-1].sz, writerbase[i-1].d, writerbase[i].d, work);writerbase[i].sign = 1;}if((1<<i) >= as) break;}reader(as-(1<<(i-1)), arr+(1<<(i-1)), rs, r, work);rs = mulKaratsuba(rs, r, writerbase[i].sz, writerbase[i].d, r, work);s = (unsigned*)work;reader(1<<(i-1), arr, ss, s, s+(1<<(i-1)));rs = add(rs, r, ss, s);}void writer(int as, unsigned a[], int d, void *work){int i, k, bs, ts, ds;unsigned *dis, *b, *tmp;if(as < 100){dis = (unsigned*)work;b = dis + 9;tmp = b + as;bs = as;rep(i,bs) b[i] = a[i];ts = 0;while(bs) tmp[ts++] = div(bs, b, 1000000000U, bs, b);if(d==-1){ds = 0;while(tmp[ts-1]) dis[ds++] = tmp[ts-1]%10, tmp[ts-1]/=10;for(i=ds-1;i>=0;i--) mypc(dis[i]+'0');ts--;} else {i = (d - ts) * 9;while(i>0) i--, mypc('0');}while(ts--){rep(i,9) dis[i] = tmp[ts]%10, tmp[ts]/=10;rep(i,9) mypc(dis[8-i]+'0');}} else {for(i=0;;i++){if(writerbase[i].sz==0) writerbase[i].mul(writerbase[i-1], writerbase[i-1]);if(writerbase[i].sz*2 >= as) break;}b = (unsigned*)work;tmp = b + as - writerbase[i].sz + 1;work = tmp + writerbase[i].sz;divKaratsuba(as, a, writerbase[i].sz, writerbase[i].d, bs, b, ts, tmp, work);writer(bs, b, d==-1?-1:d-(1<<(i-1)), work);writer(ts, tmp, 1<<(i-1), work);}}bigInt(void){init();}void free(void){std::free(d);}};void *bigInt::workMemory;bigInt *bigInt::writerbase;void bigIntInit(int memsize = 20){int i;bigInt::workMemory = malloc(memsize*1000000);bigInt::writerbase = (bigInt*) malloc(sizeof(bigInt)*40);bigInt::writerbase[0].init(1U);bigInt::writerbase[1].init(1000000000U);REP(i,2,40) bigInt::writerbase[i].init();}void reader(bigInt *a){int i, j, k, sz=0, m=0;char *buf;unsigned *arr;for(;;){mygc(k);if(k=='-'){m=1;continue;}if('0'<=k&&k<='9'){break;}}buf = (char*)a->workMemory;buf[sz++] = k - '0';for(;;){mygc(k);if(k<'0' || k>'9') break;buf[sz++] = k - '0';}reverse(buf,buf+sz);arr = (unsigned*)(buf+sz);k = sz / 9;rep(i,k){arr[i] = 0;for(j=8;j>=0;j--) arr[i] = arr[i]*10 + buf[i*9+j];}if(sz%9){arr[k] = 0;for(j=sz%9-1;j>=0;j--) arr[k] = arr[k]*10 + buf[k*9+j];k++;}if(k < 100){a->set(arr[k-1]);for(i=k-2;i>=0;i--){(*a) *= 1000000000U;(*a) += arr[i];}} else {a->set(0);a->extend(k);a->sign = 1;a->reader(k, arr, a->sz, a->d, arr+k);}if(m) a->sign *= -1;}void writer(bigInt &a, char h){if(a.sign!=0){if(a.sign==-1) mypc('-');a.writer(a.sz, a.d, -1, a.workMemory);}else{mypc('0');}mypc(h);}#define SSE4_M32U_popcount(c,a) asm volatile("popcnt %1, %0;" : "=r"(c) : "r"(a))int main(){int i, j, res = 0;bigInt k;bigIntInit(200);mint_init();reader(&k);rep(i,k.sz){SSE4_M32U_popcount(j,k.d[i]);res += j;}writerLn(res);return 0;}