QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#500140 | #5547. Short Function | arnold518 | RE | 0ms | 4096kb | C++17 | 1.6kb | 2024-07-31 23:00:30 | 2024-07-31 23:00:35 |
Judging History
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