結果
問題 | No.1321 塗るめた |
ユーザー |
![]() |
提出日時 | 2024-11-12 02:18:35 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 305 ms / 2,000 ms |
コード長 | 4,490 bytes |
コンパイル時間 | 5,465 ms |
コンパイル使用メモリ | 276,504 KB |
実行使用メモリ | 17,656 KB |
最終ジャッジ日時 | 2024-11-12 02:18:51 |
合計ジャッジ時間 | 13,840 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 45 |
ソースコード
/**author: shobonvipcreated: 2024.11.12 01:47:20**/#include<bits/stdc++.h>using namespace std;//* ATCODER#include<atcoder/all>using namespace atcoder;typedef modint998244353 mint;//*//* BOOST MULTIPRECISION#include<boost/multiprecision/cpp_int.hpp>using namespace boost::multiprecision;//*/typedef long long ll;#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)#define all(v) v.begin(), v.end()template <typename T> bool chmin(T &a, const T &b) {if (a <= b) return false;a = b;return true;}template <typename T> bool chmax(T &a, const T &b) {if (a >= b) return false;a = b;return true;}template <typename T> T max(vector<T> &a){assert(!a.empty());T ret = a[0];for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);return ret;}template <typename T> T min(vector<T> &a){assert(!a.empty());T ret = a[0];for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);return ret;}template <typename T> T sum(vector<T> &a){T ret = 0;for (int i=0; i<(int)a.size(); i++) ret += a[i];return ret;}//defmodfactconst int COMinitMAX = 998244;mint fact[COMinitMAX+1], factinv[COMinitMAX+1];void modfact(){fact[0] = 1;for (int i=1; i<=COMinitMAX; i++){fact[i] = fact[i-1] * i;}factinv[COMinitMAX] = fact[COMinitMAX].inv();for (int i=COMinitMAX-1; i>=0; i--){factinv[i] = factinv[i+1] * (i+1);}}mint binom(int a, int b){if (a<b || b<0) return mint(0);return fact[a]*factinv[b]*factinv[a-b];}//--------// Inv of Polynomial// O(N log N)// T should be modinttemplate<typename T>std::vector<T> poly_inv(std::vector<T> &a, int M = -314159265){if (M == -314159265) M = (int)a.size();else if (M <= 0) return {};int n = a.size();T r = a[0].pow(T::mod()-2);int m = 1;std::vector<T> res = {r};while (m < M){std::vector<T> f = a;f.resize(std::min(n, 2*m));std::vector<T> h = atcoder::convolution(f, res);for (int i=0; i<std::min(2*m, (int)h.size()); i++){h[i] = -h[i];}h[0] += 2;h.resize(2*m);h = atcoder::convolution(h, res);h.resize(2*m);swap(res, h);m <<= 1;}res.resize(M);return res;}vector<mint> poly_log(vector<mint> &a, int M = -314159265){if (M == -314159265) M = (int)a.size();else if (M <= 0) return {};int n = a.size();if (n == 1) return vector<mint>(M, 0);vector<mint> b(n-1);for (int i=0; i<n-1; i++){b[i] = a[i+1] * (i+1);}vector<mint> t = convolution<mint>(b, poly_inv(a, M));vector<mint> ret(M);for (int i=0; i<M-1; i++){ret[i+1] = t[i] * factinv[i+1] * fact[i];}return ret;}vector<mint> poly_exp(vector<mint> &a, int M = -314159265){if (M == -314159265) M = (int)a.size();else if (M <= 0) return {};int n = a.size();int m = 1;vector<mint> res = {1};while (m < M){vector<mint> f(2*m);for (int i=0; i<min(n, 2*m); i++) f[i] = a[i];vector<mint> v = poly_log(res, 2*m);vector<mint> w(2*m);for (int i=0; i<2*m; i++) w[i] = f[i] - v[i];w[0] += 1;vector<mint> g = convolution<mint>(res, w);res.insert(res.end(), g.begin()+m, g.begin()+2*m);m <<= 1;}res.resize(M);return res;}vector<mint> poly_pow_nonzero(vector<mint> &a, ll m, ll l){int n = a.size();mint bais = a[0].pow(m);mint invs;if (a[0].val() == 0) invs = 0;else invs = a[0].inv();vector<mint> r(n);for (int i=0; i<n; i++) r[i] = a[i] * invs;r = poly_log(r, l);for (int i=0; i<l; i++) r[i] = r[i] * m;r = poly_exp(r, l);for (int i=0; i<l; i++) r[i] = r[i] * bais;return r;}vector<mint> poly_pow(vector<mint> &a, ll m, ll l){int n = a.size();int ind = 0;for (int i=0; i<n; i++){if (a[i].val() != 0){ind = i;break;}}ll g = min(m, (ll)3141592653);if (g*ind >= l){return vector<mint>(l, 0);}vector<mint> ret(g*ind);vector<mint> b(n-ind);for (int i=0; i<n-ind; i++) b[i] = a[i+ind];vector<mint> tmp;if (l-g*ind > 0) tmp = poly_pow_nonzero(b, m, l-g*ind);else tmp = {};ret.insert(ret.end(), tmp.begin(), tmp.end());return ret;}int main(){ios_base::sync_with_stdio(false);cin.tie(NULL);modfact();int n, m, k; cin >> n >> m >> k;vector<mint> f(n+1);rep(i,1,n+1){f[i] = (mint(2).pow(i) - 1) * factinv[i];}vector<mint> g = poly_pow(f, k, n+1);mint ans = 0;for (int l=k; l<=n; l++) {mint x = g[l];x *= binom(n, l);x *= fact[l];x *= mint(m-k).pow(n-l);ans += x;}ans *= binom(m, k);cout << ans.val() << '\n';}