QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#43288 | #4495. Shinobu loves trip | BobWang | AC ✓ | 999ms | 14292kb | C++ | 1.4kb | 2022-08-08 20:24:13 | 2022-08-08 20:24:15 |
Judging History
answer
#include<set>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define maxn 1005
#define maxt 200005
using namespace std;
struct node
{
ll st;
int d;
}po[maxn];
const int mt=200000;
ll p,a,x[maxn],s[maxt];
int t,n,q,tot;
int ans[maxn];
set<ll>mp;
bool cmp(node x,node y)
{
return x.d<y.d;
}
ll mul(ll x,ll y)
{
ll ret=1;
while(y)
{
if(y&1)
ret=(ret*x)%p;
x=(x*x)%p;
y>>=1;
}
return ret;
}
ll inv(ll x)
{
return mul(x,p-2);
}
void solve()
{
for(int i=1;i<=n;++i)//按照天数从小到大枚举计划
{
while(tot<po[i].d)
{
tot++;
s[tot]=(s[tot-1]*a)%p;
mp.insert(s[tot]);
}
for(int j=1;j<=q;++j)
{
if(x[j]==0)
continue;
ll val=(x[j]*po[i].st)%p;
if(mp.find(val)!=mp.end())
ans[j]++;
}
}
}
int main()
{
// freopen("g.in","r",stdin);
s[0]=1;
scanf("%d",&t);
while(t--)
{
mp.clear();
mp.insert(1);
int cnt=0;
tot=0;
memset(ans,0,sizeof(ans));
scanf("%lld%lld%d%d",&p,&a,&n,&q);
for(int i=1;i<=n;++i)
{
scanf("%lld%d",&po[i].st,&po[i].d);
if(po[i].st==0)
cnt++;
else
po[i].st=inv(po[i].st);
}
sort(po+1,po+1+n,cmp);
for(int i=1;i<=q;++i)
scanf("%lld",&x[i]);
solve();
for(int i=1;i<=q;++i)
{
if(x[i]!=0)
printf("%d\n",ans[i]);
else printf("%d\n",cnt);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 999ms
memory: 14292kb
input:
5 999999937 4628 1000 1000 162585517 24584 407438671 108585 46973547 132178 142179754 23710 198067620 130706 829852550 190969 676555968 2127 717426372 80994 332054419 1078 471194333 66473 105470508 154839 939339406 89663 73289403 90982 529133484 198011 526081635 28219 405427868 174742 120011816 6408...
output:
167 166 168 168 174 169 2 167 169 22 153 169 150 163 7 152 149 166 166 176 63 178 125 170 94 167 155 173 56 147 163 169 167 183 78 165 179 173 182 170 166 150 152 166 169 169 169 173 162 52 180 182 170 163 173 173 175 150 171 166 170 148 170 166 63 168 172 151 150 72 129 14 61 167 167 169 174 133 17...
result:
ok 5000 lines