結果

問題 No.2272 多項式乗算 mod 258280327
ユーザー nagisa5101nagisa5101
提出日時 2023-04-14 23:18:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,129 bytes
コンパイル時間 5,234 ms
コンパイル使用メモリ 269,568 KB
実行使用メモリ 34,052 KB
最終ジャッジ日時 2024-04-18 21:00:09
合計ジャッジ時間 15,854 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 3 ms
6,944 KB
testcase_22 AC 3 ms
6,940 KB
testcase_23 AC 3 ms
6,940 KB
testcase_24 AC 31 ms
6,944 KB
testcase_25 AC 127 ms
6,940 KB
testcase_26 AC 128 ms
6,944 KB
testcase_27 AC 280 ms
7,520 KB
testcase_28 AC 276 ms
7,436 KB
testcase_29 AC 1,161 ms
18,492 KB
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;
using namespace atcoder;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repll(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep2(i, n, m) for (int i = n; i < (int)(m); i++)
#define repll2(i, n, m) for (long long i = n; i < (long long)(m); i++)
#define all(v) v.begin(),v.end()
using ll=long long;
using ld=long double;
using vi=vector<int>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vvvl=vector<vvl>;
using vld=vector<ld>;
using vvld=vector<vld>;

int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,1,-1};

const double PI = acos(-1);
//const ll MOD=1e9+7;
//const ll MOD=998244353;
const ll INF=(1LL<<60);
const int INF2=(1<<30);
//using mint=modint1000000007;
//using mint=modint998244353;
using mind=atcoder::modint;

// 特殊な剰余と原始根
// (924844033, 5)
// (998244353, 3)
// (1012924417, 5)
// (167772161, 3)
// (469762049, 3)
// (1224736769, 3)

vector<unsigned int> prime_list={924844033,998244353,1012924417,167772161,469762049,1224736769};
vector<unsigned int> root_list={5,3,5,3,3,3};
unsigned int MOD;
unsigned int root;
 
unsigned int add(const unsigned int x, const unsigned int y)
{
    return (x + y < MOD) ? x + y : x + y - MOD;
}
 
unsigned int sub(const unsigned int x, const unsigned int y)
{
    return (x >= y) ? (x - y) : (MOD - y + x);
}
 
unsigned int mul(const unsigned int x, const unsigned int y)
{
    return (unsigned long long)x * y % MOD;
}
 
unsigned int mod_pow(unsigned int x, unsigned int n)
{
    unsigned int res = 1;
    while(n > 0){
        if(n & 1){ res = mul(res, x); }
        x = mul(x, x);
        n >>= 1;
    }
    return res;
}
 
unsigned int inverse(const unsigned int x)
{
    return mod_pow(x, MOD - 2);
}
 
void ntt(vector<int>& a, const bool rev = false)
{
    unsigned int i, j, k, l, p, q, r, s;
    const unsigned int size = a.size();
    if(size == 1) return;
    vector<int> b(size);
    r = rev ? (MOD - 1 - (MOD - 1) / size) : (MOD - 1) / size;
    s = mod_pow(root, r);
    vector<unsigned int> kp(size / 2 + 1, 1);
    for(i = 0; i < size / 2; ++i) kp[i + 1] = mul(kp[i], s);
    for(i = 1, l = size / 2; i < size; i <<= 1, l >>= 1){
        for(j = 0, r = 0; j < l; ++j, r += i){
            for(k = 0, s = kp[i * j]; k < i; ++k){
                p = a[k + r], q = a[k + r + size / 2];
                b[k + 2 * r] = add(p, q);
                b[k + 2 * r + i] = mul(sub(p, q), s);
            }
        }
        swap(a, b);
    }
    if(rev){
        s = inverse(size);
        for(i = 0; i < size; i++){ a[i] = mul(a[i], s); }
    }
}
 
vector<int> convolute(const vector<int>& a, const vector<int>& b)
{
    const int size = (int)a.size() + (int)b.size() - 1;
    int t = 1;
    while(t < size){ t <<= 1; }
    vector<int> A(t, 0), B(t, 0);
    for(int i = 0; i < (int)a.size(); i++){ A[i] = a[i]; }
    for(int i = 0; i < (int)b.size(); i++){ B[i] = b[i]; }
    ntt(A), ntt(B);
    for (int i = 0; i < t; i++){ A[i] = mul(A[i], B[i]); }
    ntt(A, true);
    A.resize(size);
    return A;
}

template<typename T>
T mod_add(const T a, const T b, const T mod){
    return (a + b) % mod;
}
 
template<typename T>
T mod_mul(const T a, const T b, const T mod){
    return a * b % mod;
}
 
template<typename T>
T mod_inv(T a, T mod){
    T u[] = {a, 1, 0}, v[] = {mod, 0, 1}, t;
    while(*v){
        t = *u / *v;
        swap(u[0] -= t * v[0], v[0]);
        swap(u[1] -= t * v[1], v[1]);
        swap(u[2] -= t * v[2], v[2]);
    }
    u[1] %= mod;
    return (u[1] < 0) ? (u[1] + mod) : u[1];
}
 
template<typename T>
T garner(const vector<T>& a, vector<T> p, const T mod){
    const unsigned int sz = a.size();
    vector<T> kp(sz + 1, 0), rmult(sz + 1, 1);
    p.push_back(mod);
    for(unsigned int i = 0; i < sz; ++i){
        T x = mod_mul(a[i] - kp[i], mod_inv(rmult[i], p[i]), p[i]);
        x = (x < 0) ? (x + p[i]) : x;
        for(unsigned int j = i + 1; j < sz + 1; ++j){
            kp[j] = mod_add(kp[j], rmult[j] * x, p[j]);
            rmult[j] = mod_mul(rmult[j], p[i], p[j]);
        }
    }
    return kp[sz];
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;cin>>n;
    n++;
    vl F(n);rep(i,n)cin>>F[i];
    int m;cin>>m;
    m++;
    vl G(m);rep(i,m)cin>>G[i];
    vector<vector<ll>> ans(6,vector<ll>(n+m));
    rep(i,6){
        unsigned int p=prime_list[i];
        MOD=p;
        root=root_list[i];

        vector<int> Fp(n),Gp(m);
        rep(i,n)Fp[i]=F[i]%p;
        rep(i,m)Gp[i]=G[i]%p;
        auto Hp=convolute(Fp,Gp);
        rep(j,n+m)ans[i][j]=Hp[j];
    }
    vector<ll> res(n+m);
    vl M={924844033,998244353,1012924417,167772161,469762049,1224736769};
    ll deg=0;
    rep(i,n+m){
        vl r;
        rep(j,6){
            r.push_back(ans[j][i]);
        }
        res[i]=garner(r,M,ll(258280327));
        if(res[i]!=0)deg=i;
    }
    cout<<deg<<endl;
    rep(i,deg+1)cout<<res[i]<<" ";
    cout<<endl;
    return 0;
}
0