結果
| 問題 | No.303 割れません |
| ユーザー |
 beet
|
| 提出日時 | 2019-12-17 20:41:38 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 747 ms / 10,000 ms |
| コード長 | 17,438 bytes |
| コンパイル時間 | 3,033 ms |
| コンパイル使用メモリ | 232,384 KB |
| 実行使用メモリ | 27,312 KB |
| 最終ジャッジ日時 | 2024-07-04 13:56:18 |
| 合計ジャッジ時間 | 10,232 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 281 ms
12,388 KB |
| testcase_04 | AC | 598 ms
21,756 KB |
| testcase_05 | AC | 564 ms
21,148 KB |
| testcase_06 | AC | 578 ms
21,480 KB |
| testcase_07 | AC | 727 ms
25,920 KB |
| testcase_08 | AC | 724 ms
27,312 KB |
| testcase_09 | AC | 747 ms
26,712 KB |
| testcase_10 | AC | 2 ms
5,376 KB |
| testcase_11 | AC | 571 ms
21,232 KB |
| testcase_12 | AC | 741 ms
27,000 KB |
| testcase_13 | AC | 317 ms
14,028 KB |
| testcase_14 | AC | 298 ms
14,740 KB |
| testcase_15 | AC | 141 ms
7,784 KB |
| testcase_16 | AC | 2 ms
5,376 KB |
ソースコード
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
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=asinl(1)*2;
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> &as){
int n=as.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(as[i],as[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=as[i+j+k]*rts[j+k];
as[i+j+k]=as[i+j]-z;
as[i+j]=as[i+j]+z;
}
}
}
}
template<typename T>
vector<long long> multiply(vector<T> &as,vector<T> &bs){
int need=as.size()+bs.size()-1;
int nbase=0;
while((1<<nbase)<need) nbase++;
ensure_base(nbase);
int sz=1<<nbase;
vector<num> fa(sz);
for(int i=0;i<sz;i++){
T x=(i<(int)as.size()?as[i]:0);
T y=(i<(int)bs.size()?bs[i]:0);
fa[i]=num(x,y);
}
fft(fa);
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);
vector<long long> res(need);
for(int i=0;i<need;i++)
res[i]=round(fa[i].x);
return res;
}
};
//END CUT HERE
#ifndef call_from_test
signed main(){
int n;
cin>>n;
vector<int> as(n+1,0),bs(n+1,0);
for(int i=1;i<=n;i++) cin>>as[i]>>bs[i];
auto cs=FFT::multiply(as,bs);
for(int i=1;i<=n*2;i++) cout<<cs[i]<<"\n";
return 0;
}
/*
verified on 2019/12/17
https://atcoder.jp/contests/atc001/tasks/fft_c
*/
#endif
#undef call_from_test
#endif
//BEGIN CUT HERE
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);}
static bigint add_identity(){return bigint(0);}
static bigint mul_identity(){return bigint(1);}
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;
}
};
//END CUT HERE
#ifndef call_from_test
#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T>
struct BIT{
int n;
vector<T> bit;
//1-indexed
BIT(int n_):n(n_+1),bit(n,0){}
T sum(int i){
T s(0);
for(int x=i;x>0;x-=(x&-x))
s+=bit[x];
return s;
}
void add(int i,T a){
if(i==0) return;
for(int x=i;x<=n;x+=(x&-x))
bit[x]+=a;
}
int lower_bound(int w){
if(w<=0) return 0;
int x=0,r=1;
while(r<n) r<<=1;
for(int k=r;k>0;k>>=1){
if(x+k<=n&&bit[x+k]<w){
w-=bit[x+k];
x+=k;
}
}
return x+1;
}
// [l, r)
T query(int l,int r){
return sum(r-1)-sum(l-1);
}
T sum0(int i){
return sum(i+1);
}
void add0(int i,T a){
add(i+1,a);
}
T query0(int l,int r){
return sum(r)-sum(l);
}
};
//END CUT HERE
#ifndef call_from_test
#define call_from_test
#include "../tools/fastio.cpp"
#undef call_from_test
// lower_bound
signed ARC033_C(){
int q;
cin>>q;
BIT<int> bit(2e5);
while(q--){
int t,x;
cin>>t>>x;
if(t==1) bit.add(x,1);
if(t==2){
int k=bit.lower_bound(x);
bit.add(k,-1);
cout<<k<<endl;
}
}
return 0;
}
/*
verified on 2019/11/11
https://atcoder.jp/contests/arc033/tasks/arc033_3
*/
signed main(){
ARC033_C();
return 0;
}
#endif
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename R, size_t N>
struct SquareMatrix{
typedef array<R, N> arr;
typedef array<arr, N> mat;
mat dat;
SquareMatrix(){
for(size_t i=0;i<N;i++)
for(size_t j=0;j<N;j++)
dat[i][j]=R::add_identity();
}
bool operator==(const SquareMatrix& a) const{
return dat==a.dat;
}
size_t size() const{return N;}
arr& operator[](size_t k){return dat[k];}
const arr& operator[](size_t k) const {return dat[k];}
static SquareMatrix add_identity(){return SquareMatrix();}
static SquareMatrix mul_identity(){
SquareMatrix res;
for(size_t i=0;i<N;i++) res[i][i]=R::mul_identity();
return res;
}
SquareMatrix operator*(const SquareMatrix &B) const{
SquareMatrix res;
for(size_t i=0;i<N;i++)
for(size_t j=0;j<N;j++)
for(size_t k=0;k<N;k++)
res[i][j]=res[i][j]+(dat[i][k]*B[k][j]);
return res;
}
SquareMatrix operator+(const SquareMatrix &B) const{
SquareMatrix res;
for(size_t i=0;i<N;i++)
for(size_t j=0;j<N;j++)
res[i][j]=dat[i][j]+B[i][j];
return res;
}
SquareMatrix pow(long long n) const{
SquareMatrix a=*this,res=mul_identity();
while(n){
if(n&1) res=res*a;
a=a*a;
n>>=1;
}
return res;
}
};
//END CUT HERE
#ifndef call_from_test
#define call_from_test
#include "../tools/fastio.cpp"
#include "../tools/compress.cpp"
#include "../mod/mint.cpp"
#include "../segtree/basic/ushi.cpp"
#undef call_from_test
//INSERT ABOVE HERE
signed YAHOO2019_FINAL_D(){
using ll = long long;
using M = Mint<int>;
using MM = SquareMatrix<M, 2>;
int n,q;
cin>>n>>q;
vector<ll> ts(q),ls(q),rs(q),ps(q);
for(ll i=0;i<q;i++){
cin>>ts[i];
if(ts[i]==1) cin>>ps[i];
if(ts[i]==2) cin>>ls[i]>>rs[i];
}
vector<ll> vs;
for(ll i=0;i<q;i++){
if(ts[i]==1){
vs.emplace_back(ps[i]);
vs.emplace_back(ps[i]+1);
vs.emplace_back(ps[i]+2);
vs.emplace_back(ps[i]+3);
}
if(ts[i]==2){
vs.emplace_back(ls[i]);
vs.emplace_back(ls[i]+1);
vs.emplace_back(rs[i]);
vs.emplace_back(rs[i]+1);
}
}
vs.emplace_back(0);
vs.emplace_back(n+1);
vs=compress(vs);
auto ms=dict(vs);
MM A;
A[0][0]=M(1);A[0][1]=M(1);
A[1][0]=M(1);A[1][1]=M(0);
vector<MM> vt(vs.size()-1,A);
for(ll i=0;i+1<(ll)vs.size();i++){
vt[i]=A.pow(vs[i+1]-vs[i]);
}
MM I=MM::mul_identity();
auto f=[&](MM a,MM b){return b*a;};
SegmentTree<MM> seg(f,I);
seg.build(vt);
vector<int> used(vs.size(),0);
for(ll i=0;i<q;i++){
if(ts[i]==1){
ll k=ms[ps[i]];
used[k]^=1;
MM B;
for(ll j=k;j<=k+2;j++){
if(used[j]){
B[0][0]=M(0);B[0][1]=M(0);
B[1][0]=M(1);B[1][1]=M(0);
}else{
B[0][0]=M(!used[j-1]);B[0][1]=M(!used[j-2]);
B[1][0]=M(1);B[1][1]=M(0);
}
seg.set_val(j,B);
}
}
if(ts[i]==2){
ll l=ms[ls[i]],r=ms[rs[i]];
if(used[l]){
cout<<0<<"\n";
continue;
}
auto B=seg.query(l+1,r+1);
cout<<B[0][0].v<<"\n";
}
}
cout<<flush;
return 0;
}
/*
verified on 2019/10/29
https://atcoder.jp/contests/yahoo-procon2019-final/tasks/yahoo_procon2019_final_d
*/
signed DDCC2019_FINAL_D(){
string s;
cin>>s;
struct M{
uint32_t v;
M(){*this=add_identity();}
M(uint32_t v):v(v){}
M operator+(const M &a)const{return M(v+a.v);}
M operator*(const M &a)const{return M(v*a.v);}
static M add_identity(){return M(0);}
static M mul_identity(){return M(1);}
};
using SM = SquareMatrix<M, 6>;
auto f=[](SM a,SM b){return a*b;};
SM ti=SM::mul_identity();
SegmentTree<SM> seg(f,ti);
vector<SM> vt(s.size(),ti);
for(int i=0;i<(int)s.size();i++){
if(s[i]=='D') vt[i][0][1]=1;
if(s[i]=='I') vt[i][1][2]=1;
if(s[i]=='S') vt[i][2][3]=1;
if(s[i]=='C') vt[i][3][4]=1;
if(s[i]=='O') vt[i][4][5]=1;
}
seg.build(vt);
int q;
cin>>q;
for(int i=0;i<q;i++){
int l,r;
cin>>l>>r;
l--;
cout<<seg.query(l,r)[0][5].v<<"\n";
}
cout<<flush;
return 0;
}
/*
verified on 2019/10/29
https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_d
*/
signed main(){
//YAHOO2019_FINAL_D();
//DDCC2019_FINAL_D();
return 0;
}
#endif
#undef call_from_test
//INSERT ABOVE HERE
using ll = long long;
signed YUKI_129(){
bigint MOD = 1000000000;
ll n,m;
cin>>n>>m;
n/=1000;
n%=m;
bigint res(1);
for(int i=0;i<n;i++){
res*=m-i;
res/=i+1;
}
cout<<res%MOD<<endl;
return 0;
}
/*
verified on 2019/12/17
https://yukicoder.me/problems/no/129
*/
signed YUKI_303(){
ll l;
cin>>l;
if(l==2){
cout<<3<<endl;
cout<<"INF"<<endl;
return 0;
}
cout<<l<<endl;
using M = SquareMatrix<bigint, 2>;
M A;
A[0][0]=1;A[0][1]=1;
A[1][0]=1;A[1][1]=0;
if(l&1) cout<<A.pow(l)[1][0]<<endl;
else{
auto B=A.pow(l/2);
auto X=(B*B)[1][0];
auto Y=B[1][0];
cout<<X-Y*Y<<endl;
}
return 0;
}
/*
verified on 2019/12/17
https://yukicoder.me/problems/no/303
*/
const int MAX = 1e5+100;
ll dp[MAX];
pair<bigint, bigint> dfs(int l,int r){
if(l+1>=r) return make_pair(bigint(dp[l]),bigint(l+1));
int m=(l+r)>>1;
auto v=dfs(l,m);
auto t=dfs(m,r);
t.first*=v.second;
t.first+=v.first;
t.second*=v.second;
return t;
}
signed YUKI_696(){
int n;
cin>>n;
vector<int> p(n);
for(int i=0;i<n;i++) cin>>p[i];
BIT<ll> bit(n+1);
for(int i=0;i<n;i++) bit.add(p[i],1);
for(int i=0;i<n;i++){
dp[n-(i+1)]=bit.sum(p[i]-1);
bit.add(p[i],-1);
}
cout<<bigint(dfs(0,n).first+1)<<endl;
return 0;
}
/*
verified on 2019/12/17
https://yukicoder.me/problems/no/696
*/
signed main(){
//YUKI_129();
YUKI_303();
//YUKI_696();
return 0;
}
#endif