提出 #65514178

---

ソースコード 拡げる

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <vector>

using namespace std;

#define all(a) begin(a), end(a)
using ll = long long;

constexpr int MOD = 998244353;
using P = pair<int, int>;

const int INF = 1e9;

#include <atcoder/modint.hpp>
using mint = atcoder::modint998244353;

int gauss(vector<vector<mint>> a, vector<mint> &ans) {
    int n = (int)a.size();
    int m = (int)a[0].size() - 1;

    vector<int> where(m, -1);
    for (int col = 0, row = 0; col < m && row < n; ++col) {
        int sel = row;
        for (int i = row; i < n; ++i)
            if (a[i][col] != 0) {
                sel = i;
                break;
            }

        if (a[sel][col] == 0) {
            cerr << "No for " << col << "\n";
            return 0;
        }
        for (int i = col; i <= m; ++i)
            swap(a[sel][i], a[row][i]);
        where[col] = row;

        for (int i = 0; i < n; ++i)
            if (i != row) {
                mint c = a[i][col] / a[row][col];
                for (int j = col; j <= m; ++j)
                    a[i][j] -= a[row][j] * c;
            }
        ++row;
    }

    ans.assign(m, 0);
    for (int i = 0; i < m; ++i)
        if (where[i] != -1)
            ans[i] = a[where[i]][m] / a[where[i]][i];
    for (int i = 0; i < n; ++i) {
        mint sum = 0;
        for (int j = 0; j < m; ++j)
            sum += ans[j] * a[i][j];
        if (sum != a[i][m]) {
            cerr << "fail: " << i << "\n";
            return 0;
        }
    }

    for (int i = 0; i < m; ++i)
        if (where[i] == -1)
            return INF;
    return 1;
}

ll brute(ll n, ll h, ll w) {
    if (h < 2 * n || w < 2 * n) {
        cerr << "NO\n";
        return 0;
    }

    auto check = [&](pair<int, int> p1, pair<int, int> p2) {
        return abs(p1.first - p2.first) >= n || abs(p1.second - p2.second) >= n;
    };

    vector<P> ava;
    for (int i = 0; i + n <= h; i++)
        for (int j = 0; j + n <= w; j++)
            ava.push_back({i, j});

    int res = 0;
    int sz = ava.size();
    for (int i = 0; i < sz; i++) {
        auto p1 = ava[i];
        for (int j = i + 1; j < sz; j++) {
            auto p2 = ava[j];
            if (!check(p1, p2))
                continue;

            for (int k = j + 1; k < sz; k++) {
                auto p3 = ava[k];
                if (!check(p1, p3) || !check(p2, p3))
                    continue;

                for (int t = k + 1; t < sz; t++) {
                    auto p4 = ava[t];
                    if (!check(p1, p4) || !check(p2, p4) || !check(p3, p4))
                        continue;

                    res += 1;
                }
            }
        }
    }
    return res;
}

vector<mint> gen_coef(mint n, mint h, mint w) {
    vector<mint> res;
    constexpr int DEG = 10;
    for (int i = 0; i <= DEG; i++)
        for (int j = 0; j <= DEG; j++)
            for (int k = 0; k <= DEG; k++)
                res.push_back(n.pow(i) * h.pow(j) * w.pow(k));
    return res;
}

vector<mint> coefs;
vector<tuple<int, int, int, mint>> coefs_opt{
    {0, 0, 0, 1},         {0, 0, 1, 3},         {0, 0, 2, 748683268}, {0, 0, 3, 499122178}, {0, 0, 4, 748683265},
    {0, 1, 0, 3},         {0, 1, 1, 124780553}, {0, 1, 2, 145577311}, {0, 1, 3, 623902725}, {0, 1, 4, 603105964},
    {0, 2, 0, 748683268}, {0, 2, 1, 145577311}, {0, 2, 2, 412469031}, {0, 2, 3, 20796762},  {0, 2, 4, 3466127},
    {0, 3, 0, 499122178}, {0, 3, 1, 623902725}, {0, 3, 2, 20796762},  {0, 3, 3, 873463811}, {0, 3, 4, 977447596},
    {0, 4, 0, 748683265}, {0, 4, 1, 603105964}, {0, 4, 2, 3466127},   {0, 4, 3, 977447596}, {0, 4, 4, 828404168},
    {1, 0, 0, 998244341}, {1, 0, 1, 748683234}, {1, 0, 2, 707089722}, {1, 0, 3, 748683254}, {1, 0, 4, 790276778},
    {1, 1, 0, 748683234}, {1, 1, 1, 831870218}, {1, 1, 2, 596173644}, {1, 1, 3, 83187005},  {1, 1, 4, 984379845},
    {1, 2, 0, 707089722}, {1, 2, 1, 596173644}, {1, 2, 2, 748683209}, {1, 2, 3, 720954236}, {1, 2, 4, 124780542},
    {1, 3, 0, 748683254}, {1, 3, 1, 83187005},  {1, 3, 2, 720954236}, {1, 3, 3, 332748112}, {1, 3, 4, 360477127},
    {1, 4, 0, 790276778}, {1, 4, 1, 984379845}, {1, 4, 2, 124780542}, {1, 4, 3, 360477127}, {2, 0, 0, 499122238},
    {2, 0, 1, 748683397}, {2, 0, 2, 152509653}, {2, 0, 3, 748683295}, {2, 0, 4, 13864508},  {2, 1, 0, 748683397},
    {2, 1, 1, 610038483}, {2, 1, 2, 249561273}, {2, 1, 3, 610038266}, {2, 1, 4, 748683269}, {2, 2, 0, 152509653},
    {2, 2, 1, 249561273}, {2, 2, 2, 665496349}, {2, 2, 3, 499122202}, {2, 2, 4, 915057325}, {2, 3, 0, 748683295},
    {2, 3, 1, 610038266}, {2, 3, 2, 499122202}, {2, 3, 3, 110916043}, {2, 4, 0, 13864508},  {2, 4, 1, 748683269},
    {2, 4, 2, 915057325}, {3, 0, 0, 665496059}, {3, 0, 1, 388205827}, {3, 0, 2, 332747934}, {3, 0, 3, 887328272},
    {3, 0, 4, 166374056}, {3, 1, 0, 388205827}, {3, 1, 1, 332747625}, {3, 1, 2, 554579944}, {3, 1, 3, 665496190},
    {3, 1, 4, 443664155}, {3, 2, 0, 332747934}, {3, 2, 1, 554579944}, {3, 2, 2, 998244251}, {3, 2, 3, 665496224},
    {3, 3, 0, 887328272}, {3, 3, 1, 665496190}, {3, 3, 2, 665496224}, {3, 4, 0, 166374056}, {3, 4, 1, 443664155},
    {4, 0, 0, 610038526}, {4, 0, 1, 430},       {4, 0, 2, 388206326}, {4, 0, 3, 332748146}, {4, 0, 4, 277290099},
    {4, 1, 0, 430},       {4, 1, 1, 887328818}, {4, 1, 2, 170},       {4, 1, 3, 443664172}, {4, 2, 0, 388206326},
    {4, 2, 1, 170},       {4, 2, 2, 34},        {4, 3, 0, 332748146}, {4, 3, 1, 443664172}, {4, 4, 0, 277290099},
    {5, 0, 0, 998244009}, {5, 0, 1, 332747765}, {5, 0, 2, 998244251}, {5, 0, 3, 776412267}, {5, 1, 0, 332747765},
    {5, 1, 1, 998244081}, {5, 1, 2, 665496190}, {5, 2, 0, 998244251}, {5, 2, 1, 665496190}, {5, 3, 0, 776412267},
    {6, 0, 0, 443664392}, {6, 0, 1, 665496394}, {6, 0, 2, 665496258}, {6, 1, 0, 665496394}, {6, 1, 1, 776412335},
    {6, 2, 0, 665496258}, {7, 0, 0, 332748027}, {7, 0, 1, 110916009}, {7, 1, 0, 110916009}, {8, 0, 0, 443664172},
};

void init() {
    vector<array<mint, 4>> data;
    for (int n = 1; n <= 19; n++)
        for (int h = 2 * n; h <= min(2 * n + 12, 3 * n - 1); h++)
            for (int w = 2 * n; w <= min(2 * n + 12, 3 * n - 1); w++)
                data.push_back({n, h, w, brute(n, h, w)});

    vector<vector<mint>> mat;
    for (auto [n, h, w, res] : data) {
        // cerr << n.val() << " " << h.val() << " " << w.val() << " " << res.val() << "\n";
        mat.push_back(gen_coef(n, h, w));
        mat.back().push_back(res);
    }

    cerr << "gauss: " << gauss(mat, coefs) << endl;

    constexpr int DEG = 10;
    int ind = 0;

    cerr << "{";
    for (int i = 0; i <= DEG; i++)
        for (int j = 0; j <= DEG; j++)
            for (int k = 0; k <= DEG; k++, ind++) {
                if (coefs[ind] != 0) {
                    cerr << "    {" << i << ", " << j << ", " << k << ", " << coefs[ind].val() << "},\n";
                }
            }
    cerr << "}";
}

void solve() {
    ll n_, h_, w_;
    cin >> n_ >> h_ >> w_;

    mint n{n_}, h{h_}, w{w_};

    if (h_ < 2 * n_ || w_ < 2 * n_) {
        cout << "0\n";
        return;
    }

    mint res = 0;
    for (auto [i, j, k, coef] : coefs_opt) {
        res += coef * n.pow(i) * h.pow(j) * w.pow(k);
    }
    cout << res.val() << "\n";
}

int main() {
    // init();

    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int tests = 1;
    cin >> tests;

    while (tests--)
        solve();
}

提出情報

コンパイルエラー

./Main.cpp:17:15: warning: unused variable 'MOD' [-Wunused-const-variable]
constexpr int MOD = 998244353;
              ^
1 warning generated.

ジャッジ結果