QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#500140#5547. Short Functionarnold518RE 0ms4096kbC++171.6kb2024-07-31 23:00:302024-07-31 23:00:35

Judging History

This is the latest submission verdict.

  • [2024-07-31 23:00:35]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 4096kb
  • [2024-07-31 23:00:30]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int P = 998244353;
const int MAXN = 1e5;

int N, K, A[MAXN+10];

ll mpow(ll a, ll b, ll mod)
{
    ll ret=1;
    while(b)
    {
        if(b&1) ret=ret*a%mod;
        a=a*a%mod; b>>=1;
    }
    return ret;
}

int phi(int X)
{
    int ans=1;
    for(int i=2; i*i<=X; i++)
    {
        int val;
        for(val=1; X%i==0; X/=i) val*=i;
        ans*=val-val/i;
    }
    if(X>1) ans*=X-1;
    return ans;
}

typedef __int128 dll;
ll mmod(dll x, ll m) { return (x % m + m) % m; }
ll get_inv(ll a, ll b) {
	return (b == 1) ? 0 : mmod((1 - (dll)b * get_inv(b, a % b)) / (a % b), b);
}

mt19937 rng(1557);
ll rnd(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    scanf("%d%d", &N, &K);
    // for(int i=0; i<N; i++) A[i]=rnd(1, P-1);
    for(int i=0; i<N; i++) scanf("%d", &A[i]);

    int M=mpow(2, K, N);
    int G=__gcd(N, P-1);
    int t=((mpow(2, K, P-1)-M)%(P-1)+(P-1))%(P-1)/G;
    ll val=1ll*t*get_inv(N, (P-1)/G)%((P-1)/G);

    // printf("!%d %d %d %lld %lld\n", M, G, t, val, mpow(N/G, phi((P-1)/G), (P-1)/G));

    ll mul=1;
    for(int i=0; i<N; i++) mul=mul*A[i]%P;
    mul=mpow(mul, val, P);
    // printf("%lld\n", mul);

    t=1;
    for(int i=0; i<M; i++) t=1ll*t*A[i]%P;
    for(int i=0; i<N; i++)
    {
        printf("%lld ", (t*mul)%P);
        t=1ll*t*A[(i+M)%N]%P;
        t=1ll*t*mpow(A[i], P-2, P)%P;
    }
    printf("\n");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 2
1 2 3 4 5

output:

24 120 60 40 30 

result:

ok 5 number(s): "24 120 60 40 30"

Test #2:

score: -100
Runtime Error

input:

8 3
12 5 16 14 10 6 9 2

output:


result: