結果
| 問題 | No.1621 Sequence Inversions |
| ユーザー |
 yuto1115
|
| 提出日時 | 2021-07-11 13:19:25 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 206 ms / 3,000 ms |
| コード長 | 15,987 bytes |
| コンパイル時間 | 2,815 ms |
| コンパイル使用メモリ | 230,204 KB |
| 実行使用メモリ | 12,544 KB |
| 最終ジャッジ日時 | 2024-07-17 15:53:49 |
| 合計ジャッジ時間 | 5,211 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,376 KB |
| testcase_02 | AC | 2 ms
5,376 KB |
| testcase_03 | AC | 4 ms
5,376 KB |
| testcase_04 | AC | 44 ms
6,400 KB |
| testcase_05 | AC | 2 ms
5,376 KB |
| testcase_06 | AC | 2 ms
5,376 KB |
| testcase_07 | AC | 4 ms
5,376 KB |
| testcase_08 | AC | 50 ms
6,528 KB |
| testcase_09 | AC | 65 ms
7,424 KB |
| testcase_10 | AC | 129 ms
11,608 KB |
| testcase_11 | AC | 56 ms
6,784 KB |
| testcase_12 | AC | 141 ms
11,708 KB |
| testcase_13 | AC | 160 ms
12,124 KB |
| testcase_14 | AC | 28 ms
5,376 KB |
| testcase_15 | AC | 23 ms
5,376 KB |
| testcase_16 | AC | 80 ms
6,912 KB |
| testcase_17 | AC | 163 ms
9,984 KB |
| testcase_18 | AC | 74 ms
6,784 KB |
| testcase_19 | AC | 3 ms
5,376 KB |
| testcase_20 | AC | 42 ms
5,504 KB |
| testcase_21 | AC | 183 ms
10,752 KB |
| testcase_22 | AC | 42 ms
5,376 KB |
| testcase_23 | AC | 206 ms
12,544 KB |
| testcase_24 | AC | 2 ms
5,376 KB |
| testcase_25 | AC | 2 ms
5,376 KB |
| testcase_26 | AC | 2 ms
5,376 KB |
| testcase_27 | AC | 2 ms
5,376 KB |
| testcase_28 | AC | 2 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h>
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)
#define rep3(i, s, n, d) for(ll i = ll(s); i < ll(n); i+=d)
#define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i, n) for (ll i = ll(n)-1; i >= 0; i--)
#define rrep2(i, n, t) for (ll i = ll(n)-1; i >= (ll)t; i--)
#define rrep3(i, n, t, d) for (ll i = ll(n)-1; i >= (ll)t; i-=d)
#define rrep(...) overload4(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SUM(a) accumulate(all(a),0LL)
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define popcount(x) __builtin_popcountll(x)
#define pb push_back
#define eb emplace_back
#ifdef __LOCAL
#define debug(...) { cout << #__VA_ARGS__; cout << ": "; print(__VA_ARGS__); cout << flush; }
#else
#define debug(...) void(0)
#endif
#define INT(...) int __VA_ARGS__;scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;scan(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using LP = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vp = vector<P>;
using vvp = vector<vp>;
template<class S, class T>
istream &operator>>(istream &is, pair<S, T> &p) { return is >> p.first >> p.second; }
template<class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << '{' << p.first << ", " << p.second << '}'; }
template<class S, class T, class U>
istream &operator>>(istream &is, tuple<S, T, U> &t) { return is >> get<0>(t) >> get<1>(t) >> get<2>(t); }
template<class S, class T, class U>
ostream &operator<<(ostream &os, const tuple<S, T, U> &t) {
return os << '{' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << '}';
}
template<class T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &t:v) { is >> t; }
return is;
}
template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
os << '[';
rep(i, v.size())os << v[i] << (i == int(v.size() - 1) ? "" : ", ");
return os << ']';
}
template<class T>
void vecout(const vector<T> &v, char div = '\n') {
rep(i, v.size()) cout << v[i] << (i == int(v.size() - 1) ? '\n' : div);
}
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
void scan() {}
template<class Head, class... Tail>
void scan(Head &head, Tail &... tail) {
cin >> head;
scan(tail...);
}
template<class T>
void print(const T &t) { cout << t << '\n'; }
template<class Head, class... Tail>
void print(const Head &head, const Tail &... tail) {
cout << head << ' ';
print(tail...);
}
template<class... T>
void fin(const T &... a) {
print(a...);
exit(0);
}
struct Init_io {
Init_io() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << boolalpha << fixed << setprecision(15);
cerr << boolalpha << fixed << setprecision(15);
}
} init_io;
const string yes[] = {"no", "yes"};
const string Yes[] = {"No", "Yes"};
const string YES[] = {"NO", "YES"};
const int inf = 1001001001;
const ll linf = 1001001001001001001;
template<class T, class S>
vector<T> cumsum(const vector<S> &v, bool shift_one = true) {
int n = v.size();
vector<T> res;
if (shift_one) {
res.resize(n + 1);
rep(i, n) res[i + 1] = res[i] + v[i];
} else {
res.resize(n);
if (n) {
res[0] = v[0];
rep(i, 1, n) res[i] = res[i - 1] + v[i];
}
}
return res;
}
vvi graph(int n, int m, bool directed = false, int origin = 1) {
vvi G(n);
rep(_, m) {
INT(u, v);
u -= origin, v -= origin;
G[u].pb(v);
if (!directed) G[v].pb(u);
}
return G;
}
template<class T>
vector<vector<pair<int, T>>> weighted_graph(int n, int m, bool directed = false, int origin = 1) {
vector<vector<pair<int, T>>> G(n);
rep(_, m) {
int u, v;
T w;
scan(u, v, w);
u -= origin, v -= origin;
G[u].eb(v, w);
if (!directed) G[v].eb(u, w);
}
return G;
}
template<class T>
void resemble(vector<T> &v) {}
template<class T, class... Tail>
void resemble(vector<T> &v, vector<T> &head, Tail &...tail) {
for (T &e : head) v.pb(e);
resemble(v, tail...);
}
template<class T>
void renumber(vector<T> &v) {}
template<class T, class... Tail>
void renumber(vector<T> &v, vector<T> &head, Tail &...tail) {
for (T &e : head) e = lower_bound(all(v), e) - v.begin();
renumber(v, tail...);
}
template<class T, class... Tail>
vector<T> zip(vector<T> &head, Tail &... tail) {
vector<T> v;
resemble(v, head, tail...);
sort(all(v));
v.erase(unique(all(v)), v.end());
renumber(v, head, tail...);
return v;
}
template<int mod>
class modint {
ll x;
public:
constexpr modint(ll x = 0) : x((x % mod + mod) % mod) {}
static constexpr int get_mod() { return mod; }
constexpr int val() const { return x; }
constexpr modint operator-() const { return modint(-x); }
constexpr modint &operator+=(const modint &a) {
if ((x += a.val()) >= mod) x -= mod;
return *this;
}
constexpr modint &operator++() { return *this += 1; }
constexpr modint &operator-=(const modint &a) {
if ((x += mod - a.val()) >= mod) x -= mod;
return *this;
}
constexpr modint &operator--() { return *this -= 1; }
constexpr modint &operator*=(const modint &a) {
(x *= a.val()) %= mod;
return *this;
}
constexpr modint operator+(const modint &a) const {
modint res(*this);
return res += a;
}
constexpr modint operator-(const modint &a) const {
modint res(*this);
return res -= a;
}
constexpr modint operator*(const modint &a) const {
modint res(*this);
return res *= a;
}
constexpr modint pow(ll t) const {
modint res = 1, a(*this);
while (t > 0) {
if (t & 1) res *= a;
t >>= 1;
a *= a;
}
return res;
}
template<int m>
friend istream &operator>>(istream &, modint<m> &);
// for prime mod
constexpr modint inv() const { return pow(mod - 2); }
constexpr modint &operator/=(const modint &a) { return *this *= a.inv(); }
constexpr modint operator/(const modint &a) const {
modint res(*this);
return res /= a;
}
};
using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1000000007>;
template<int mod>
istream &operator>>(istream &is, modint<mod> &a) { return is >> a.x; }
template<int mod>
constexpr ostream &operator<<(ostream &os, const modint<mod> &a) { return os << a.val(); }
template<int mod>
constexpr bool operator==(const modint<mod> &a, const modint<mod> &b) { return a.val() == b.val(); }
template<int mod>
constexpr bool operator!=(const modint<mod> &a, const modint<mod> &b) { return a.val() != b.val(); }
template<int mod>
constexpr modint<mod> &operator++(modint<mod> &a) { return a += 1; }
template<int mod>
constexpr modint<mod> &operator--(modint<mod> &a) { return a -= 1; }
using mint = modint998244353;
using vm = vector<mint>;
using vvm = vector<vm>;
class NTT {
int pr;
constexpr ll pow_mod(ll x, ll n, int m) {
if (m == 1) return 0;
ll res = 1;
ll now = x % m;
while (n > 0) {
if (n & 1) res = (res * now) % m;
now = (now * now) % m;
n >>= 1;
}
return res;
}
constexpr int primitive_root(int mod) {
if (mod == 2) return 1;
if (mod == 167772161) return 3;
if (mod == 469762049) return 3;
if (mod == 754974721) return 11;
if (mod == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (mod - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (ll) i * i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) divs[cnt++] = x;
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod(g, (mod - 1) / divs[i], mod) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
public:
bool first = true;
mint sum_e[30]; // sum_e[i] = ies[0] * ... * ies[i - 1] * es[i]
mint sum_ie[30]; // sum_ie[i] = es[0] * ... * es[i - 1] * ies[i]
void init(int mod) {
first = false;
pr = primitive_root(mod);
mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1
int cnt2 = __builtin_ctz(mint::get_mod() - 1);
mint e = mint(pr).pow((mint::get_mod() - 1) >> cnt2), ie = e.inv();
for (int i = cnt2; i >= 2; i--) {
// e^(2^i) == 1
es[i - 2] = e;
ies[i - 2] = ie;
e *= e;
ie *= ie;
}
mint now = 1;
for (int i = 0; i <= cnt2 - 2; i++) {
sum_e[i] = es[i] * now;
now *= ies[i];
}
now = 1;
for (int i = 0; i <= cnt2 - 2; i++) {
sum_ie[i] = ies[i] * now;
now *= es[i];
}
}
void operator()(vector<mint> &a, bool inverse = false) {
int n = a.size();
int h = __builtin_ctz(n);
if (inverse) {
rrep(ph, h + 1, 1) {
int w = 1 << (ph - 1), p = 1 << (h - ph);
mint now = 1;
rep(s, w) {
int offset = s << (h - ph + 1);
rep(i, p) {
auto l = a[i + offset];
auto r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] = (l - r) * now;
}
now *= sum_ie[__builtin_ctz(~(unsigned int) (s))];
}
}
} else {
rep(ph, 1, h + 1) {
int w = 1 << (ph - 1), p = 1 << (h - ph);
mint now = 1;
rep(s, w) {
int offset = s << (h - ph + 1);
rep(i, p) {
auto l = a[i + offset];
auto r = a[i + offset + p] * now;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
now *= sum_e[__builtin_ctz(~(unsigned int) (s))];
}
}
}
}
} ntt;
vm convolution(const vm &a, const vm &b) {
if (a.empty()) return {};
if (b.empty()) return {};
int s = a.size() + b.size() - 1;
if (min(a.size(), b.size()) <= 50) {
vm res(s);
if (a.size() >= b.size()) {
rep(i, a.size()) rep(j, b.size()) res[i + j] += a[i] * b[j];
} else {
rep(j, b.size()) rep(i, a.size()) res[i + j] += a[i] * b[j];
}
return res;
}
int t = 1;
while (t < s) t *= 2;
vm A(t), B(t);
rep(i, a.size()) A[i] = a[i];
rep(i, b.size()) B[i] = b[i];
if (ntt.first) ntt.init(mint::get_mod());
ntt(A);
ntt(B);
rep(i, t) A[i] *= B[i];
ntt(A, true);
vm res(s);
mint it = mint(t).inv();
rep(i, s) res[i] = A[i] * it;
return res;
}
template<class T>
class polynomial : public vector<T> {
public:
using vector<T>::vector;
constexpr T eval(T x) const {
T res = 0;
T now = 1;
rep(i, this->size()) {
res += (*this)[i] * now;
now *= x;
}
return res;
}
// return f'(x)
constexpr polynomial differ() const {
vector<T> res;
rep2(i, 1, this->size()) res.pb((*this)[i] * i);
return polynomial(all(res));
}
// return ∫ f(x)dx
constexpr polynomial integral() const {
int n = this->size();
if (n == 0) return vector<T>();
vector<T> res = {0};
rep(i, n) res.pb((*this)[i] / (i + 1));
return polynomial(all(res));
};
constexpr polynomial operator+(const polynomial &a) const {
vector<T> res(max(this->size(), a.size()));
rep(i, this->size()) res[i] += (*this)[i];
rep(i, a.size()) res[i] += a[i];
return polynomial(all(res));
}
constexpr polynomial operator-(const polynomial &a) const {
vector<T> res(max(this->size(), a.size()));
rep(i, this->size()) res[i] += (*this)[i];
rep(i, a.size()) res[i] -= a[i];
return polynomial(all(res));
}
constexpr polynomial operator*(const polynomial &a) const {
vector<T> res = convolution(*this, a);
return polynomial(all(res));
}
constexpr polynomial operator*(T k) const {
polynomial res(*this);
rep(i, res.size()) res[i] *= k;
return res;
}
constexpr polynomial &operator+=(const polynomial &a) {
return *this = *this + a;
}
constexpr polynomial &operator-=(const polynomial &a) {
return *this = *this - a;
}
constexpr polynomial &operator*=(const polynomial &a) {
return *this = *this * a;
}
// P *= (ax + b)
constexpr void multiply(T a = 0, T b = 1) {
int n = this->size();
this->push_back(T(0));
rrep(i, n) {
(*this)[i + 1] += (*this)[i] * a;
(*this)[i] *= b;
}
}
// P /= (ax + b)
constexpr void divide(T a = 0, T b = 1) {
int n = this->size();
assert(n >= 2);
assert(a != 0 or b != 0);
if (b == T(0)) {
assert((*this)[0] == T(0));
T inv = T(1) / a;
rep(i, n - 1) (*this)[i] = (*this)[i + 1] * inv;
this->back() = T(0);
} else {
T inv = T(1) / b;
rep(i, n - 1) {
(*this)[i] *= inv;
(*this)[i + 1] -= (*this)[i] * a;
}
assert(this->back() == T(0));
}
}
};
using poly = polynomial<mint>;
int main() {
INT(n, k);
vi a(n);
cin >> a;
int sz = zip(a).size();
vi cnt(sz);
rep(i, n) cnt[a[i]]++;
vvp rq(n + 1);
int sum = 0;
vector<poly> ps(sz, poly(k + 1));
rep(i, sz) {
rq[cnt[i]].eb(i, sum);
// rep(j, sum + 1) rep(l, k + 1) ps[i][l] += dp[cnt[i]][j][l];
sum += cnt[i];
}
rep(i, n + 1) reverse(all(rq[i]));
vvm dp(n + 1, vm(k + 2));
vvm ndp(n + 1, vm(k + 2));
dp[0][0] = 1;
dp[1][1] = -1;
rep(i, n + 1) {
rep(j, n) rep(s, k + 1) {
for (auto[pos, lim] : rq[i]) {
if (j > lim) break;
ps[pos][s] += dp[j][s];
}
if (s + j <= k) ndp[j][s + j] += dp[j][s];
dp[j + 1][s + 1] += dp[j][s];
dp[j][s] = 0;
}
swap(dp, ndp);
}
poly ans(k + 1);
ans[0] = 1;
rep(i, sz) {
ans *= ps[i];
ans.resize(k + 1);
}
print(ans[k]);
}