QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #759361 | #9727. Barkley III | zzuqy | WA | 0ms | 3932kb | C++14 | 12.8kb | 2024-11-18 02:58:10 | 2024-11-18 02:58:12 |
Judging History
answer
#include<bits/stdc++.h>
#define MOD 1000000007
#define double long double
#define N 506
int n,m;
long long x[N];
double v[N];
long long invm,inv2;
long long ff[N],gg[N],*f=ff,*g=gg;
struct Ask{
int i,j;
double n,m;
};
Ask ask[N*N];
int pos[N];
inline long long power(long long a, long long b){
long long ans=1;
while(b){
if(b&1) ans=ans*a%MOD;
a=a*a%MOD;b>>=1;
}
return ans;
}
inline void mul(long long pos){
long long p=pos;
long long q=n-pos;
// p=(p+inv2)%MOD;
// q=(q+inv2)%MOD;
for(int i=0;i<=m;i++){
g[i]=f[i]*q%MOD;
}
for(int i=0;i<m;i++){
g[i+1]=(g[i+1]+f[i]*p%MOD)%MOD;
}
std::swap(f,g);
}
inline void div(long long pos){
if(!pos){
long long q=n-pos;
// q=(q+inv2)%MOD;
long long inv=power(q,MOD-2);
for(int i=0;i<=m;i++){
f[i]=f[i]*inv%MOD;
}
return;
}
long long p=pos;
long long q=n-p;
// p=(p+inv2)%MOD;
// q=(q+inv2)%MOD;
long long invp=power(p,MOD-2);
for(int i=m;i>=1;i--){
g[i-1]=f[i]*invp%MOD;
f[i-1]=(f[i-1]-q*g[i-1]%MOD+MOD)%MOD;
}
std::swap(f,g);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",x+i);
x[i]=-x[i];
}
for(int i=1;i<=m;i++){
scanf("%Lf",v+i);
// v[i]=(v[i]+i*power(1000000,MOD-2)%MOD)%MOD;
v[i]+=i*0.0000001;
}
std::sort(x+1,x+1+n);
int cnt=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
ask[++cnt]=(Ask){i,j,x[j],v[i]};
}
}
std::sort(ask+1,ask+1+cnt,[](const Ask &a,const Ask &b){
return a.n/a.m<b.n/b.m;
});
double nown=0,nowm=1;
long long ans=0,now;
invm=power(m,MOD-2);
// inv2=power(2,MOD-2);
f[0]=power(n,m);
// f[0]=power((n+1)%MOD,m);
// f[0]=1;
// for(int i=1;i<=m;i++){
// mul(0);
// }
for(int i=1;i<=m;i++){
pos[i]=0;
}
// static int que[N*N];
// int top=-1;
for(int k=1;k<=cnt;k++){
nown=ask[k].n;
nowm=ask[k].m;
// if(nown*ask[k-1].m!=nowm*ask[k-1].n){
// while(top>0){
// div(que[top]-1);
// mul(que[top]);
// top--;
// }
// top=-1;
// }
for(int i=1;i<=m;i++){
int last=pos[i];
while(pos[i]+1<=n&&x[pos[i]+1]/v[i]<=nown/nowm){
pos[i]++;
}
if(last!=pos[i]){
div(last);
// if(x[pos[i]]*nowm!=v[i]*nown)
mul(pos[i]);
// else{
// if(top==-1){
// mul(pos[i]);
// top=0;
// }
// else{
// que[++top]=pos[i];
// mul(pos[i]-1);
// }
// }
}
}
div(pos[ask[k].i]);
// nowm=(nowm-ask[k].i*power(1000000,MOD-2)%MOD+MOD)%MOD;
// printf(">>>%.10lf\n",nowm);
now=f[m/2]*(long long)nown%MOD*power((long long)nowm,MOD-2)%MOD;
ans=(ans+now)%MOD;
mul(pos[ask[k].i]);
}
for(int i=1;i<=m;i++){
ans=ans*power(n,MOD-2)%MOD;
}
printf("%lld\n",ans%MOD);
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3932kb
input:
5 9 7 7 7 6 7 3 1 5 2 1 3 3 1 5 3 1 3 1 1 2 3 3 1 3 2 2 8 3 1 3 3 1 2
output:
-714666674
result:
wrong answer 1st lines differ - expected: '7', found: '-714666674'