QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #829878 | #1264. Lower Algorithmics | World_Creater | WA | 479ms | 47192kb | C++17 | 1.0kb | 2024-12-24 14:30:20 | 2024-12-24 14:30:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,l,r,lim=1<<21,rev[3000005],ans;
complex<double> a[3000005],b[3000005];
const double pi=acos(-1),eps=1e-7;
void FFT(complex<double> a[],int inv)
{
for(int i=0;i<=lim;i++)
{
if(i<rev[i]) swap(a[i],a[rev[i]]);
}
for(int w=1;w<lim;w*=2)
{
complex<double> com(cos(pi/w),inv*sin(pi/w));
for(int i=0;i<lim;i+=w*2)
{
complex<double> o(1,0);
for(int j=0;j<w;j++)
{
complex<double> x=a[i+j],y=o*a[i+j+w];
a[i+j]=x+y,a[i+j+w]=x-y;
o*=com;
}
}
}
}
int main()
{
cin>>n>>l>>r;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[x]=complex<double>(1,0);
}
for(int i=0;i<lim;i++)
{
rev[i]=(rev[i>>1]>>1);
if(i&1) rev[i]|=lim>>1;
}
FFT(a,1);
for(int i=0;i<lim;i++)
{
if(fabs(a[i].imag())<eps&&fabs(a[i].real()-1)<eps) a[i]*=r-l+1;
else a[i]=(pow(a[i],r+1)-pow(a[i],l))/(a[i]-(complex<double>(1,0)));
}
FFT(a,-1);
for(int i=0;i<lim;i++)
{
if(fabs(a[i].real()/lim)>eps) ans++;
}
cout<<ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 217ms
memory: 46880kb
input:
2 1 2 1 2
output:
4
result:
ok answer is '4'
Test #2:
score: 0
Accepted
time: 221ms
memory: 47092kb
input:
3 1 3 1 3 10
output:
18
result:
ok answer is '18'
Test #3:
score: 0
Accepted
time: 227ms
memory: 47184kb
input:
6 3 5 1 2 3 4 5 6
output:
28
result:
ok answer is '28'
Test #4:
score: 0
Accepted
time: 236ms
memory: 47192kb
input:
3 1 3 1 3 4
output:
12
result:
ok answer is '12'
Test #5:
score: -100
Wrong Answer
time: 479ms
memory: 46876kb
input:
500 1 2000 6 8 9 10 11 14 16 19 23 24 25 30 31 33 34 38 44 46 48 49 52 53 55 56 58 60 64 65 68 69 70 71 72 74 75 77 79 81 83 84 88 89 93 95 98 103 105 108 109 110 111 118 119 120 121 123 125 129 130 132 134 136 137 138 140 141 144 149 154 155 159 160 161 163 165 166 169 170 172 173 174 175 176 177 1...
output:
0
result:
wrong answer expected '1999990', found '0'