結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
|
提出日時 | 2021-04-08 00:59:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 9,493 bytes |
コンパイル時間 | 920 ms |
コンパイル使用メモリ | 68,520 KB |
最終ジャッジ日時 | 2025-01-20 12:56:35 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
/home/tfuruta/repos/compro-library/lib/math/NumberTheoreticalTransform.cpp:14:12: error: ‘unordered_map’ does not name a type
ソースコード
#line 1 "NumberTheoreticalTransform.test.cpp"#define PROBLEM "https://yukicoder.me/problems/no/1307"#include <vector>#include <iostream>#include <algorithm>#include <array>using namespace std;#line 1 "/home/tfuruta/repos/compro-library/lib/util/ModInt.cpp"/** @title ModInt* @docs md/util/ModInt.md*/template<long long mod> class ModInt {public:long long x;constexpr ModInt():x(0) {}constexpr ModInt(long long y) : x(y>=0?(y%mod): (mod - (-y)%mod)%mod) {}ModInt &operator+=(const ModInt &p) {if((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator+=(const long long y) {ModInt p(y);if((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator+=(const int y) {ModInt p(y);if((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const long long y) {ModInt p(y);if((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const int y) {ModInt p(y);if((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (x * p.x % mod);return *this;}ModInt &operator*=(const long long y) {ModInt p(y);x = (x * p.x % mod);return *this;}ModInt &operator*=(const int y) {ModInt p(y);x = (x * p.x % mod);return *this;}ModInt &operator^=(const ModInt &p) {x = (x ^ p.x) % mod;return *this;}ModInt &operator^=(const long long y) {ModInt p(y);x = (x ^ p.x) % mod;return *this;}ModInt &operator^=(const int y) {ModInt p(y);x = (x ^ p.x) % mod;return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inv();return *this;}ModInt &operator/=(const long long y) {ModInt p(y);*this *= p.inv();return *this;}ModInt &operator/=(const int y) {ModInt p(y);*this *= p.inv();return *this;}ModInt operator=(const int y) {ModInt p(y);*this = p;return *this;}ModInt operator=(const long long y) {ModInt p(y);*this = p;return *this;}ModInt operator-() const {return ModInt(-x); }ModInt operator++() {x++;if(x>=mod) x-=mod;return *this;}ModInt operator--() {x--;if(x<0) x+=mod;return *this;}ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }ModInt operator^(const ModInt &p) const { return ModInt(*this) ^= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }ModInt inv() const {int a=x,b=mod,u=1,v=0,t;while(b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);} return ModInt(u);}ModInt pow(long long n) const {ModInt ret(1), mul(x);for(;n > 0;mul *= mul,n >>= 1) if(n & 1) ret *= mul;return ret;}friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;}friend istream &operator>>(istream &is, ModInt &a) {long long t;is >> t;a = ModInt<mod>(t);return (is);}};//using modint = ModInt<MOD>;#line 1 "/home/tfuruta/repos/compro-library/lib/math/NumberTheoreticalTransform.cpp"/** @title NumberTheoreticalTransform - 数論変換* @docs md/math/NumberTheoreticalTransform.md*/template<class T> class NumberTheoreticalTransform {inline static constexpr int prime1 =1004535809;inline static constexpr int prime2 =998244353;inline static constexpr int prime3 =985661441;inline static constexpr int inv21 =332747959; // ModInt<mod2>(mod1).inv().x;inline static constexpr int inv31 =766625513; // ModInt<mod3>(mod1).inv().x;inline static constexpr int inv32 =657107549; // ModInt<mod3>(mod2).inv().x;inline static constexpr long long prime12=(1002772198720536577LL);inline static constexpr int log2n_max = 21;static unordered_map<int,array<int,log2n_max>> base_map;using Mint = T;using Mint1 = ModInt<prime1>;using Mint2 = ModInt<prime2>;using Mint3 = ModInt<prime3>;inline static Mint garner(const Mint1& b1,const Mint2& b2,const Mint3& b3) {Mint2 t2 = (b2-b1.x)*inv21;Mint3 t3 = ((b3-b1.x)*inv31-t2.x)*inv32;return Mint(Mint(prime12)*t3.x+b1.x+prime1*t2.x);}template<int prime> inline static array<ModInt<prime>,log2n_max> get_base(int inv=0) {array<ModInt<prime>,log2n_max> base, es, ies;ModInt<prime> e = ModInt<prime>(3).pow((prime - 1) >> log2n_max), ie = e.inv();for (int i = log2n_max; i >= 2; --i) {es[i - 2] = e, ies[i - 2] = ie;e *= e, ie *= ie;}ModInt<prime> acc = 1;if(!inv) for (int i = 0; i < log2n_max - 2; ++i) {base[i] = es[i] * acc;acc *= ies[i];}else for (int i = 0; i < log2n_max - 2; ++i) {base[i] = ies[i] * acc;acc *= es[i];}return base;}template<int prime> inline static void butterfly(vector<ModInt<prime>>& a, const array<ModInt<prime>,log2n_max>& base) {int h = __builtin_ctz(a.size());for (int i = 0; i < h; i++) {int w = 1 << i, p = 1 << (h - (i+1));ModInt<prime> acc = 1;for (int s = 0; s < w; s++) {int offset = s << (h - i);for (int j = 0; j < p; ++j) {auto l = a[j + offset];auto r = a[j + offset + p] * acc;a[j + offset] = l + r;a[j + offset + p] = l - r;}acc *= base[__builtin_ctz(~(unsigned int)(s))];}}}template<int prime> inline static void ibutterfly(vector<ModInt<prime>>& a, const array<ModInt<prime>,log2n_max>& base) {int h = __builtin_ctz(a.size());for (int i = h-1; 0 <= i; i--) {int w = 1 << i, p = 1 << (h - (i+1));ModInt<prime> acc = 1;for (int s = 0; s < w; s++) {int offset = s << (h - i);for (int j = 0; j < p; ++j) {auto l = a[j + offset];auto r = a[j + offset + p];a[j + offset] = l + r;a[j + offset + p] = (l - r) * acc;}acc *= base[__builtin_ctz(~(unsigned int)(s))];}}}template<int prime> inline static vector<ModInt<prime>> convolution_friendrymod(vector<Mint> a,vector<Mint> b){int n = a.size(), m = b.size();if (!n || !m) return {};if (min(n, m) <= 60) {if (n < m) swap(n, m),swap(a, b);vector<ModInt<prime>> f(n+m-1);for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) f[i+j]+=a[i].x*b[j].x;return f;}int N,M=n+m-1; for(N=1;N<M;N*=2);ModInt<prime> inverse(N); inverse = inverse.inv();vector<ModInt<prime>> g(N,0),h(N,0);for(int i=0;i<a.size();++i) g[i]=a[i].x;for(int i=0;i<b.size();++i) h[i]=b[i].x;static array<ModInt<prime>,log2n_max> base;if(!base.front().x) base = get_base<prime>();static array<ModInt<prime>,log2n_max> ibase;if(!ibase.front().x) ibase = get_base<prime>(1);butterfly<prime>(g,base);butterfly<prime>(h,base);for(int i = 0; i < N; ++i) g[i] *= h[i];ibutterfly<prime>(g,ibase);for (int i = 0; i < n + m - 1; i++) g[i] *= inverse;return g;}inline static vector<Mint> convolution_arbitrarymod(const vector<Mint>& g,const vector<Mint>& h){auto f1 = convolution_friendrymod<prime1>(g, h);auto f2 = convolution_friendrymod<prime2>(g, h);auto f3 = convolution_friendrymod<prime3>(g, h);vector<Mint> f(f1.size());for(int i=0; i<f1.size(); ++i) f[i] = garner(f1[i],f2[i],f3[i]);return f;}public:inline static vector<long long> convolution(const vector<long long>& g,const vector<long long>& h) {vector<T> a(g.size()), b(h.size());transform(g.begin(),g.end(),a.begin(),[&](long long x){return T(x);});transform(h.begin(),h.end(),b.begin(),[&](long long x){return T(x);});auto c = convolution_arbitrarymod(a,b);vector<long long> f(g.size()+h.size()-1);transform(c.begin(),c.end(),f.begin(),[&](T x){return x.x;});return f;}inline static vector<ModInt<998244353>> convolution(const vector<ModInt<998244353>>& g,const vector<ModInt<998244353>>& h){returnconvolution_friendrymod<998244353>(g,h);}inline static vector<ModInt<1000000007>> convolution(const vector<ModInt<1000000007>>& g,const vector<ModInt<1000000007>>& h){returnconvolution_arbitrarymod(g,h);}// inline vector<RuntimeModInt<runtime_mod>> convolution(const vector<RuntimeModInt<runtime_mod>>& g,const vector<RuntimeModInt<runtime_mod>>& h){return convolution_arbitrarymod(g,h);}};#line 10 "NumberTheoreticalTransform.test.cpp"constexpr long long mod = 998244353;int main() {cin.tie(0);ios::sync_with_stdio(false);int N,Q; cin >> N >> Q;vector<ModInt<mod>> A(N),B(N,0),D(N,0);for(int i=0;i<N;++i) cin >> A[i];while(Q--){int r; cin >> r; B[N-1-r]+=1;}auto C = NumberTheoreticalTransform<ModInt<mod>>::convolution(A,B);for(int i=0;i<2*N-1;++i) {D[(i+1)%N]+=C[i];}for(int i=0;i<N;++i) cout << D[i] << " \n"[i==N-1];return 0;}