yukicoder No.931 - Multiplicative Convolution

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLay（version 20191123-1）のコード

C++に変換後のコードはこちら

#define MD 998244353
int P, A[1d5], B[1d5], c[1d5];
Mint x[1d5], y[1d5], z[2d5];
{
  int i, k, r;
  rd(P,A(P-1),B(P-1));
  r = primitiveRoot(P);
  rep(i,P-1){
    k = powmod(r,i,P);
    x[i] = A[k-1];
    y[i] = B[k-1];
  }
  convolution(x,P-1,y,P-1,z,2*P-2);
  rep(i,P-1){
    k = powmod(r,i,P);
    c[k-1] = z[i] + z[i+P-1];
  }
  wt(c(P-1));
}

Current time: 2024年04月27日05時48分02秒
Last modified: 2019年11月23日19時24分42秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)