結果
| 問題 | No.1621 Sequence Inversions |
| ユーザー |
 2 n
|
| 提出日時 | 2021-07-23 02:18:04 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 93 ms / 3,000 ms |
| コード長 | 7,653 bytes |
| コンパイル時間 | 17,671 ms |
| コンパイル使用メモリ | 247,276 KB |
| 最終ジャッジ日時 | 2025-01-23 07:24:06 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
ソースコード
#pragma GCC target("avx2")//#pragma GCC target("avx")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#pragma GCC optimize("O3")//#pragma GCC optimize("Ofast")//#pragma GCC optimize("unroll-loops")// #include<bits/stdc++.h>// #include <array>#include <vector>// #include <list>// #include <forward_list>#include <deque>#include <queue>#include <stack>// #include <bitset>#include <unordered_map>#include <map>#include <unordered_set>#include <set>#include <algorithm>#include <string>#include <iostream>#include <iomanip>// #include <sstream>// #include <bit>// #include <complex>// #include <exception>// #include <fstream>// #include <functional>// #include <iosfwd>// #include <iterator>// #include <limits>// #include <locale>// #include <memory>// #include <new>// #include <numeric>// #include <stdexcept>// #include <typeinfo>// #include <utility>// #include <valarray>// #include <atomic>// #include <chrono>// #include <condition_variable>// #include <future>// #include <mutex>// #include <random>// #include <ratio>// #include <regex>// #include <scoped_allocator>// #include <system_error>// #include <thread>// #include <tuple>// #include <typeindex>// #include <type_traits>// #include <cctype>// #include <cerrno>// #include <cfloat>// #include <ciso646>// #include <climits>// #include <clocale>// #include <cmath>// #include <csetjmp>// #include <csignal>// #include <cstdarg>// #include <cstddef>// #include <cstdio>// #include <cstdlib>// #include <cstring>#include <ctime>// #include <ccomplex>// #include <cfenv>// #include <cinttypes>// #include <cstdbool>// #include <cstdint>// #include <ctgmath>// #include <cwchar>// #include <cwctype>using namespace std;#include <atcoder/all>using namespace atcoder;#define STRINGIFY(n) #n#define TOSTRING(n) STRINGIFY(n)using ll = long long;using ull = unsigned long long;template<typename T> using maxque = priority_queue<T>;template<typename T> using minque = priority_queue<T,vector<T>,greater<T>>;#define int ll#define endl "\n"#define unless(cond) if(!(cond))#define until(cond) while(!(cond))#define rep(i,s,e) for(ll i = (s); i < (e); ++i)#define repR(i,s,e) for(ll i = (e)-1; (s) <= i; --i)#define repE(i,s,e) for(ll i = (s); i <= (e); ++i)#define repER(i,s,e) for(ll i = (e); (s) <= i; --i)#define repSubsetR(set,super) for(ll _super=super,set = _super; 0 <= set; --set)if(set &= _super, true)#define ALL(xs) begin(xs), end(xs)#define ALLR(xs) rbegin(xs), rend(xs)#define ALLC(xs) cbegin(xs), cend(xs)#define ALLCR(xs) crbegin(xs), crend(xs)template<typename C> void uniq(C &xs){ xs.erase(unique(ALL(xs)), xs.end()); }template<typename C> constexpr ll len(C &&xs){ return size(forward<C>(xs)); }ll BIT(ll n){ return 1LL<<n; }auto clock0 = clock();void debug_h(const char *file, signed line, const char *str_args){ cerr << file << ":" << line << ": " << str_args << " => "; }template<class X, class... Xs> void debug_(const X &x, const Xs&... xs){ cerr << x; (void)initializer_list<int>{ (cerr << ", " << xs,0)... };cerr <<endl; }void debug_(){ cerr << endl; }#define ASSERT(pred,...) (static_cast<bool>(pred) ? void(0) : (debug_h(__FILE__, __LINE__, "ASSERT FAIL! " #pred "; " #__VA_ARGS__),debug_(__VA_ARGS__),exit(1)))template<class X> X &&dbg_(X &&x){ cerr<<x<<endl; return forward<X>(x); }#ifdef DEBUG#define dbg(x) (debug_h(__FILE__, __LINE__, "" #x),dbg_(x))#define debug(...) (debug_h(__FILE__, __LINE__, "" #__VA_ARGS__),debug_(__VA_ARGS__))#define clk(...) (cerr << __VA_ARGS__ " @ " << (clock()-clock0) <<endl,(void)0)#else#define dbg(x) (x)#define debug(...) ((void)0)#define clk(...) ((void)0)//#define ASSERT(pred,...) ((void)0)#endif#define DEF_ORD(op) bool operator op(SELF_ const &b)const { return Ord() op b.Ord(); }#define ORD(...) auto Ord()const{ return tie(__VA_ARGS__); } typedef auto self_fn_() -> decltype(*this); using SELF_ = decltype(((self_fn_*)nullptr)()); DEF_ORD(==) DEF_ORD(!=) DEF_ORD(<) DEF_ORD(>) DEF_ORD(<=) DEF_ORD(>=)template<class C> auto operator<<(ostream &out, const C &xs) -> enable_if_t<!is_same_v<decay_t<C>, char*> && !is_same_v<decay_t<C>, string>, decltype(begin(xs),out)&> { out<<"[ "; for(auto&&x:xs)out<<x<<", "; return out<<"]"; }template<class C> auto operator>>(istream &in, C &xs) -> enable_if_t<!is_same_v<decay_t<C>, char*> && !is_same_v<decay_t<C>, string>, decltype(begin(xs),in)&> { for(auto&x:xs)in>>x; return in; }template<class Tuple, size_t... I> void print_tuple_(ostream &out, Tuple const &xs, std::index_sequence<I...>){ out << "("; (void)initializer_list<int>{ (out << (I==0?"":", ") << std::get<I>(xs),0)... }; out << ")"; }template<class... T> ostream &operator<<(ostream &out, tuple<T...> const &xs){ print_tuple_(out, xs, make_index_sequence<sizeof...(T)>()); return out; }template<class Tuple, size_t... I> void read_tuple_(istream &in, Tuple &xs, std::index_sequence<I...>){ (void)initializer_list<int>{ (in >> std::get<I>(xs),0)... }; }template<class... T> istream &operator>>(istream &in, tuple<T...> &xs){ read_tuple_(in, xs, make_index_sequence<sizeof...(T)>()); return in; }template<class S, class T> ostream &operator<<(ostream &out, pair<S, T> const &p){ return out << "(" << p.first << ", " << p.second << ")"; }template<class S, class T> istream &operator>>(istream &in, pair<S, T> &p){ return in >> p.first >> p.second; }template<typename MINT, typename = internal::is_modint_t<MINT>> ostream &operator<<(ostream &out, MINT x){ return out << x.val(); }template<typename MINT, typename = internal::is_modint_t<MINT>> istream &operator>>(istream &in, MINT &x){ ll a; in>>a; x = a; return in; }template<typename F> struct Fix : F {template<typename G> Fix(G &&g) : F{forward<G>(g)} {}template<typename... Xs> decltype(auto) operator()(Xs&&... xs)const{ return F::operator()(*this, forward<Xs>(xs)...); }};template<typename F> Fix(F&&) -> Fix<decay_t<F>>;template<typename T,typename U> bool chmin(T &a, U b){ if(a <= b)return false; a = b; return true; }template<typename T,typename U> bool chmax(T &a, U b){ if(a >= b)return false; a = b; return true; }const signed MOD = 998244353;using mint = static_modint<MOD>;// using mint = dynamic_modint<-1>; // mint::set_mod(mod);// using mint0 = dynamic_modint<0>; // mint0::set_mod(mod);const ll INF = BIT(60);mint op(mint a, mint b) {return a+b;}mint e() {return 0;}ll solve(){ll n,ktarget;cin>>n>>ktarget;map<ll,ll> cnt;rep(i,0,n){ll x;cin>>x;++cnt[x];}ll csum=0;vector<mint> dp2(ktarget+1);dp2[0] = 1;for(auto [_i,c] : cnt){ll kmax=0;vector<segtree<mint,op,e>> dp(kmax+1, segtree<mint,op,e>(n+1));dp[0].set(csum, 1);rep(foo,0,c){auto old = move(dp);dp.resize(kmax+csum+1, segtree<mint,op,e>(n+1));repE(k,0,kmax)repE(j,0,csum) dp[k+j].set(j, old[k].prod(j,csum+1));kmax += csum;}vector<mint> dp3(min(ktarget,kmax)+1);repE(k,0,min(ktarget,kmax)) dp3[k] = dp[k].prod(0, csum+1);dp2 = convolution(dp2, dp3);if(ktarget+1 < len(dp2)) dp2.resize(ktarget+1);csum += c;}return dp2[ktarget].val();}signed main(){cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << fixed << setprecision(15);try{cout << solve() << endl;/*cout << (solve()?"Yes":"No") << endl; // */return 0;}catch(exception& e){cerr << e.what() << endl;}catch(char *s){cerr << s << endl;}return 1;}