結果
問題 | No.8055 2019(注:異常な難易度です) |
ユーザー | もりを |
提出日時 | 2019-04-02 00:10:29 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 16,423 bytes |
コンパイル時間 | 2,044 ms |
コンパイル使用メモリ | 184,276 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-27 06:32:09 |
合計ジャッジ時間 | 4,223 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | AC | 2 ms
5,248 KB |
testcase_24 | AC | 2 ms
5,248 KB |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | AC | 2 ms
5,248 KB |
testcase_27 | AC | 2 ms
5,248 KB |
testcase_28 | AC | 2 ms
5,248 KB |
testcase_29 | AC | 2 ms
5,248 KB |
testcase_30 | AC | 2 ms
5,248 KB |
testcase_31 | AC | 2 ms
5,248 KB |
testcase_32 | AC | 2 ms
5,248 KB |
testcase_33 | AC | 2 ms
5,248 KB |
testcase_34 | AC | 2 ms
5,248 KB |
testcase_35 | AC | 2 ms
5,248 KB |
testcase_36 | AC | 2 ms
5,248 KB |
testcase_37 | AC | 2 ms
5,248 KB |
testcase_38 | AC | 2 ms
5,248 KB |
testcase_39 | AC | 2 ms
5,248 KB |
testcase_40 | AC | 2 ms
5,248 KB |
testcase_41 | AC | 2 ms
5,248 KB |
testcase_42 | AC | 2 ms
5,248 KB |
testcase_43 | AC | 2 ms
5,248 KB |
testcase_44 | AC | 2 ms
5,248 KB |
testcase_45 | AC | 2 ms
5,248 KB |
testcase_46 | AC | 2 ms
5,248 KB |
testcase_47 | AC | 2 ms
5,248 KB |
testcase_48 | AC | 2 ms
5,248 KB |
testcase_49 | AC | 2 ms
5,248 KB |
testcase_50 | AC | 2 ms
5,248 KB |
testcase_51 | AC | 2 ms
5,248 KB |
testcase_52 | AC | 2 ms
5,248 KB |
testcase_53 | AC | 2 ms
5,248 KB |
testcase_54 | AC | 2 ms
5,248 KB |
testcase_55 | AC | 2 ms
5,248 KB |
testcase_56 | AC | 2 ms
5,248 KB |
testcase_57 | AC | 2 ms
5,248 KB |
testcase_58 | AC | 2 ms
5,248 KB |
testcase_59 | AC | 2 ms
5,248 KB |
testcase_60 | AC | 2 ms
5,248 KB |
testcase_61 | AC | 2 ms
5,248 KB |
testcase_62 | AC | 2 ms
5,248 KB |
testcase_63 | AC | 2 ms
5,248 KB |
testcase_64 | AC | 2 ms
5,248 KB |
testcase_65 | AC | 2 ms
5,248 KB |
testcase_66 | AC | 2 ms
5,248 KB |
testcase_67 | AC | 2 ms
5,248 KB |
testcase_68 | AC | 2 ms
5,248 KB |
testcase_69 | AC | 2 ms
5,248 KB |
testcase_70 | AC | 2 ms
5,248 KB |
testcase_71 | AC | 3 ms
5,248 KB |
testcase_72 | AC | 2 ms
5,248 KB |
testcase_73 | AC | 2 ms
5,248 KB |
testcase_74 | AC | 2 ms
5,248 KB |
testcase_75 | AC | 2 ms
5,248 KB |
testcase_76 | AC | 2 ms
5,248 KB |
testcase_77 | AC | 3 ms
5,248 KB |
testcase_78 | AC | 3 ms
5,248 KB |
testcase_79 | AC | 2 ms
5,248 KB |
testcase_80 | AC | 2 ms
5,248 KB |
testcase_81 | AC | 2 ms
5,248 KB |
testcase_82 | AC | 3 ms
5,248 KB |
testcase_83 | AC | 3 ms
5,248 KB |
testcase_84 | AC | 4 ms
5,248 KB |
testcase_85 | AC | 3 ms
5,248 KB |
testcase_86 | AC | 4 ms
5,248 KB |
testcase_87 | AC | 3 ms
5,248 KB |
testcase_88 | AC | 5 ms
5,248 KB |
testcase_89 | AC | 3 ms
5,248 KB |
testcase_90 | AC | 3 ms
5,248 KB |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:38:37: warning: 'digit' may be used uninitialized [-Wmaybe-uninitialized] 38 | #define REPI(i,a,b) for(ll i=ll(a);i<ll(b);++i) | ^ main.cpp:539:9: note: 'digit' was declared here 539 | ll M, digit; | ^~~~~ main.cpp:561:7: warning: 'M' may be used uninitialized [-Wmaybe-uninitialized] 561 | if (tmp == M) { | ^~ main.cpp:539:6: note: 'M' was declared here 539 | ll M, digit; | ^
ソースコード
#include <bits/stdc++.h> using namespace std; //#define int long long //TEMPLATE START---------------8<---------------8<---------------8<---------------8<---------------// typedef long long Int; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<string> vst; typedef vector<bool> vb; typedef vector<ld> vld; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vector<int> > vvi; const int INF = (0x7FFFFFFFL); const ll INFF = (0x7FFFFFFFFFFFFFFFL); const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const int MOD = 1e9 + 7; const int MODD = 998244353; const string alphabet = "abcdefghijklmnopqrstuvwxyz"; const double PI = acos(-1.0); const double EPS = 1e-9; const string Alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; int dx[9] = { 1, 0, -1, 0, 1, -1, -1, 1, 0 }; int dy[9] = { 0, 1, 0, -1, -1, -1, 1, 1, 0 }; #define ln '\n' #define scnaf scanf #define sacnf scanf #define sancf scanf #define SS(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__); template<typename T> void MACRO_VAR_Scan(T& t){cin >> t;}template<typename First, typename...Rest> void MACRO_VAR_Scan(First& first, Rest&...rest){cin >> first;MACRO_VAR_Scan(rest...);} #define SV(type,c,n) vector<type> c(n);for(auto& i:c)cin >> i; #define SVV(type,c,n,m) vector<vector<type>> c(n,vector<type>(m));for(auto& r:c)for(auto& i:r)cin >> i; template<class T,class U>ostream &operator<<(ostream &o,const pair<T,U>&j){o<<"{"<<j.first<<", "<<j.second<<"}";return o;} template<class T,class U>ostream &operator<<(ostream &o,const map<T,U>&j){o<<"{";for(auto t=j.begin();t!=j.end();++t)o<<(t!=j.begin()?", ":"")<<*t;o<<"}";return o;} template<class T>ostream &operator<<(ostream &o,const set<T>&j){o<<"{";for(auto t=j.begin();t!=j.end();++t)o<<(t!=j.begin()?", ":"")<<*t;o<<"}";return o;} template<class T>ostream &operator<<(ostream &o,const vector<T>&j){o<<"{";for(int i=0;i<(int)j.size();++i)o<<(i>0?", ":"")<<j[i];o<<"}";return o;} inline int print(void){cout << endl; return 0;} template<class Head> int print(Head&& head){cout << head;print();return 0;} template<class Head,class... Tail> int print(Head&& head,Tail&&... tail){cout<<head<<" ";print(forward<Tail>(tail)...);return 0;} inline int debug(void){cerr << endl; return 0;} template<class Head> int debug(Head&& head){cerr << head;debug();return 0;} template<class Head,class... Tail> int debug(Head&& head,Tail&&... tail){cerr<<head<<" ";debug(forward<Tail>(tail)...);return 0;} template<typename T> void PA(T &a){int ASIZE=sizeof(a)/sizeof(a[0]);for(int ii=0;ii<ASIZE;++ii){cout<<a[ii]<<" \n"[ii==ASIZE-1];}} template<typename T> void PV(T &v){int VSIZE=v.size();for(int ii=0;ii<VSIZE;++ii){cout<<v[ii]<<" \n"[ii==VSIZE-1];}} #define ER(x) cerr << #x << " = " << (x) << endl; #define ERV(v) {cerr << #v << " : ";for(const auto& xxx : v){cerr << xxx << " ";}cerr << "\n";} inline int YES(bool x){cout<<((x)?"YES":"NO")<<endl;return 0;} inline int Yes(bool x){cout<<((x)?"Yes":"No")<<endl;return 0;} inline int yes(bool x){cout<<((x)?"yes":"no")<<endl;return 0;} inline int yES(bool x){cout<<((x)?"yES":"nO")<<endl;return 0;} inline int Yay(bool x){cout<<((x)?"Yay!":":(")<<endl;return 0;} template<typename A,typename B> void sankou(bool x,A a,B b){cout<<((x)?(a):(b))<<endl;} #define _overload3(_1,_2,_3,name,...) name #define _REP(i,n) REPI(i,0,n) #define REPI(i,a,b) for(ll i=ll(a);i<ll(b);++i) #define REP(...) _overload3(__VA_ARGS__,REPI,_REP,)(__VA_ARGS__) #define _RREP(i,n) RREPI(i,n,0) #define RREPI(i,a,b) for(ll i=ll(a);i>=ll(b);--i) #define RREP(...) _overload3(__VA_ARGS__,RREPI,_RREP,)(__VA_ARGS__) #define EACH(e,v) for(auto& e : v) #define PERM(v) sort((v).begin(),(v).end());for(bool c##p=1;c##p;c##p=next_permutation((v).begin(),(v).end())) #define ADD(a,b) a=(a+ll(b))%MOD #define MUL(a,b) a=(a*ll(b))%MOD inline ll MOP(ll x,ll n,ll m=MOD){ll r=1;while(n>0){if(n&1)(r*=x)%=m;(x*=x)%=m;n>>=1;}return r;} inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}inline ll POW(ll a,ll b){ll c=1ll;do{if(b&1)c*=1ll*a;a*=1ll*a;}while(b>>=1);return c;} template<typename T,typename A,typename B> inline bool between(T x,A a,B b) {return ((a<=x)&&(x<b));}template<class T> inline T sqr(T x){return x*x;} template<typename A,typename B> inline bool chmax(A &a,const B &b){if(a<b){a=b;return 1;}return 0;} template<typename A,typename B> inline bool chmin(A &a,const B &b){if(a>b){a=b;return 1;}return 0;} #define tmax(x,y,z) max((x),max((y),(z))) #define tmin(x,y,z) min((x),min((y),(z))) #define PB push_back #define MP make_pair #define MT make_tuple #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define SORT(v) sort((v).begin(),(v).end()) #define RSORT(v) sort((v).rbegin(),(v).rend()) #define EXIST(s,e) (find((s).begin(),(s).end(),(e))!=(s).end()) #define EXISTST(s,c) (((s).find(c))!=string::npos) #define POSL(x,val) (lower_bound(x.begin(),x.end(),val)-x.begin()) #define POSU(x,val) (upper_bound(x.begin(),x.end(),val)-x.begin()) #define GEQ(x,val) (int)(x).size() - POSL((x),(val)) #define GREATER(x,val) (int)(x).size() - POSU((x),(val)) #define LEQ(x,val) POSU((x),(val)) #define LESS(x,val) POSL((x),(val)) #define SZV(a) int((a).size()) #define SZA(a) sizeof(a)/sizeof(a[0]) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) #define MEMINF(a) memset(a,0x3f,sizeof(a)) #define FILL(a,b) memset(a,b,sizeof(a)) #define UNIQUE(v) sort((v).begin(),(v).end());(v).erase(unique((v).begin(),(v).end()),(v).end()) struct abracadabra{ abracadabra(){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(20); cerr << fixed << setprecision(5); }; } ABRACADABRA; //TEMPLATE END---------------8<---------------8<---------------8<---------------8<---------------// namespace FFT{ using dbl = double; struct num{ dbl x,y; num(){x=y=0;} num(dbl x,dbl y):x(x),y(y){} }; inline num operator+(num a,num b){ return num(a.x+b.x,a.y+b.y); } inline num operator-(num a,num b){ return num(a.x-b.x,a.y-b.y); } inline num operator*(num a,num b){ return num(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x); } inline num conj(num a){ return num(a.x,-a.y); } int base=1; vector<num> rts={{0,0},{1,0}}; vector<int> rev={0,1}; const dbl PI=acosl(-1.0); void ensure_base(int nbase){ if(nbase<=base) return; rev.resize(1<<nbase); for(int i=0;i<(1<<nbase);i++) rev[i]=(rev[i>>1]>>1)+((i&1)<<(nbase-1)); rts.resize(1<<nbase); while(base<nbase){ dbl angle=2*PI/(1<<(base+1)); for(int i=1<<(base-1);i<(1<<base);i++){ rts[i<<1]=rts[i]; dbl angle_i=angle*(2*i+1-(1<<base)); rts[(i<<1)+1]=num(cos(angle_i),sin(angle_i)); } base++; } } void fft(vector<num> &a,int n=-1){ if(n==-1) n=a.size(); assert((n&(n-1))==0); int zeros=__builtin_ctz(n); ensure_base(zeros); int shift=base-zeros; for(int i=0;i<n;i++) if(i<(rev[i]>>shift)) swap(a[i],a[rev[i]>>shift]); for(int k=1;k<n;k<<=1){ for(int i=0;i<n;i+=2*k){ for(int j=0;j<k;j++){ num z=a[i+j+k]*rts[j+k]; a[i+j+k]=a[i+j]-z; a[i+j]=a[i+j]+z; } } } } vector<num> fa; template<typename T> vector<Int> multiply(const vector<T> &a,const vector<T> &b){ int need=a.size()+b.size()-1; int nbase=0; while((1<<nbase)<need) nbase++; ensure_base(nbase); int sz=1<<nbase; if(sz>(int)fa.size()) fa.resize(sz); for(int i=0;i<sz;i++){ int x=(i<(int)a.size()?a[i]:0); int y=(i<(int)b.size()?b[i]:0); fa[i]=num(x,y); } fft(fa,sz); num r(0,-0.25/sz); for(int i=0;i<=(sz>>1);i++){ int j=(sz-i)&(sz-1); num z=(fa[j]*fa[j]-conj(fa[i]*fa[i]))*r; if(i!=j) fa[j]=(fa[i]*fa[i]-conj(fa[j]*fa[j]))*r; fa[i]=z; } fft(fa,sz); vector<Int> res(need); for(int i=0;i<need;i++) res[i]=fa[i].x+0.5; return res; } }; struct bigint { using ll = long long; using vll = vector<ll>; constexpr static ll base = 1000000000; constexpr static ll base_digits = 9; vll a; ll sign; bigint():sign(1){} bigint(ll v){*this=v;} bigint(const string &s){read(s);} void operator=(const bigint &v){ sign=v.sign; a=v.a; } void operator=(ll v){ sign=1; if(v<0) sign=-1,v=-v; for(;v>0;v=v/base) a.push_back(v%base); } bigint operator+(const bigint &v) const{ if(sign==v.sign){ bigint res=v; for(ll i=0,carry=0;i<(ll)max(a.size(),v.a.size())||carry;++i){ if(i==(ll)res.a.size()) res.a.push_back(0); res.a[i]+=carry+(i<(ll)a.size()?a[i]:0); carry=res.a[i]>=base; if(carry) res.a[i]-=base; } return res; } return *this -(-v); } bigint operator-(const bigint &v) const{ if(sign==v.sign){ if(abs()>=v.abs()){ bigint res=*this; for(ll i=0,carry=0;i<(ll)v.a.size()||carry;++i){ res.a[i]-=carry+(i<(ll)v.a.size()?v.a[i]:0); carry=res.a[i]<0; if(carry) res.a[i]+=base; } res.trim(); return res; } return -(v-*this); } return *this+(-v); } void operator*=(ll v){ if(v<0) sign=-sign,v=-v; for(ll i=0,carry=0;i<(ll)a.size()|| carry;++i){ if(i ==(ll)a.size()) a.push_back(0); ll cur=a[i] *(ll)v+carry; carry=(ll)(cur/base); a[i]=(ll)(cur%base); // asm("divl %%ecx" : "=a"(carry),"=d"(a[i]) : "A"(cur),"c"(base)); } trim(); } bigint operator*(ll v) const{ bigint res=*this; res *=v; return res; } friend pair<bigint,bigint> divmod(const bigint &a1,const bigint &b1){ ll norm=base/(b1.a.back()+1); bigint a=a1.abs()*norm; bigint b=b1.abs()*norm; bigint q,r; q.a.resize(a.a.size()); for(ll i=a.a.size()-1;i>=0;i--){ r *=base; r+=a.a[i]; ll s1=r.a.size()<=b.a.size() ? 0 : r.a[b.a.size()]; ll s2=r.a.size()<=b.a.size()-1 ? 0 : r.a[b.a.size()-1]; ll d=((ll)base*s1+s2)/b.a.back(); r-=b*d; while(r<0) r+=b,--d; q.a[i]=d; } q.sign=a1.sign*b1.sign; r.sign=a1.sign; q.trim(); r.trim(); return make_pair(q,r/norm); } bigint operator/(const bigint &v) const{ return divmod(*this,v).first; } bigint operator%(const bigint &v) const{ return divmod(*this,v).second; } void operator/=(ll v){ if(v<0) sign=-sign,v=-v; for(ll i=(ll)a.size()-1,rem=0;i>=0;--i){ ll cur=a[i]+rem *(ll)base; a[i]=(ll)(cur/v); rem=(ll)(cur%v); } trim(); } bigint operator/(ll v) const{ bigint res=*this; res/=v; return res; } ll operator%(ll v) const{ if(v<0) v=-v; ll m=0; for(ll i=a.size()-1;i>=0;--i) m=(a[i]+m *(ll)base)%v; return m*sign; } void operator+=(const bigint &v){ *this=*this+v; } void operator-=(const bigint &v){ *this=*this-v; } void operator*=(const bigint &v){ *this=*this*v; } void operator/=(const bigint &v){ *this=*this/v; } bool operator<(const bigint &v) const{ if(sign!=v.sign) return sign<v.sign; if(a.size()!=v.a.size()) return a.size()*sign<v.a.size()*v.sign; for(ll i=a.size()-1;i>=0;i--) if(a[i]!=v.a[i]) return a[i]*sign<v.a[i]*sign; return false; } bool operator>(const bigint &v) const{ return v<*this; } bool operator<=(const bigint &v) const{ return !(v<*this); } bool operator>=(const bigint &v) const{ return !(*this<v); } bool operator==(const bigint &v) const{ return !(*this<v)&&!(v<*this); } bool operator!=(const bigint &v) const{ return *this<v|| v<*this; } void trim(){ while(!a.empty()&&!a.back()) a.pop_back(); if(a.empty()) sign=1; } bool isZero() const{ return a.empty()||(a.size()==1&&!a[0]); } bigint operator-() const{ bigint res=*this; res.sign=-sign; return res; } bigint abs() const{ bigint res=*this; res.sign*=res.sign; return res; } ll longValue() const{ ll res=0; for(ll i=a.size()-1;i>=0;i--) res=res*base+a[i]; return res*sign; } friend bigint gcd(const bigint &a,const bigint &b){ return b.isZero() ? a : gcd(b,a%b); } friend bigint lcm(const bigint &a,const bigint &b){ return a/gcd(a,b)*b; } void read(const string &s){ sign=1; a.clear(); ll pos=0; while(pos<(ll)s.size()&&(s[pos]=='-'|| s[pos]=='+')){ if(s[pos]=='-') sign=-sign; ++pos; } for(ll i=s.size()-1;i>=pos;i-=base_digits){ ll x=0; for(ll j=max(pos,i-base_digits+1);j<=i;j++) x=x*10+s[j]-'0'; a.push_back(x); } trim(); } friend istream &operator>>(istream &stream,bigint &v){ string s; stream>>s; v.read(s); return stream; } friend ostream &operator<<(ostream &stream,const bigint &v){ if(v.sign==-1) stream<<'-'; stream<<(v.a.empty()?0:v.a.back()); for(ll i=(ll)v.a.size()-2;i>=0;--i) stream<<setw(base_digits)<<setfill('0')<<v.a[i]; return stream; } static vll convert_base(const vll &a,ll old_digits,ll new_digits){ vll p(max(old_digits,new_digits)+1); p[0]=1; for(ll i=1;i<(ll)p.size();i++) p[i]=p[i-1]*10; vll res; ll cur=0; ll cur_digits=0; for(ll i=0;i<(ll)a.size();i++){ cur+=a[i]*p[cur_digits]; cur_digits+=old_digits; while(cur_digits>=new_digits){ res.push_back(signed(cur%p[new_digits])); cur/=p[new_digits]; cur_digits-=new_digits; } } res.push_back((signed)cur); while(!res.empty()&&!res.back()) res.pop_back(); return res; } static vll karatsubaMultiply(const vll &a,const vll &b){ ll n=a.size(); vll res(n+n); if(n<=32){ for(ll i=0;i<n;i++) for(ll j=0;j<n;j++) res[i+j]+=a[i]*b[j]; return res; } ll k=n>>1; vll a1(a.begin(),a.begin()+k); vll a2(a.begin()+k,a.end()); vll b1(b.begin(),b.begin()+k); vll b2(b.begin()+k,b.end()); vll a1b1=karatsubaMultiply(a1,b1); vll a2b2=karatsubaMultiply(a2,b2); for(ll i=0;i<k;i++) a2[i]+=a1[i]; for(ll i=0;i<k;i++) b2[i]+=b1[i]; vll r=karatsubaMultiply(a2,b2); for(ll i=0;i<(ll)a1b1.size();i++) r[i]-=a1b1[i]; for(ll i=0;i<(ll)a2b2.size();i++) r[i]-=a2b2[i]; for(ll i=0;i<(ll)r.size();i++) res[i+k]+=r[i]; for(ll i=0;i<(ll)a1b1.size();i++) res[i]+=a1b1[i]; for(ll i=0;i<(ll)a2b2.size();i++) res[i+n]+=a2b2[i]; return res; } bigint operator*(const bigint &v) const{ constexpr static ll nbase = 10000; constexpr static ll nbase_digits = 4; vll a=convert_base(this->a,base_digits,nbase_digits); vll b=convert_base(v.a,base_digits,nbase_digits); /* while(a.size()<b.size()) a.push_back(0); while(b.size()<a.size()) b.push_back(0); while(a.size() &(a.size()-1)) a.push_back(0),b.push_back(0); vll c=karatsubaMultiply(a,b); */ if(a.empty()) a.push_back(0); if(b.empty()) b.push_back(0); vll c=FFT::multiply(a,b); bigint res; res.sign=sign*v.sign; for(ll i=0,carry=0;i<(ll)c.size();i++){ ll cur=c[i]+carry; res.a.push_back((ll)(cur%nbase)); carry=(ll)(cur/nbase); if(i+1==(int)c.size()&&carry>0) c.push_back(0); } res.a=convert_base(res.a,nbase_digits,base_digits); res.trim(); return res; } }; const int MAX_BIT = 1850; void out(int _1, int _2, int _3) { // print(_1, _2, _3); bigint res = 0; REP(i, _1 + _2 + _3) { res *= 2; if (i < _1 || i >= _1 + _2) { res += 1; } } print(res); } signed main() { SS(ll, N); ll tmp = 0; ll M, digit; REP(i, MAX_BIT) { tmp += i * (i - 1) / 2 + 1; if (tmp == N) { out(i + 1, 0, 0); return 0; } if (tmp > N) { digit = i + 1; break; } M = N - tmp; } // 初期状態: 1がdigit個ならんでいる REP(l, 1, digit) { REP(r, l + 1, digit) { int _1 = l; int _2 = r - l; int _3 = digit - r; ll tmp = _3 + (_2 + _3 - 1) * (_1 - 1) + _1 * (_1 - 1) / 2; // print(_1, _2, _3, tmp); if (tmp == M) { out(_1, _2, _3); return 0; } } } // debug(M, digit); }