#496101 (C++17) No.1080 Strange Squared Score Sum

• 問題: No.1080 Strange Squared Score Sum
• ユーザー: noimi
• 提出日時: 2020-06-12 22:56:06
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 17,591 bytes
• コンパイル時間: 4,582 ms
• コンパイル使用メモリ: 239,084 KB
• 最終ジャッジ日時: 2025-01-11 02:52:51
• ジャッジサーバーID （参考情報）: judge3 / judge3

ファイルパターン	結果
sample	AC * 1 WA * 1
other	AC * 1 WA * 19

コンパイルメッセージ

main.cpp:618:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
  618 | main() {
      | ^~~~
main.cpp: In function ‘void scan(char*)’:
main.cpp:72:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   72 | void scan(char a[]) { scanf("%s", a); }
      |                       ~~~~~^~~~~~~~~

ソースコード

#pragma region Macros
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define rep2(i, a, b) for(ll i = a; i <= b; ++i)
#define rep(i, n) for(ll i = 0; i < n; ++i)
#define rep3(i, a, b) for(ll i = a; i >= b; --i)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vec vector<int>
#define vll vector<ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define overload2(_1, _2, name, ...) name
#define vv(a, b) vector<vector<int>>(a, vector<int>(b))
#define vv2(a, b, c) vector<vector<int>>(a, vector<int>(b, c))
#define vvl(a, b) vector<vector<ll>>(a, vector<ll>(b))
#define vvl2(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define vvv(a, b, c) vector<vv(b, c)>(a)
#define vvv2(a, b, c, d) vector<vv(b, c, d)>(a)
#define vvvl(a, b, c) vector<vvl(b, c)>(a)
#define vvvl2(a, b, c, d) vector<vvl(b, c, d)>(a)
#define fi first
#define se second
#define all(c) begin(c), end(c)
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
using namespace std;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define Size(c) (int)(c).size()
#define INT(...)     \
    int __VA_ARGS__; \
    IN(__VA_ARGS__)
#define LL(...)     \
    ll __VA_ARGS__; \
    IN(__VA_ARGS__)
#define ULL(...)     \
    ull __VA_ARGS__; \
    IN(__VA_ARGS__)
#define STR(...)        \
    string __VA_ARGS__; \
    IN(__VA_ARGS__)
#define CHR(...)      \
    char __VA_ARGS__; \
    IN(__VA_ARGS__)
#define DBL(...)        \
    double __VA_ARGS__; \
    IN(__VA_ARGS__)
#define LD(...)     \
    ld __VA_ARGS__; \
    IN(__VA_ARGS__)
#define VEC(type, name, size) \
    vector<type> name(size);  \
    IN(name)
#define VV(type, name, h, w)                       \
    vector<vector<type>> name(h, vector<type>(w)); \
    IN(name)
int scan() { return getchar(); }
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(long double &a) { cin >> a; }
void scan(char a[]) { scanf("%s", a); }
void scan(string &a) { cin >> a; }
template <class T>
void scan(vector<T> &);
template <class T, size_t size>
void scan(array<T, size> &);
template <class T, class L>
void scan(pair<T, L> &);
template <class T, size_t size>
void scan(T (&)[size]);
template <class T>
void scan(vector<T> &a) {
    for(auto &i : a) scan(i);
}
template <class T>
void scan(deque<T> &a) {
    for(auto &i : a) scan(i);
}
template <class T, size_t size>
void scan(array<T, size> &a) {
    for(auto &i : a) scan(i);
}
template <class T, class L>
void scan(pair<T, L> &p) {
    scan(p.first);
    scan(p.second);
}
template <class T, size_t size>
void scan(T (&a)[size]) {
    for(auto &i : a) scan(i);
}
template <class T>
void scan(T &a) {
    cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head &head, Tail &... tail) {
    scan(head);
    IN(tail...);
}
string stin() {
    string s;
    cin >> s;
    return s;
}
template <class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
vi iota(int n) {
    vi a(n);
    iota(all(a), 0);
    return a;
}
template <class T>
void UNIQUE(vector<T> &x) {
    sort(all(x));
    x.erase(unique(all(x)), x.end());
}
int in() {
    int x;
    cin >> x;
    return x;
}
ll lin() {
    unsigned long long x;
    cin >> x;
    return x;
}
void print() { putchar(' '); }
void print(bool a) { cout << a; }
void print(int a) { cout << a; }
void print(long long a) { cout << a; }
void print(char a) { cout << a; }
void print(string &a) { cout << a; }
void print(double a) { cout << a; }
template <class T>
void print(const vector<T> &);
template <class T, size_t size>
void print(const array<T, size> &);
template <class T, class L>
void print(const pair<T, L> &p);
template <class T, size_t size>
void print(const T (&)[size]);
template <class T>
void print(const vector<T> &a) {
    if(a.empty()) return;
    print(a[0]);
    for(auto i = a.begin(); ++i != a.end();) {
        cout << " ";
        print(*i);
    }
    cout << endl;
}
template <class T>
void print(const deque<T> &a) {
    if(a.empty()) return;
    print(a[0]);
    for(auto i = a.begin(); ++i != a.end();) {
        cout << " ";
        print(*i);
    }
}
template <class T, size_t size>
void print(const array<T, size> &a) {
    print(a[0]);
    for(auto i = a.begin(); ++i != a.end();) {
        cout << " ";
        print(*i);
    }
}
template <class T, class L>
void print(const pair<T, L> &p) {
    cout << '(';
    print(p.first);
    cout << ",";
    print(p.second);
    cout << ')';
}
template <class T>
void print(set<T> &x) {
    for(auto e : x) print(e), cout << " ";
    cout << endl;
}
template <class T>
void print(multiset<T> &x) {
    for(auto e : x) print(e), cout << " ";
    cout << endl;
}
template <class T, size_t size>
void print(const T (&a)[size]) {
    print(a[0]);
    for(auto i = a; ++i != end(a);) {
        cout << " ";
        print(*i);
    }
}
template <class T>
void print(const T &a) {
    cout << a;
}
int out() {
    putchar('\n');
    return 0;
}
template <class T>
int out(const T &t) {
    print(t);
    putchar('\n');
    return 0;
}
template <class Head, class... Tail>
int out(const Head &head, const Tail &... tail) {
    print(head);
    putchar(' ');
    out(tail...);
    return 0;
}
ll gcd(ll a, ll b) {
    while(b) {
        ll c = b;
        b = a % b;
        a = c;
    }
    return a;
}
ll lcm(ll a, ll b) {
    if(!a || !b) return 0;
    return a * b / gcd(a, b);
}
vector<pll> factor(ll x) {
    vector<pll> ans;
    for(ll i = 2; i * i <= x; i++)
        if(x % i == 0) {
            ans.push_back({i, 1});
            while((x /= i) % i == 0) ans.back().second++;
        }
    if(x != 1) ans.push_back({x, 1});
    return ans;
}
vector<int> divisor(int x) {
    vector<int> ans;
    for(int i = 1; i * i <= x; i++)
        if(x % i == 0) {
            ans.pb(i);
            if(i * i != x) ans.pb(x / i);
        }
    return ans;
}
int popcount(ll x) { return __builtin_popcountll(x); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int n) { return uniform_int_distribution<int>(0, n - 1)(rng); }
#define endl '\n'

#ifdef _LOCAL
#undef endl
#define debug(x)        \
    cout << #x << ": "; \
    print(x);           \
    cout << endl;
void err() {}
template <class T>
void err(const T &t) {
    print(t);
    cout << " ";
}
template <class Head, class... Tail>
void err(const Head &head, const Tail &... tail) {
    print(head);
    putchar(' ');
    out(tail...);
}
#else
#define debug(x)
template <class... T>
void err(const T &...) {}
#endif

struct Setup_io {
    Setup_io() {
        ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cout << fixed << setprecision(15);
    }
} setup_io;
#pragma endregion

// _______ここから編集！_______________

// exp of poly from https://judge.yosupo.jp/submission/2613
template <class T>
vector<T> operator-(vector<T> a) {
    for(auto &&e : a) e = -e;
    return a;
}
template <class T>
vector<T> &operator+=(vector<T> &l, const vector<T> &r) {
    l.resize(max(l.size(), r.size()));
    for(int i = 0; i < (int)r.size(); ++i) l[i] += r[i];
    return l;
}
template <class T>
vector<T> operator+(vector<T> l, const vector<T> &r) {
    return l += r;
}
template <class T>
vector<T> &operator-=(vector<T> &l, const vector<T> &r) {
    l.resize(max(l.size(), r.size()));
    for(int i = 0; i < (int)r.size(); ++i) l[i] -= r[i];
    return l;
}
template <class T>
vector<T> operator-(vector<T> l, const vector<T> &r) {
    return l -= r;
}
template <class T>
vector<T> &operator<<=(vector<T> &a, size_t n) {
    return a.insert(begin(a), n, 0), a;
}
template <class T>
vector<T> operator<<(vector<T> a, size_t n) {
    return a <<= n;
}
template <class T>
vector<T> &operator>>=(vector<T> &a, size_t n) {
    return a.erase(begin(a), begin(a) + min(a.size(), n)), a;
}
template <class T>
vector<T> operator>>(vector<T> a, size_t n) {
    return a >>= n;
}
template <class T>
vector<T> operator*(const vector<T> &l, const vector<T> &r) {
    if(l.empty() or r.empty()) return {};
    vector<T> res(l.size() + r.size() - 1);
    for(int i = 0; i < (int)l.size(); ++i)
        for(int j = 0; j < (int)r.size(); ++j) res[i + j] += l[i] * r[j];
    return res;
}
template <class T>
vector<T> &operator*=(vector<T> &l, const vector<T> &r) {
    return l = l * r;
}
template <class T>
vector<T> inverse(const vector<T> &a) {
    assert(not a.empty() and not(a[0] == 0));
    vector<T> b{1 / a[0]};
    while(b.size() < a.size()) {
        vector<T> x(begin(a), begin(a) + min(a.size(), 2 * b.size()));
        x *= b * b;
        b.resize(2 * b.size());
        for(auto i = b.size() / 2; i < min(x.size(), b.size()); ++i)
            b[i] = -x[i];
    }
    return {begin(b), begin(b) + a.size()};
}
template <class T>
vector<T> operator/(vector<T> l, vector<T> r) {
    if(l.size() < r.size()) return {};
    reverse(begin(l), end(l)), reverse(begin(r), end(r));
    int n = l.size() - r.size() + 1;
    l.resize(n), r.resize(n);
    l *= inverse(r);
    return {rend(l) - n, rend(l)};
}
template <class T>
vector<T> &operator/=(vector<T> &l, const vector<T> &r) {
    return l = l / r;
}
template <class T>
vector<T> operator%(vector<T> l, const vector<T> &r) {
    if(l.size() < r.size()) return l;
    l -= l / r * r;
    return {begin(l), begin(l) + (r.size() - 1)};
}
template <class T>
vector<T> &operator%=(vector<T> &l, const vector<T> &r) {
    return l = l % r;
}
template <class T>
vector<T> derivative(const vector<T> &a) {
    vector<T> res(max((int)a.size() - 1, 0));
    for(int i = 0; i < (int)res.size(); ++i) res[i] = (i + 1) * a[i + 1];
    return res;
}
template <class T>
vector<T> primitive(const vector<T> &a) {
    vector<T> res(a.size() + 1);
    for(int i = 1; i < (int)res.size(); ++i) res[i] = a[i - 1] / i;
    return res;
}
template <class T>
vector<T> logarithm(const vector<T> &a) {
    assert(not a.empty() and a[0] == 1);
    auto res = primitive(derivative(a) * inverse(a));
    return {begin(res), begin(res) + a.size()};
}
template <class T>
vector<T> exponent(const vector<T> &a) {
    assert(a.empty() or a[0] == 0);
    vector<T> b{1};
    while(b.size() < a.size()) {
        vector<T> x(begin(a), begin(a) + min(a.size(), 2 * b.size()));
        x[0] += 1;
        b.resize(2 * b.size());
        x -= logarithm(b);
        x *= {begin(b), begin(b) + b.size() / 2};
        for(auto i = b.size() / 2; i < min(x.size(), b.size()); ++i)
            b[i] = x[i];
    }
    return {begin(b), begin(b) + a.size()};
}

template <class T, class F = multiplies<T>>
T power(T a, long long n, F op = multiplies<T>(), T e = {1}) {
    assert(n >= 0);
    T res = e;
    while(n) {
        if(n & 1) res = op(res, a);
        if(n >>= 1) a = op(a, a);
    }
    return res;
}

template <unsigned Mod>
struct Modular {
    using M = Modular;
    unsigned v;
    Modular(long long a = 0) : v((a %= Mod) < 0 ? a + Mod : a) {}
    M operator-() const { return M() -= *this; }
    M &operator+=(M r) {
        if((v += r.v) >= Mod) v -= Mod;
        return *this;
    }
    M &operator-=(M r) {
        if((v += Mod - r.v) >= Mod) v -= Mod;
        return *this;
    }
    M &operator*=(M r) {
        v = (uint64_t)v * r.v % Mod;
        return *this;
    }
    M &operator/=(M r) { return *this *= power(r, Mod - 2); }
    friend M operator+(M l, M r) { return l += r; }
    friend M operator-(M l, M r) { return l -= r; }
    friend M operator*(M l, M r) { return l *= r; }
    friend M operator/(M l, M r) { return l /= r; }
    friend bool operator==(M l, M r) { return l.v == r.v; }
};

template <unsigned Mod>
void ntt(vector<Modular<Mod>> &a, bool inverse) {
    static vector<Modular<Mod>> dt(30), idt(30);
    if(dt[0] == 0) {
        Modular<Mod> root = 2;
        while(power(root, (Mod - 1) / 2) == 1) root += 1;
        for(int i = 0; i < 30; ++i)
            dt[i] = -power(root, (Mod - 1) >> (i + 2)), idt[i] = 1 / dt[i];
    }
    int n = a.size();
    assert((n & (n - 1)) == 0);
    if(not inverse) {
        for(int w = n; w >>= 1;) {
            Modular<Mod> t = 1;
            for(int s = 0, k = 0; s < n; s += 2 * w) {
                for(int i = s, j = s + w; i < s + w; ++i, ++j) {
                    auto x = a[i], y = a[j] * t;
                    if(x.v >= Mod) x.v -= Mod;
                    a[i].v = x.v + y.v, a[j].v = x.v + (Mod - y.v);
                }
                t *= dt[__builtin_ctz(++k)];
            }
        }
    } else {
        for(int w = 1; w < n; w *= 2) {
            Modular<Mod> t = 1;
            for(int s = 0, k = 0; s < n; s += 2 * w) {
                for(int i = s, j = s + w; i < s + w; ++i, ++j) {
                    auto x = a[i], y = a[j];
                    a[i] = x + y, a[j].v = x.v + (Mod - y.v), a[j] *= t;
                }
                t *= idt[__builtin_ctz(++k)];
            }
        }
    }
    auto c = 1 / Modular<Mod>(inverse ? n : 1);
    for(auto &&e : a) e *= c;
}
template <unsigned Mod>
vector<Modular<Mod>> operator*(vector<Modular<Mod>> l, vector<Modular<Mod>> r) {
    if(l.empty() or r.empty()) return {};
    int n = l.size(), m = r.size(), sz = 1 << __lg(2 * (n + m - 1) - 1);
    if(min(n, m) < 30) {
        vector<long long> res(n + m - 1);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j) res[i + j] += (l[i] * r[j]).v;
        return {begin(res), end(res)};
    }
    bool eq = l == r;
    l.resize(sz), ntt(l, false);
    if(eq)
        r = l;
    else
        r.resize(sz), ntt(r, false);
    for(int i = 0; i < sz; ++i) l[i] *= r[i];
    ntt(l, true), l.resize(n + m - 1);
    return l;
}

template <unsigned Mod>
vector<Modular<Mod>> inverse(const vector<Modular<Mod>> &a) {
    assert(not a.empty() and not(a[0] == 0));
    vector<Modular<Mod>> b{1 / a[0]};
    for(int m = 1; m < (int)a.size(); m *= 2) {
        vector<Modular<Mod>> x(begin(a), begin(a) + min<int>(a.size(), 2 * m));
        auto y = b;
        x.resize(2 * m), ntt(x, false);
        y.resize(2 * m), ntt(y, false);
        for(int i = 0; i < 2 * m; ++i) x[i] *= y[i];
        ntt(x, true);
        fill(begin(x), begin(x) + m, 0);
        ntt(x, false);
        for(int i = 0; i < 2 * m; ++i) x[i] *= -y[i];
        ntt(x, true);
        b.insert(end(b), begin(x) + m, end(x));
    }
    return {begin(b), begin(b) + a.size()};
}
template <unsigned Mod>
vector<Modular<Mod>> exponent(const vector<Modular<Mod>> &a) {
    assert(a.empty() or a[0] == 0);
    vector<Modular<Mod>> b{1, 1 < a.size() ? a[1] : 0}, c{1}, z1, z2{1, 1};
    for(int m = 2; m < (int)a.size(); m *= 2) {
        auto y = b;
        y.resize(2 * m), ntt(y, false);
        z1 = z2;
        vector<Modular<Mod>> z(m);
        for(int i = 0; i < m; ++i) z[i] = y[i] * z1[i];
        ntt(z, true);
        fill(begin(z), begin(z) + m / 2, 0);
        ntt(z, false);
        for(int i = 0; i < m; ++i) z[i] *= -z1[i];
        ntt(z, true);
        c.insert(end(c), begin(z) + m / 2, end(z));
        z2 = c, z2.resize(2 * m), ntt(z2, false);
        vector<Modular<Mod>> x(begin(a), begin(a) + min<int>(a.size(), m));
        x = derivative(x), x.push_back(0), ntt(x, false);
        for(int i = 0; i < m; ++i) x[i] *= y[i];
        ntt(x, true);
        x -= derivative(b);
        x.resize(2 * m);
        for(int i = 0; i < m - 1; ++i) x[m + i] = x[i], x[i] = 0;
        ntt(x, false);
        for(int i = 0; i < 2 * m; ++i) x[i] *= z2[i];
        ntt(x, true);
        x = primitive(x), x.pop_back();
        for(int i = m; i < min<int>(a.size(), 2 * m); ++i) x[i] += a[i];
        fill(begin(x), begin(x) + m, 0);
        ntt(x, false);
        for(int i = 0; i < 2 * m; ++i) x[i] *= y[i];
        ntt(x, true);
        b.insert(end(b), begin(x) + m, end(x));
    }
    return {begin(b), begin(b) + a.size()};
}

constexpr long long mod = 1e9 + 9;
using Mint = Modular<mod>;

vector<Mint> fact, inv_fact, minv;
void prepare(int n) {
    fact.resize(n + 1), inv_fact.resize(n + 1), minv.resize(n + 1);
    for(int i = 0; i <= n; ++i) fact[i] = i ? i * fact[i - 1] : 1;
    inv_fact[n] = 1 / fact[n];
    for(int i = n; i; --i) inv_fact[i - 1] = i * inv_fact[i];
    for(int i = 1; i <= n; ++i) minv[i] = inv_fact[i] * fact[i - 1];
}
Mint binom(int n, int k) {
    if(k < 0 or k > n) return 0;
    return fact[n] * inv_fact[k] * inv_fact[n - k];
}
template <>
Mint &Mint::operator/=(Mint r) {
    return *this *= r.v < minv.size() ? minv[r.v] : power(r, mod - 2);
}
ll modpow(ll x, ll n, ll mod) {
    ll res = 1;
    while(n) {
        if(n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
main() {
    INT(n);
    ll a = 430477711, b = 569522298;
    vector<Mint> f1(n + 1), f2(n + 1);
    rep2(i, 1, n) f1[i] = (i + 1) * (i + 1) % mod * a;
    rep2(i, 1, n) f2[i] = (i + 1) * (i + 1) % mod * b;
    prepare(2 * (n + 1));
    f1 = exponent(f1);
    f2 = exponent(f2);
    ll p = 1;
    rep2(i, 1, n) p = p * i % mod;
    rep2(i, 1, n) f1[i] *= p, f2[i] *= p;
    Mint I = modpow(b - a, mod - 2, mod);
    rep2(i, 1, n) {
        Mint c = (f2[i] - f1[i]) * I;
        cout << (c.v + (f1[i] - c * a).v) % mod << endl;
    }
}