結果
問題 | No.2944 Sigma Partition Problem |
ユーザー |
|
提出日時 | 2024-10-18 23:32:01 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 8,117 bytes |
コンパイル時間 | 8,568 ms |
コンパイル使用メモリ | 337,704 KB |
実行使用メモリ | 13,640 KB |
最終ジャッジ日時 | 2024-10-18 23:36:17 |
合計ジャッジ時間 | 49,851 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 TLE * 2 -- * 1 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; }ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); }istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; }ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; }ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); }typedef long long ll;typedef vector<vector<int>> Graph;typedef pair<int, int> pii;typedef pair<ll, ll> pll;#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)#define rep(i,n) for (int i = 0;i < (int)(n); i++)#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define my_sort(x) sort(x.begin(), x.end())#define my_max(x) *max_element(all(x))#define my_min(x) *min_element(all(x))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; }const int INF = (1<<30) - 1;const ll LINF = (1LL<<62) - 1;const int MOD = 998244353;const int MOD2 = 1e9+7;const double PI = acos(-1);vector<int> di = {1,0,-1,0};vector<int> dj = {0,1,0,-1};#ifdef LOCAL# include <debug_print.hpp># define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)#else# define debug(...) (static_cast<void>(0))#endif//形式的冪級数//https://qiita.com/gg_hatano/items/3591ddf267092c235a23#define rep2(i, m, n) for (int i = (m); i < (n); ++i)#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)#define drep(i, n) drep2(i, n, 0)template<class T>struct FormalPowerSeries : vector<T> {using vector<T>::vector;using vector<T>::operator=;using F = FormalPowerSeries;F operator-() const {F res(*this);for (auto &e : res) e = -e;return res;}F &operator*=(const T &g) {for (auto &e : *this) e *= g;return *this;}F &operator/=(const T &g) {assert(g != T(0));*this *= g.inv();return *this;}F &operator+=(const F &g) {int n = (*this).size(), m = g.size();rep(i, min(n, m)) (*this)[i] += g[i];return *this;}F &operator-=(const F &g) {int n = (*this).size(), m = g.size();rep(i, min(n, m)) (*this)[i] -= g[i];return *this;}F &operator<<=(const int d) {int n = (*this).size();(*this).insert((*this).begin(), d, 0);(*this).resize(n);return *this;}F &operator>>=(const int d) {int n = (*this).size();(*this).erase((*this).begin(), (*this).begin() + min(n, d));(*this).resize(n);return *this;}F inv(int d = -1) const {int n = (*this).size();assert(n != 0 && (*this)[0] != 0);if (d == -1) d = n;assert(d > 0);F res{(*this)[0].inv()};while (res.size() < d) {int m = size(res);F f(begin(*this), begin(*this) + min(n, 2*m));F r(res);f.resize(2*m), internal::butterfly(f);r.resize(2*m), internal::butterfly(r);rep(i, 2*m) f[i] *= r[i];internal::butterfly_inv(f);f.erase(f.begin(), f.begin() + m);f.resize(2*m), internal::butterfly(f);rep(i, 2*m) f[i] *= r[i];internal::butterfly_inv(f);T iz = T(2*m).inv(); iz *= -iz;rep(i, m) f[i] *= iz;res.insert(res.end(), f.begin(), f.begin() + m);}return {res.begin(), res.begin() + d};}// fast: FMT-friendly modulus onlyF &operator*=(const F &g) {int n = (*this).size();*this = convolution(*this, g);(*this).resize(n);return *this;}F &operator/=(const F &g) {int n = (*this).size();*this = convolution(*this, g.inv(n));(*this).resize(n);return *this;}// // naive// F &operator*=(const F &g) {// int n = (*this).size(), m = g.size();// drep(i, n) {// (*this)[i] *= g[0];// rep2(j, 1, min(i+1, m)) (*this)[i] += (*this)[i-j] * g[j];// }// return *this;// }// F &operator/=(const F &g) {// assert(g[0] != T(0));// T ig0 = g[0].inv();// int n = (*this).size(), m = g.size();// rep(i, n) {// rep2(j, 1, min(i+1, m)) (*this)[i] -= (*this)[i-j] * g[j];// (*this)[i] *= ig0;// }// return *this;// }// sparseF &operator*=(vector<pair<int, T>> g) {int n = (*this).size();auto [d, c] = g.front();if (d == 0) g.erase(g.begin());else c = 0;drep(i, n) {(*this)[i] *= c;for (auto &[j, b] : g) {if (j > i) break;(*this)[i] += (*this)[i-j] * b;}}return *this;}F &operator/=(vector<pair<int, T>> g) {int n = (*this).size();auto [d, c] = g.front();assert(d == 0 && c != T(0));T ic = c.inv();g.erase(g.begin());rep(i, n) {for (auto &[j, b] : g) {if (j > i) break;(*this)[i] -= (*this)[i-j] * b;}(*this)[i] *= ic;}return *this;}// multiply and divide (1 + cz^d)void multiply(const int d, const T c) {int n = (*this).size();if (c == T(1)) drep(i, n-d) (*this)[i+d] += (*this)[i];else if (c == T(-1)) drep(i, n-d) (*this)[i+d] -= (*this)[i];else drep(i, n-d) (*this)[i+d] += (*this)[i] * c;}void divide(const int d, const T c) {int n = (*this).size();if (c == T(1)) rep(i, n-d) (*this)[i+d] -= (*this)[i];else if (c == T(-1)) rep(i, n-d) (*this)[i+d] += (*this)[i];else rep(i, n-d) (*this)[i+d] -= (*this)[i] * c;}T eval(const T &a) const {T x(1), res(0);for (auto e : *this) res += e * x, x *= a;return res;}F operator*(const T &g) const { return F(*this) *= g; }F operator/(const T &g) const { return F(*this) /= g; }F operator+(const F &g) const { return F(*this) += g; }F operator-(const F &g) const { return F(*this) -= g; }F operator<<(const int d) const { return F(*this) <<= d; }F operator>>(const int d) const { return F(*this) >>= d; }F operator*(const F &g) const { return F(*this) *= g; }F operator/(const F &g) const { return F(*this) /= g; }F operator*(vector<pair<int, T>> g) const { return F(*this) *= g; }F operator/(vector<pair<int, T>> g) const { return F(*this) /= g; }};using mint = modint998244353;using fps = FormalPowerSeries<mint>;using sfps = vector<pair<int, mint>>; // (次数,係数)int main(){cin.tie(0);ios_base::sync_with_stdio(false);int Q; cin >> Q;while(Q--){int flg, N, K; cin >> flg >> N >> K;if(flg == 1 || flg == 2){mint ans = 0;fps f(N + 1);f[0] = 1;FOR(j, 1, K + 1){int m = N / j;sfps g10 = {{j, 1}, {(m + 1) * j, -1}};sfps g11 = {{0, 1}, {j, -1}};fps h = f;h *= g10;h /= g11;ans += h[N];sfps g00 = {{0, 1}, {(m + 1) * j, -1}};sfps g01 = {{0, 1}, {j, -1}};f *= g00;f /= g01;}cout << ans << endl;}else{mint ans = 0;fps f(N + 1);FOR(i, 1, N + 1) f[i] = 1;sfps g = {{0, 1}, {1, -1}};rep(i, K - 1){ans += f[N];f /= g;}cout << -1 << endl;}}}