結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
![]() |
提出日時 | 2021-01-05 23:15:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 92 ms / 5,000 ms |
コード長 | 5,681 bytes |
コンパイル時間 | 1,483 ms |
コンパイル使用メモリ | 132,956 KB |
最終ジャッジ日時 | 2025-01-17 09:50:57 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include<iostream>#include<array>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<random>#include<map>#include<set>#include<complex>#include<bitset>#include<stack>#include<unordered_map>#include<utility>#include<tuple>#include<cassert>using namespace std;typedef long long ll;typedef unsigned int ui;const ll mod = 998244353;const ll INF = (ll)1000000007 * 1000000007;typedef pair<int, int> P;#define stop char nyaa;cin>>nyaa;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)typedef long double ld;const ld eps = 1e-8;const ld pi = acos(-1.0);typedef pair<ll, ll> LP;int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};template<class T>bool chmax(T &a, const T &b) {if(a<b){a=b;return 1;}return 0;}template<class T>bool chmin(T &a, const T &b) {if(b<a){a=b;return 1;}return 0;}template<int mod>struct ModInt {long long x;static constexpr int MOD = mod;ModInt() : x(0) {}ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}explicit operator int() const {return x;}ModInt &operator+=(const ModInt &p) {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 ModInt &p) {x = (int)(1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}ModInt operator-() const { return ModInt(-x); }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(0); }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }ModInt inverse() const{int a = x, b = mod, u = 1, v = 0, t;while(b > 0) {t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}return ModInt(u);}ModInt power(long long n) const {ModInt ret(1), mul(x);while(n > 0) {if(n & 1)ret *= mul;mul *= mul;n >>= 1;}return ret;}ModInt power(const ModInt p) const{return ((ModInt)x).power(p.x);}friend ostream &operator<<(ostream &os, const ModInt<mod> &p) {return os << p.x;}friend istream &operator>>(istream &is, ModInt<mod> &a) {long long x;is >> x;a = ModInt<mod>(x);return (is);}};using modint = ModInt<mod>;constexpr int bmds(int x){const int v[] = {1012924417, 924844033, 998244353,897581057, 645922817};return v[x];}constexpr int brts(int x){const int v[] = {5, 5, 3, 3, 3};return v[x];}template<int X>struct NTT{static constexpr int md = bmds(X);static constexpr int rt = brts(X);using M = ModInt<md>;vector< vector<M> > rts,rrts;void ensure_base(int n){if((int)rts.size()>=n) return;rts.resize(n);rrts.resize(n);for(int i=1;i<n;i<<=1){if(!rts[i].empty()) continue;M w=M(rt).power((md-1)/(i<<1));M rw=w.inverse();rts[i].resize(i);rrts[i].resize(i);rts[i][0]=M(1);rrts[i][0]=M(1);for(int k=1;k<i;k++){rts[i][k]=rts[i][k-1]*w;rrts[i][k]=rrts[i][k-1]*rw;}}}void ntt(vector<M> &as,bool f){int n=as.size();assert((n&(n-1))==0);ensure_base(n);for(int i=0,j=1;j+1<n;j++){for(int k=n>>1;k>(i^=k);k>>=1);if(i>j) swap(as[i],as[j]);}for(int i=1;i<n;i<<=1){for(int j=0;j<n;j+=i*2){for(int k=0;k<i;k++){M z=as[i+j+k]*(f?rrts[i][k]:rts[i][k]);as[i+j+k]=as[j+k]-z;as[j+k]+=z;}}}if(f){M tmp=M(n).inverse();for(int i=0;i<n;i++) as[i]*=tmp;}}vector<M> multiply(vector<M> as,vector<M> bs){int need=as.size()+bs.size()-1;int sz=1;while(sz<need) sz<<=1;as.resize(sz,M(0));bs.resize(sz,M(0));ntt(as,0);ntt(bs,0);for(int i=0;i<sz;i++) as[i]*=bs[i];ntt(as,1);as.resize(need);return as;}vector<int> multiply(vector<int> as,vector<int> bs){vector<M> am(as.size()),bm(bs.size());for(int i=0;i<(int)am.size();i++) am[i]=M(as[i]);for(int i=0;i<(int)bm.size();i++) bm[i]=M(bs[i]);vector<M> cm=multiply(am,bm);vector<int> cs(cm.size());for(int i=0;i<(int)cs.size();i++) cs[i]=cm[i].x;return cs;}};template<int X> constexpr int NTT<X>::md;template<int X> constexpr int NTT<X>::rt;int n,q;NTT<2> ntt;void solve(){cin >> n >> q;vector<modint> A(n),B(n);rep(i,n) cin >> A[i];rep(i,q){int r;cin >> r;B[(n-r)%n]+=1;}vector<modint> ans=ntt.multiply(A,B);rep(i,n){cout << ans[i]+ans[i+n] << " ";}cout << "" << endl;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(50);solve();}