QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#816982#9870. ItemsCoffinsWA 159ms13972kbC++141.8kb2024-12-16 19:33:292024-12-16 19:33:31

Judging History

你现在查看的是最新测评结果

  • [2024-12-16 19:33:31]
  • 评测
  • 测评结果:WA
  • 用时:159ms
  • 内存:13972kb
  • [2024-12-16 19:33:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1<<19;
const int p=998244353;
const int ig=(p+1)/3;
int n,l,a[N],q,r;ll m;
ll f[N],g[N],A[N],B[N];int rv[N];
ll ksm(ll a,ll b)
{
    ll ans=1;while(b)
    {
        if(b&1)ans=ans*a%p;
        a=a*a%p,b>>=1;
    }return ans;
}
void init(int n)
{
    for(int i=0;i<n;i++)
    {
        rv[i]=rv[i>>1]>>1;
        if(i&1)rv[i]|=(n>>1);
    }
}void NTT(ll *a,int n,int o)
{
    for(int i=0;i<n;i++)
    if(rv[i]<i)swap(a[i],a[rv[i]]);
    for(int d=1;d<n;d<<=1)
    {
        ll bs=ksm(ig,(p-1)/d/2);
        if(~o)bs=ksm(bs,p-2);
        for(int i=0;i<n;i+=(d<<1))
        {
            ll vl=1;
            for(int j=i;j<i+d;j++)
            {
                ll x=a[j],y=a[j+d]*vl%p;
                a[j]=(x+y)%p,a[j+d]=(x+p-y)%p;
                vl=vl*bs%p;
            }
        }
    }if(o==-1)
    {
        const ll vl=ksm(n,p-2);
        for(int i=0;i<n;i++)
        a[i]=a[i]*vl%p;
    }
}void mul(ll *f,ll *g,int d)
{
    for(int i=0;i<l;i++)A[i]=f[i];
    for(int i=0;i<l;i++)B[i]=g[i];
    NTT(A,l,1),NTT(B,l,1);
    for(int i=0;i<l;i++)
    A[i]=A[i]*B[i]%p;
    NTT(A,l,-1);
    for(int i=0;i<l;i++)
    if(i+d<l&&A[i+d])f[i]=1;
    else f[i]=0;
}void calc(int k)
{
    if(!k)return;
    calc(k>>1);
    mul(g,g,n);
    if(k&1)mul(g,f,q);
}
void solve()
{
    cin>>n>>m;q=m/n,r=m%n;
    l=1;while(l<=(n<<2))l<<=1;init(l);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<l;i++)f[i]=0;
    for(int i=0;i<l;i++)g[i]=0;g[n]=1;
    for(int i=1;i<=n;i++)f[a[i]]=1;
    calc(n);if(g[r+n])cout<<"Yes\n";
    else cout<<"No\n";
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;while(t--)solve();return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 13900kb

input:

4
5 25
0 0 0 0 5
5 11
4 4 4 5 5
5 0
1 2 3 4 5
5 25
0 1 2 3 4

output:

Yes
No
No
No

result:

ok 4 token(s): yes count is 1, no count is 3

Test #2:

score: 0
Accepted
time: 19ms
memory: 13972kb

input:

1314
1 0
0
1 0
1
1 1
0
1 1
1
2 0
0 0
2 0
0 1
2 0
0 2
2 0
1 0
2 0
1 1
2 0
1 2
2 0
2 0
2 0
2 1
2 0
2 2
2 1
0 0
2 1
0 1
2 1
0 2
2 1
1 0
2 1
1 1
2 1
1 2
2 1
2 0
2 1
2 1
2 1
2 2
2 2
0 0
2 2
0 1
2 2
0 2
2 2
1 0
2 2
1 1
2 2
1 2
2 2
2 0
2 2
2 1
2 2
2 2
2 3
0 0
2 3
0 1
2 3
0 2
2 3
1 0
2 3
1 1
2 3
1 2
2 3
2 0...

output:

Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
No
Yes
No
No
No
Yes
No
Yes
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
Yes
No
Yes
No
No
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
No
No
No
Yes
No
No
No
Yes
Yes
Yes...

result:

ok 1314 token(s): yes count is 732, no count is 582

Test #3:

score: 0
Accepted
time: 159ms
memory: 13840kb

input:

10000
4 1
0 0 0 0
4 1
0 0 0 1
4 1
0 0 0 2
4 1
0 0 0 3
4 1
0 0 0 4
4 1
0 0 1 0
4 1
0 0 1 1
4 1
0 0 1 2
4 1
0 0 1 3
4 1
0 0 1 4
4 1
0 0 2 0
4 1
0 0 2 1
4 1
0 0 2 2
4 1
0 0 2 3
4 1
0 0 2 4
4 1
0 0 3 0
4 1
0 0 3 1
4 1
0 0 3 2
4 1
0 0 3 3
4 1
0 0 3 4
4 1
0 0 4 0
4 1
0 0 4 1
4 1
0 0 4 2
4 1
0 0 4 3
4 1
0 ...

output:

No
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
No
No
Yes
No
No
No
No
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
No
No
Yes
No
No
No
No
Yes
No
No
No
No
Yes
No
No
No
Yes
Yes
Yes
Yes
...

result:

ok 10000 token(s): yes count is 6168, no count is 3832

Test #4:

score: 0
Accepted
time: 31ms
memory: 13916kb

input:

1612
5 0
0 0 0 0 0
5 0
1 1 1 1 1
5 0
0 1 1 1 1
5 0
2 2 2 2 2
5 0
0 2 2 2 2
5 0
1 2 2 2 2
5 0
0 1 2 2 2
5 0
3 3 3 3 3
5 0
0 3 3 3 3
5 0
1 3 3 3 3
5 0
0 1 3 3 3
5 0
2 3 3 3 3
5 0
0 2 3 3 3
5 0
1 2 3 3 3
5 0
0 1 2 3 3
5 0
4 4 4 4 4
5 0
0 4 4 4 4
5 0
1 4 4 4 4
5 0
0 1 4 4 4
5 0
2 4 4 4 4
5 0
0 2 4 4 4
5...

output:

Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
No
No
Yes
No
No
No
Yes
No
No
No
Yes
No
No
No
Yes
No
No
No
Yes
No
No
No
Yes
No
No
No...

result:

ok 1612 token(s): yes count is 864, no count is 748

Test #5:

score: -100
Wrong Answer
time: 96ms
memory: 13964kb

input:

4662
6 0
0 0 0 0 0 0
6 0
1 1 1 1 1 1
6 0
0 1 1 1 1 1
6 0
2 2 2 2 2 2
6 0
0 2 2 2 2 2
6 0
1 2 2 2 2 2
6 0
0 1 2 2 2 2
6 0
3 3 3 3 3 3
6 0
0 3 3 3 3 3
6 0
1 3 3 3 3 3
6 0
0 1 3 3 3 3
6 0
2 3 3 3 3 3
6 0
0 2 3 3 3 3
6 0
1 2 3 3 3 3
6 0
0 1 2 3 3 3
6 0
4 4 4 4 4 4
6 0
0 4 4 4 4 4
6 0
1 4 4 4 4 4
6 0
0 1...

output:

Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes...

result:

wrong answer expected NO, found YES [68th token]