QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#74271 | #5433. Absolute Difference | zhangboju# | WA | 2ms | 3576kb | C++14 | 4.4kb | 2023-01-31 12:44:38 | 2023-01-31 12:44:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
x=0;short f=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x*=f;return;
}
namespace polynomial{
#define poly vector<int>
#define ull unsigned long long
const int N=4e6+5;
const int mod=998244353,G=3,Gi=332748118;
int r[N];
bool is_init;
int qpow(int a,int k)
{
int res=1;
while(k)
{
if(k&1) res=1ll*res*a%mod;
a=1ll*a*a%mod;
k>>=1;
}
return res;
}
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int dec(int x,int y){return x>=y?x-y:x-y+mod;}
ull w[N],c[N];
void init()
{
const int n=262144*4;
int t=qpow(3,(mod-1)/n);
w[n>>1]=1;
for(int i=(n>>1)+1;i<n;++i) w[i]=w[i-1]*t%mod;
for(int i=(n>>1)-1;i;--i) w[i]=w[i<<1];
}
void NTT(vector<int> &f,int n,int op)
{
if(!is_init) is_init=1,init();
copy(f.begin(),f.end(),c);
for(int i=0;i<n;++i)
{
r[i]=((r[i>>1]>>1)|((i&1)?(n>>1):0));
if(i<r[i]) swap(c[i],c[r[i]]);
}
for(int i=1;i<n;i<<=1)
for(int j=0;j<n;j+=i*2)
for(int k=0;k<i;++k)
{
ull t=w[i+k]*c[i+j+k]%mod;
c[i+j+k]=c[j+k]-t+mod;
c[j+k]+=t;
}
for(int i=0;i<n;++i) f[i]=c[i]%mod;
if(op==-1)
{
int t=qpow(n,mod-2);
for(int i=0;i<n;++i) f[i]=1ll*f[i]*t%mod;
reverse(f.begin()+1,f.end());
}
}
poly mul(poly a,poly b)
{
int ed=a.size()+b.size()-1,k=1;
while(k<a.size()+b.size()) k<<=1;
a.resize(k,0),b.resize(k,0);
NTT(a,k,1),NTT(b,k,1);
for(int i=0;i<k;++i) a[i]=1ll*a[i]*b[i]%mod;
NTT(a,k,-1);
while(a.size()>ed) a.pop_back();
return a;
}
void get_inv(poly &f,poly &g,int len)
{
if(len==1) return g[0]=qpow(f[0],mod-2),void();
get_inv(f,g,(len+1)>>1);
int k=1;
while(k<2*len) k<<=1;
g.resize(k,0);
poly c(k);
for(int i=0;i<len;++i) c[i]=f[i];
for(int i=len;i<k;++i) c[i]=0;
NTT(c,k,1);NTT(g,k,1);
for(int i=0;i<k;++i) g[i]=1ll*dec(2,1ll*c[i]*g[i]%mod)*g[i]%mod;
NTT(g,k,-1);
for(int i=len;i<k;++i) g[i]=0;
}
poly inv(poly f,int n)
{
poly invf(n);
f.resize(n,0);
get_inv(f,invf,n);
while(invf.size()>n) invf.pop_back();
return invf;
}
poly R(poly f)
{
poly a=f;
reverse(a.begin(),a.end());
return a;
}
pair<poly,poly> div(poly f,poly g)
{
poly gr=R(g),fr=R(f);
poly invgr=inv(gr,f.size());
poly qr=mul(fr,invgr);
while(qr.size()>f.size()-g.size()+1) qr.pop_back();
poly q=R(qr);
poly res=mul(g,q);
int k=f.size();
poly r(k);
for(int i=0;i<k;++i) r[i]=dec(f[i],res[i]);
while(r.size()&&r.back()==0) r.pop_back();
return {q,r};
}
poly dev(poly f)
{
int k=f.size();
poly g(k);
for(int i=1;i<k;++i) g[i-1]=1ll*f[i]*i%mod;
g[k-1]=0;
return g;
}
poly dev_inv(poly f)
{
int k=f.size();
poly g(k+1);
for(int i=1;i<=k;++i) g[i]=1ll*f[i-1]*qpow(i,mod-2)%mod;
g[0]=0;
return g;
}
poly ln(poly f,int len)
{
poly a=dev(f),b=inv(f,len);
a=mul(a,b);
poly g=dev_inv(a);
return g;
}
void get_exp(poly &f,poly &g,int len)
{
if(len==1) return g[0]=1,void();
get_exp(f,g,(len+1)>>1);
int k=1;
while(k<len*2) k<<=1;
poly d=ln(g,len);
poly e(k,0);
for(int i=0;i<len;++i) e[i]=f[i];
d.resize(k,0),g.resize(k,0);
NTT(g,k,1),NTT(d,k,1),NTT(e,k,1);
for(int i=0;i<k;++i) g[i]=1ll*dec(add(e[i],1),d[i])*g[i]%mod;
NTT(g,k,-1);
for(int i=len;i<k;++i) g[i]=0;
}
poly exp(poly f)
{
int k=f.size();
poly g(k);
get_exp(f,g,k);
return g;
}
poly sqrt(poly f)
{
int k=f.size();
poly t=ln(f,k);
int inv=qpow(2,mod-2);
for(int i=0;i<k;++i) t[i]=1ll*t[i]*inv%mod;
while(t.size()>k) t.pop_back();
poly g=exp(t);
while(g.size()>f.size()) g.pop_back();
return g;
}
poly qpow(poly f,int k)
{
int n=f.size();
poly g=ln(f,n);
for(int i=0;i<n;++i) g[i]=1ll*g[i]*k%mod;
poly t=exp(g);
return t;
}
}
using namespace polynomial;
int n,m;
double A,B;
int main()
{
read(n),read(m);
for(int i=1;i<=n;++i)
{
int l,r;read(l),read(r);
A+=(r-l)/2.0;
}
for(int i=1;i<=m;++i)
{
int l,r;read(l),read(r);
B+=(r-l)/2.0;
}
A/=n,B/=m;
printf("%.10lf",fabs(A-B));
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3576kb
input:
1 1 0 1 0 1
output:
0.0000000000
result:
wrong answer 1st numbers differ - expected: '0.3333333', found: '0.0000000', error = '0.3333333'