QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#67525	#2680. 白兔之舞	alpha1022	100 ✓	652ms	22704kb	C++23	6.5kb	2022-12-10 16:58:03	2022-12-10 16:58:05

Judging History

This is the latest submission verdict.

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-12-10 16:58:05]
Judged

Verdict: 100
Time: 652ms
Memory: 22704kb

Show

[2022-12-10 16:58:03]
Submitted

answer

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define add(a,b) (a + b >= mod ? a + b - mod : a + b)
#define dec(a,b) (a < b ? a - b + mod : a - b)
using namespace std;
const int N = 3;
const int K = 1 << 16;
int n,k,ki,L,x,y,mod,len;
int G,rt[K + 5],ans[K + 5];
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
struct Matrix
{
    int a[N + 5][N + 5];
    inline Matrix()
    {
        memset(a,0,sizeof a);
    }
    inline Matrix(int)
    {
        memset(a,0,sizeof a);
        for(register int i = 1;i <= n;++i)
            a[i][i] = 1;
    }
    inline int *operator[](const int &x)
    {
        return a[x];
    }
    inline const int *operator[](const int &x) const
    {
        return a[x];
    }
    inline Matrix operator*(const int &x) const
    {
        Matrix ret;
        for(register int i = 1;i <= n;++i)
            for(register int j = 1;j <= n;++j)
                ret[i][j] = (long long)a[i][j] * x % mod;
        return ret;
    }
    inline Matrix operator+(const Matrix &o) const
    {
        Matrix ret;
        for(register int i = 1;i <= n;++i)
            for(register int j = 1;j <= n;++j)
                ret[i][j] = (a[i][j] + o[i][j]) % mod;
        return ret;
    }
    inline Matrix operator*(const Matrix &o) const
    {
        Matrix ret;
        for(register int i = 1;i <= n;++i)
            for(register int j = 1;j <= n;++j)
                for(register int k = 1;k <= n;++k)
                    ret[i][j] = (ret[i][j] + (long long)a[i][k] * o[k][j]) % mod;
        return ret;
    }
} w;
inline Matrix fpow(Matrix a,int b)
{
    Matrix ret(1);
    for(;b;b >>= 1)
        (b & 1) && (ret = ret * a,1),a = a * a;
    return ret;
}
namespace Poly
{
    const int N = 1 << 18;
    const double pi = acos(-1);
    const int W = 1 << 15;
    int n;
    int lg2[N + 5],rev[N + 5];
    struct poly
    {
        int a[N + 5];
        inline const int &operator[](int x) const
        {
            return a[x];
        }
        inline int &operator[](int x)
        {
            return a[x];
        }
        inline void clear(int x = 0)
        {
            memset(a + x,0,(N - x + 1) << 2);
        }
    } f,g;
    struct cp
    {
        double a,b;
        inline void operator+=(const cp &o)
        {
            a += o.a,b += o.b;
        }
        inline cp operator+(const cp &o) const
        {
            return (cp){a + o.a,b + o.b};
        }
        inline cp operator-(const cp &o) const
        {
            return (cp){a - o.a,b - o.b};
        }
        inline cp operator*(const cp &o) const
        {
            return (cp){a * o.a - b * o.b,a * o.b + b * o.a};
        }
        inline void operator*=(const cp &o)
        {
            *this = *this * o;
        }
        inline cp operator*(const double &o) const
        {
            return (cp){a * o,b * o};
        }
        inline cp operator~() const
        {
            return (cp){a,-b};
        }
    } rt[N + 5];
    inline void init(int len)
    {
        for(n = 1;n < len;n <<= 1);
        for(register int i = 2;i <= n;++i)
            lg2[i] = lg2[i >> 1] + 1;
        for(register int i = 0;i <= (n >> 1);++i)
            rt[(n >> 1) + i] = (cp){cos(2 * pi * i / n),sin(2 * pi * i / n)};
        for(register int i = (n >> 1) - 1;i;--i)
            rt[i] = rt[i << 1];
    }
    inline void fft(cp *a,int type,int n)
    {
        type == -1 && (reverse(a + 1,a + n),1);
        int lg = lg2[n] - 1;
        for(register int i = 0;i < n;++i)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lg),
            i < rev[i] && (swap(a[i],a[rev[i]]),1);
        for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
            for(register int i = 0;i < n;i += w)
                for(register int j = 0;j < m;++j)
                {
                    cp t = rt[m | j] * a[i | j | m];
                    a[i | j | m] = a[i | j] - t,a[i | j] += t;
                }
        if(type == -1)
            for(register int i = 0;i < n;++i)
                a[i].a /= n,a[i].b /= n;
    }
    inline void mul(poly &a,const poly &b,int n)
    {
        static cp f[N + 5],g[N + 5],h[N + 5];
        int lim = 1;
        memset(f,0,sizeof f),memset(g,0,sizeof g);
        for(;lim < (n << 1);lim <<= 1);
        for(register int i = 0;i < n;++i)
            f[i] = (cp){a[i] / W,a[i] % W},g[i] = (cp){b[i] / W,b[i] % W};
        fft(f,1,lim),fft(g,1,lim);
        for(register int i = 0;i < lim;++i)
            h[i] = ~f[(lim - i) % lim];
        for(register int i = 0;i < lim;++i)
            f[i] *= g[i],g[i] *= h[i];
        fft(f,-1,lim),fft(g,-1,lim);
        for(register int i = 0;i < lim;++i)
        {
            long long ac = (f[i].a + g[i].a) / 2 + 0.5;
            long long bd = g[i].a - ac + 0.5;
            long long bcad = f[i].b + 0.5;
            a[i] = ((ac % mod * W % mod * W % mod) % mod + (bcad % mod * W % mod) % mod + bd % mod) % mod;
        }
    }
}
int p[N + 5],t,cnt;
int main()
{
    scanf("%d%d%d%d%d%d",&n,&k,&L,&x,&y,&mod);
    len = k << 1,Poly::init(len << 1);
    t = mod - 1;
    for(register int i = 2;i * i <= t;++i)
    {
        if(!(t % i))
            p[++cnt] = i;
        for(;!(t % i);t /= i);
    }
    t > 1 && (p[++cnt] = t);
    for(register int i = 2,flag;i < mod;++i)
    {
        flag = 1;
        for(register int j = 1;j <= cnt;++j)
            if(fpow(i,(mod - 1) / p[j]) == 1)
            {
                flag = 0;
                break;
            }
        if(flag)
        {
            G = i;
            break;
        }
    }
    for(register int i = 0;i < k;++i)
        rt[i] = fpow(G,(mod - 1) / k * i);
    for(register int i = 1;i <= n;++i)
        for(register int j = 1;j <= n;++j)
            scanf("%d",w.a[i] + j);
    for(register int i = 0;i < k;++i)
        Poly::f[i] = (long long)fpow(w * rt[i] + Matrix(1),L)[x][y] * rt[(long long)i * (i - 1) / 2 % k] % mod;
    for(register int i = 0;i < len - 1;++i)
        Poly::g[len - i - 1] = rt[(k - (long long)i * (i - 1) / 2 % k) % k];
    Poly::mul(Poly::f,Poly::g,len);
    ki = fpow(k,mod - 2);
    for(register int i = 0;i < k;++i)
        ans[i] = (long long)Poly::f[len - i - 1] * rt[(long long)i * (i - 1) / 2 % k] % mod * ki % mod;
    for(register int i = 0;i < k;++i)
        printf("%d\n",ans[i]);
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10

Accepted

time: 516ms

memory: 22600kb

input:

3 60868 28281 3 2 997261313
541377333 663518765 140473546
710072468 931907445 481102683
305037615 409799686 182541807

output:

result:

ok 60868 lines

Test #2:

score: 10

Accepted

time: 522ms

memory: 22600kb

input:

3 60868 87117 3 1 997261313
412700968 717333471 192489438
784392110 821696732 949091933
8361642 752502310 726930970

output:

result:

ok 60868 lines

Test #3:

score: 10

Accepted

time: 169ms

memory: 22672kb

input:

1 65536 10016911 1 1 997261313
1

output:

result:

ok 65536 lines

Test #4:

score: 10

Accepted

time: 179ms

memory: 22704kb

input:

1 65536 20544218 1 1 997261313
437647132

output:

result:

ok 65536 lines

Test #5:

score: 10

Accepted

time: 138ms

memory: 22612kb

input:

1 50906 10066288 1 1 776061971
1

output:

result:

ok 50906 lines

Test #6:

score: 10

Accepted

time: 141ms

memory: 22576kb

input:

1 50906 14193447 1 1 776061971
7058676

output:

result:

ok 50906 lines

Test #7:

score: 10

Accepted

time: 352ms

memory: 22676kb

input:

2 65536 15489019 1 2 997261313
81819404 229263011
752816130 408725138

output:

result:

ok 65536 lines

Test #8:

score: 10

Accepted

time: 316ms

memory: 22632kb

input:

2 65536 69511249 1 1 997261313
500289590 382459525
578601485 187892897

output:

result:

ok 65536 lines

Test #9:

score: 10

Accepted

time: 630ms

memory: 22456kb

input:

3 50906 57946722 1 1 776061971
647247752 742197886 79186200
237641887 308607445 80891991
134069917 377341939 143644495

output:

result:

ok 50906 lines

Test #10:

score: 10

Accepted

time: 652ms

memory: 22408kb

input:

3 50906 93980303 1 2 776061971
505745611 708180844 233942141
7793688 560919932 211232826
486943270 62469440 149793907

output:

result:

ok 50906 lines