Test/My/FPS/PowerProjection.test.cpp

• View this file on GitHub
• Last update: 2026-01-12 16:27:35+09:00
• Problem: https://judge.yosupo.jp/problem/aplusb

Depends on

• Src/FPS/FPS.hpp
• Src/FPS/FPSNTTFriendly.hpp
• FPS Power Projection (Src/FPS/PowerProjection.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include "../../../Src/FPS/FPSNTTFriendly.hpp"
#include "../../../Src/FPS/PowerProjection.hpp"
#include "atcoder/modint"
using namespace zawa;
using mint = atcoder::modint998244353;
using fps = FPSNTTFriendly<mint::mod()>;

#include <iostream>
#include <random>
using namespace std;
mt19937 mt{random_device{}()};
vector<mint> naive(int M, const fps& W, const fps& F) {
    vector<mint> res(M);
    fps cur{1};
    for (int i = 0 ; i < M ; i++) {
        cur.resize(W.size());
        for (int j = 0 ; j < ssize(W) ; j++)
            res[i] += W[j] * cur[j];
        cur *= F;
    }
    return res;
}
void test(int MAXN, int MAXM, int MAXVAL, bool verify = true) {
    int N = mt() % MAXN + 1;
    int M = mt() % MAXM + 1;
    fps W(N), F(mt() % MAXN + 1);
    for (int i = 0 ; i < N ; i++)
        W[i] = mt() % MAXVAL;
    for (int i = 0 ; i < ssize(F) ; i++)
        F[i] = mt() % MAXVAL;
    auto ans = PowerProjection(M, W, F);
    if (verify) {
        auto nv = naive(M, W, F);
        if (ans != nv) {
            cerr << "fail" << endl;
            cerr << "W -> " << W << endl;
            cerr << "F -> " << F << endl;
            cerr << "ans: ";
            for (auto i : nv)
                cerr << i.val() << ' ';
            cerr << endl;
            cerr << "you: ";
            for (auto i : ans)
                cerr << i.val() << ' ';
            cerr << endl;
            exit(0);
        }
    }
}
void test2(int N, int M, int MAXVAL) {
    fps W(N), F(N);
    for (int i = 0 ; i < N ; i++) {
        W[i] = mt() % MAXVAL;
        F[i] = mt() % MAXVAL;
    }
    auto ans = PowerProjection(M, W, F);
    std::cerr << ans.size() << "fin" << std::endl;
}
int main() {
    for (int i = (1 << 15) ; i-- ; )
        test(4, 10, 10);
    cerr << "tiny end" << endl;
    for (int i = (1 << 10) ; i-- ; )
        test(50, 50, mint::mod());
    cerr << "small end" << endl;
    for (int i = 0 ; i < (1 << 3) ; i++)
        test(3000, 1000, mint::mod());
    cerr << "med end" << endl;
    test2(250000, 250000, mint::mod());
    cerr << "large end" << endl;
    int A, B;
    cin >> A >> B;
    cout << A + B << '\n';
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.13/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/modint: line -1: no such header

Back to top page