Shift of Sampling Points of Polynomial (verify/poly/sampling.test.cpp)

View this file on GitHub
Last update: 2026-10-16 14:16:08+02:00
Problem: https://judge.yosupo.jp/problem/shift_of_sampling_points_of_polynomial

Depends on

Code

// @brief Shift of Sampling Points of Polynomial
#define PROBLEM "https://judge.yosupo.jp/problem/shift_of_sampling_points_of_polynomial"
#define CP_ALGO_MAXN 1 << 20
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include "blazingio/blazingio.min.hpp"
#include "cp-algo/math/combinatorics.hpp"
#include "cp-algo/math/poly/base.hpp"

using namespace std;
using namespace cp_algo::math;

const int mod = 998244353;
using base = modint<mod>;
using polyn = poly_t<base>;

void solve() {
    int n, m, c;
    cin >> n >> m >> c;
    polyn::Vector a(n);
    for(auto &it: a) {cin >> it;}

    // f(x) = prod_j(x-j) * sum_i (-1)^(n-1-i) f(i) / (i! (n-1-i)! (x-i)).
    // The sums for consecutive x are one convolution with coefficients 1/j of log(1/(1-x)).
    polyn::Vector weighted(n);
    for(int i = 0; i < n; i++) {
        base v = a[i] * rfact<base>(i) * rfact<base>(n - 1 - i);
        weighted[i] = (n - 1 - i) & 1 ? -v : v;
    }
    auto denominators = views::iota(c - n + 1, c + m) | views::transform([](int x) {
        return base(x) == base(0) ? base(1) : base(x);
    });
    auto log_segment = bulk_invs<base>(denominators);
    for(int z: {n - 1 - c, n - 1 - c + mod}) {
        if(0 <= z && z < ssize(log_segment)) {log_segment[z] = 0;}
    }
    // Only [n-1,n+m-1) is read; cyclic wrap reaches at most index n-2.
    auto shifted = log_segment;
    size_t length = std::max(fft::flen, std::bit_ceil(shifted.size()));
    shifted.resize(length);
    weighted.resize(length);
    fft::cyclic_mul(shifted, weighted, length);

    base product = ranges::fold_left(views::iota(0, n), base(1), [c](base p, int i) {return p * base(c - i);});
    for(int i = 0, x = c; i < m; i++, x = (x + 1) % mod) {
        cout << (x < n ? a[x] : shifted[n - 1 + i] * product) << ' ';
        base next = base(x) + 1;
        product = next == base(n) ? fact<base>(n) : product * next * log_segment[i];
    }
    cout << '\n';
}

signed main() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;// cin >> t;
    while(t--) {
        solve();
    }
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 290, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/languages/cplusplus.py", line 243, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/languages/cplusplus_bundle.py", line 373, in update
    assert len(lines) == len(uncommented_lines)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError

Test cases

Env	Name	Status	Elapsed	Memory
g++	N_1_00	AC	45 ms	37 MB
g++	c_0_00	AC	71 ms	67 MB
g++	example_00	AC	11 ms	14 MB
g++	example_01	AC	11 ms	14 MB
g++	max_random_00	AC	80 ms	69 MB
g++	max_random_01	AC	80 ms	69 MB
g++	max_random_02	AC	80 ms	69 MB
g++	max_random_03	AC	82 ms	69 MB
g++	medium_random_00	AC	13 ms	14 MB
g++	medium_random_01	AC	13 ms	14 MB
g++	medium_random_02	AC	13 ms	15 MB
g++	medium_random_03	AC	13 ms	14 MB
g++	small_random_00	AC	12 ms	14 MB
g++	small_random_01	AC	11 ms	14 MB
g++	small_random_02	AC	11 ms	14 MB
g++	small_random_03	AC	11 ms	14 MB
g++	type0_random_00	AC	43 ms	43 MB
g++	type0_random_01	AC	44 ms	45 MB
g++	type0_random_02	AC	17 ms	16 MB
g++	type0_random_03	AC	57 ms	66 MB
g++	type1_random_00	AC	75 ms	68 MB
g++	type1_random_01	AC	63 ms	67 MB
g++	type1_random_02	AC	19 ms	19 MB
g++	type1_random_03	AC	78 ms	69 MB
g++	type2_random_00	AC	72 ms	67 MB
g++	type2_random_01	AC	77 ms	69 MB
g++	type2_random_02	AC	45 ms	38 MB
g++	type2_random_03	AC	42 ms	44 MB
g++	type3_random_00	AC	69 ms	67 MB
g++	type3_random_01	AC	76 ms	69 MB
g++	type3_random_02	AC	47 ms	38 MB
g++	type3_random_03	AC	42 ms	44 MB