QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#385691#5107. Mosaic BrowsingSolitaryDream#WA 526ms99212kbC++173.4kb2024-04-10 23:17:142024-04-10 23:17:15

Judging History

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

  • [2024-04-10 23:17:15]
  • 评测
  • 测评结果:WA
  • 用时:526ms
  • 内存:99212kb
  • [2024-04-10 23:17:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define double long double
using cpx=complex<double>;
#define int long long

const double pi=acos(-1);

const int N=5e3+1e2+7,P=998244353;

int qpow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)
            ret=ret*a%P;
        b>>=1;
        a=a*a%P;
    }
    return ret;
}

int na,ma,nb,mb;

mt19937 rng(58);

int col[111],rev[N];

int w[N];

int a[N][N],b[N][N];

int tmp[N];

void dft(int *a,int len)
{
    for(int i=1;i<len;i++)
        if(i>rev[i])
            swap(a[i],a[rev[i]]);
    for(int d=1;d<len;d<<=1)
        for(int m=d<<1,i=0;i<len;i+=m)
            for(int j=0;j<d;j++)
            {
                int tmp=a[i+j+d]*w[len/m*j]%P;
                a[i+j+d]=(a[i+j]-tmp)%P;
                a[i+j]=(a[i+j]+tmp)%P;
            }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i=1;i<=100;i++)
    {
        int w;
        int ok;
        do {
            w=rng()%P;
            ok=1;
            for(int j=0;j<i;j++)
                if(w==col[j])
                    ok=0;
        }while(ok==0);
        col[i]=w;
    }
    int len=2048;
    for(int i=1;i<len;i++)
        rev[i]=rev[i>>1]>>1|(i&1?len>>1:0);
    w[0]=1;
    w[1]=qpow(3,(P-1)/len);
    for(int i=2;i<len;i++)
        w[i]=w[i-1]*w[1]%P;
    cin>>na>>ma;
    int ha=0;
    for(int i=0;i<na;i++)
        for(int j=0;j<ma;j++)
        {
            int x;
            cin>>x;
            a[na-1-i][ma-1-j]=col[x];
            ha+=col[x]*col[x];
            ha%=P;
        }
    for(int i=0;i<len;i++)
    {
        for(int j=0;j<len;j++)
            tmp[j]=a[i][j];
        dft(tmp,len);
        for(int j=0;j<len;j++)
            a[i][j]=tmp[j];
    }
    
    for(int j=0;j<len;j++)
    {
        for(int i=0;i<len;i++)
            tmp[i]=a[i][j];
        dft(tmp,len);
        for(int i=0;i<len;i++)
            a[i][j]=tmp[i];
    }
    
    cin>>nb>>mb;
    for(int i=1;i<=nb;i++)
        for(int j=1;j<=mb;j++)
        {
            int x;
            cin>>x;
            b[i-1][j-1]=col[x];
        }
        
    for(int i=0;i<len;i++)
    {
        for(int j=0;j<len;j++)
            tmp[j]=b[i][j];
        dft(tmp,len);
        for(int j=0;j<len;j++)
            b[i][j]=tmp[j];
    }
    
    for(int j=0;j<len;j++)
    {
        for(int i=0;i<len;i++)
            tmp[i]=b[i][j];
        dft(tmp,len);
        for(int i=0;i<len;i++)
            b[i][j]=tmp[i];
    }
    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++)
            a[i][j]=a[i][j]*b[i][j]%P;

    
    int inv=qpow(len,P-2);
    for(int i=0;i<len;i++)
    {
        for(int j=0;j<len;j++)
            tmp[j]=a[i][j];
        reverse(tmp+1,tmp+len);
        dft(tmp,len);
        for(int j=0;j<len;j++)
            a[i][j]=tmp[j]*inv%P;
    }
    
    for(int j=0;j<len;j++)
    {
        for(int i=0;i<len;i++)
            tmp[i]=a[i][j];
        reverse(tmp+1,tmp+len);
        dft(tmp,len);
        for(int i=0;i<len;i++)
            a[i][j]=tmp[i]*inv%P;
    }
    vector<pair<int,int> >ans;
    for(int i=na-1;i<=nb-na+1;i++)
        for(int j=ma-1;j<=mb-ma+1;j++)
        {
            int w=a[i][j];
            w=(w%P+P)%P;
            if(w==ha)
                ans.push_back({i-na+1,j-ma+1});
        }
    cout<<ans.size()<<"\n";
    for(auto [x,y]:ans)
        cout<<x+1<<" "<<y+1<<"\n";
}

详细

Test #1:

score: 0
Wrong Answer
time: 526ms
memory: 99212kb

input:

100 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
...

output:

1212
1 1
1 101
1 201
1 301
2 1
2 101
2 201
2 301
3 1
3 101
3 201
3 301
4 1
4 101
4 201
4 301
5 1
5 101
5 201
5 301
6 1
6 101
6 201
6 301
7 1
7 101
7 201
7 301
8 1
8 101
8 201
8 301
9 1
9 101
9 201
9 301
10 1
10 101
10 201
10 301
11 1
11 101
11 201
11 301
12 1
12 101
12 201
12 301
13 1
13 101
13 201
...

result:

wrong answer 1st lines differ - expected: '2005', found: '1212'