結果
問題 | No.2485 Add to Variables (Another) |
ユーザー | ytqm3 |
提出日時 | 2023-09-22 00:08:01 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 13,714 bytes |
コンパイル時間 | 4,057 ms |
コンパイル使用メモリ | 273,732 KB |
実行使用メモリ | 30,720 KB |
最終ジャッジ日時 | 2024-07-08 11:27:59 |
合計ジャッジ時間 | 10,241 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
26,752 KB |
testcase_01 | AC | 41 ms
26,752 KB |
testcase_02 | AC | 41 ms
26,624 KB |
testcase_03 | AC | 41 ms
26,624 KB |
testcase_04 | RE | - |
testcase_05 | AC | 42 ms
26,752 KB |
testcase_06 | RE | - |
testcase_07 | AC | 43 ms
26,880 KB |
testcase_08 | AC | 41 ms
26,752 KB |
testcase_09 | AC | 41 ms
26,752 KB |
testcase_10 | AC | 42 ms
26,624 KB |
testcase_11 | AC | 43 ms
26,752 KB |
testcase_12 | AC | 54 ms
26,880 KB |
testcase_13 | AC | 42 ms
26,752 KB |
testcase_14 | AC | 42 ms
26,880 KB |
testcase_15 | AC | 42 ms
26,752 KB |
testcase_16 | AC | 41 ms
26,880 KB |
testcase_17 | AC | 42 ms
26,880 KB |
testcase_18 | AC | 43 ms
26,880 KB |
testcase_19 | AC | 43 ms
26,752 KB |
testcase_20 | AC | 43 ms
26,752 KB |
testcase_21 | AC | 40 ms
26,752 KB |
testcase_22 | AC | 42 ms
26,752 KB |
testcase_23 | AC | 43 ms
26,880 KB |
testcase_24 | AC | 41 ms
26,752 KB |
testcase_25 | AC | 123 ms
30,720 KB |
testcase_26 | AC | 94 ms
28,928 KB |
testcase_27 | AC | 49 ms
27,136 KB |
testcase_28 | AC | 70 ms
27,776 KB |
testcase_29 | AC | 105 ms
28,416 KB |
testcase_30 | AC | 123 ms
30,720 KB |
testcase_31 | AC | 123 ms
30,720 KB |
testcase_32 | AC | 130 ms
30,720 KB |
testcase_33 | AC | 129 ms
30,720 KB |
testcase_34 | AC | 127 ms
30,720 KB |
testcase_35 | AC | 132 ms
30,720 KB |
testcase_36 | AC | 123 ms
30,720 KB |
testcase_37 | AC | 123 ms
30,720 KB |
testcase_38 | AC | 128 ms
30,720 KB |
testcase_39 | AC | 125 ms
30,720 KB |
testcase_40 | AC | 126 ms
30,720 KB |
testcase_41 | AC | 131 ms
30,720 KB |
testcase_42 | RE | - |
testcase_43 | RE | - |
ソースコード
#include <bits/stdc++.h>#if __has_include(<atcoder/all>)#include <atcoder/all>#endifusing namespace std;using ll = long long;using ull = unsigned long long int;using i128 = __int128_t;using pii = pair<int, int>;using pll = pair<ll, ll>;using ld = long double;template <typename T> using vc = vector<T>;template <typename T> using vvc = vector<vc<T>>;template <typename T> using vvvc = vector<vvc<T>>;using vi = vc<int>;using vl = vc<ll>;using vpi = vc<pii>;using vpl = vc<pll>;template <class T> using pq = priority_queue<T>;template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;#define overload5(a, b, c, d, e, name, ...) name#define overload4(a, b, c, d, name, ...) name#define REP0(n) for(ll jidlsjf = 0; jidlsjf < n; ++jidlsjf)#define REP1(i, n) for(ll i = 0; i < (n); ++i)#define REP2(i, a, b) for(ll i = (a); i < (b); ++i)#define REP3(i, a, b, c) for(ll i = (a); i < (b); i += (c))#define rep(...) overload4(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__)#define per0(n) for(int jidlsjf = 0; jidlsjf < (n); ++jidlsjf)#define per1(i, n) for(ll i = (n)-1; i >= 0; --i)#define per2(i, a, b) for(ll i = (a)-1; i >= b; --i)#define per3(i, a, b, c) for(ll i = (a)-1; i >= (b); i -= (c))#define per(...) overload4(__VA_ARGS__, per3, per2, per1, per0)(__VA_ARGS__)#define fore0(a) rep(a.size())#define fore1(i, a) for(auto &&i : a)#define fore2(a, b, v) for(auto &&[a, b] : v)#define fore3(a, b, c, v) for(auto &&[a, b, c] : v)#define fore4(a, b, c, d, v) for(auto &&[a, b, c, d] : v)#define fore(...) overload5(__VA_ARGS__, fore4, fore3, fore2, fore1, fore0)(__VA_ARGS__)#define perm(v) for(bool permrepflag = true; (permrepflag ? exchange(permrepflag, false) : next_permutation(all(v)));)#define fi first#define se second#define pb push_back#define ppb pop_back#define ppf pop_front#define eb emplace_back#define drop(s) cout << #s << endl, exit(0)#define si(c) (int)(c).size()#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))#define lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{}))#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))#define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{}))#define rng(v, l, r) v.begin() + (l), v.begin() + (r)#define all(c) begin(c), end(c)#define rall(c) rbegin(c), rend(c)#define SORT(v) sort(all(v))#define RSORT(v) sort(rall(v))#define REV(v) reverse(all(v))#define UNIQUE(x) SORT(x), x.erase(unique(all(x)), x.end())template <typename T = ll, typename S> T SUM(const S &v) { return accumulate(all(v), T(0)); }#define MIN(v) *min_element(all(v))#define MAX(v) *max_element(all(v))#define INT(...)\int __VA_ARGS__;\IN(__VA_ARGS__)#define INTd(...)\int __VA_ARGS__;\IN2(__VA_ARGS__)#define LL(...)\ll __VA_ARGS__;\IN(__VA_ARGS__)#define LLd(...)\ll __VA_ARGS__;\IN2(__VA_ARGS__)#define STR(...)\string __VA_ARGS__;\IN(__VA_ARGS__)#define CHR(...)\char __VA_ARGS__;\IN(__VA_ARGS__)#define LD(...)\ld __VA_ARGS__;\IN(__VA_ARGS__)#define VEC(type, name, size)\vector<type> name(size);\IN(name)#define VECd(type, name, size)\vector<type> name(size);\IN2(name)#define VEC2(type, name1, name2, size)\vector<type> name1(size), name2(size);\for(int i = 0; i < size; i++) IN(name1[i], name2[i])#define VEC2d(type, name1, name2, size)\vector<type> name1(size), name2(size);\for(int i = 0; i < size; i++) IN2(name1[i], name2[i])#define VEC3(type, name1, name2, name3, size)\vector<type> name1(size), name2(size), name3(size);\for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i])#define VEC3d(type, name1, name2, name3, size)\vector<type> name1(size), name2(size), name3(size);\for(int i = 0; i < size; i++) IN2(name1[i], name2[i], name3[i])#define VEC4(type, name1, name2, name3, name4, size)\vector<type> name1(size), name2(size), name3(size), name4(size);\for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i], name4[i]);#define VEC4d(type, name1, name2, name3, name4, size)\vector<type> name1(size), name2(size), name3(size), name4(size);\for(int i = 0; i < size; i++) IN2(name1[i], name2[i], name3[i], name4[i]);#define VV(type, name, h, w)\vector<vector<type>> name(h, vector<type>(w));\IN(name)#define VVd(type, name, h, w)\vector<vector<type>> name(h, vector<type>(w));\IN2(name)int scan() { return getchar(); }void scan(int &a) { cin >> a; }void scan(long long &a) { cin >> a; }void scan(char &a) { cin >> a; }void scan(ld &a) { cin >> a; }void scan(string &a) { cin >> a; }template <class T, class S> void scan(pair<T, S> &p) { scan(p.first), scan(p.second); }template <class T> void scan(vector<T> &);template <class T> void scan(vector<T> &a) {for(auto &i : a) scan(i);}template <class T> void scan(T &a) { cin >> a; }void IN() {}void IN2() {}template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {scan(head);IN(tail...);}template <class Head, class... Tail> void IN2(Head &head, Tail &...tail) {scan(head);--head;IN2(tail...);}template<class T> void prt_(T a){ cout<<a; }template<class T,class U> void prt_(pair<T,U> a){ cout<<"{"<<a.fi<<", "<<a.se<<"}"; }void prt_(ld a){ printf("%.15Lf",a); }template<class T> void prt(vc<T> a){for(size_t i=0;i<a.size();++i){prt_(a[i]);cout<<" \n"[i==a.size()-1];}}template<class T> void prt(vvc<T> a){for(auto& v:a){for(size_t i=0;i<v.size();++i){prt_(v[i]);cout<<" \n"[i==v.size()-1];}}}template<class T> void prt(T a){ prt_(a),cout<<"\n"; }template<class T,class... Args> void prt(T a,Args... args){ prt_(a),cout<<" ",prt(args...); }template<class Head,class... Tail> struct multi_dim_vector{ using type=vc<typename multi_dim_vector<Tail...>::type>; };template<class T> struct multi_dim_vector<T>{ using type=T; };template<class T,class Arg> vc<T> mvec(int n,Arg&& arg){ return vc<T>(n,arg); }template<class T,class... Args> class multi_dim_vector<Args...,T>::type mvec(int n,Args&&... args){return typename multi_dim_vector<Args...,T>::type(n,mvec<T>(args...));}template<class T> T REVed(T a){reverse(a.begin(),a.end());return a;}template<class T> T SORTed(T a){sort(a.begin(),a.end());return a;}template<class T> T RSORTed(T a){sort(a.rbegin(),a.rend());return a;}vi iota(int n){vi res(n);iota(res.begin(),res.end(),0);return res;}template <class T> bool chmax(T &a, T b){ return (a < b ? a = b, 1 : 0); }template <class T> bool chmin(T &a, T b){ return (a > b ? a = b, 1 : 0); }template<class T> auto runLength(T a) -> vc<pair<typename decltype(a)::value_type,ll>>{int n=a.size();vc<pair<typename decltype(a)::value_type,ll>> res;if(n==0){ return res; }typename decltype(a)::value_type now=a[0];ll l=1;rep(i,1,n){if(a[i-1]==a[i]){ l++; }else{res.pb(now,l);now=a[i],l=1;}}res.pb(now,l);return res;}template<int mod> struct mymodint{ll x;static constexpr ll get_mod(){ return mod; }ll val(){ return x; }mymodint(ll x_=0):x((x_%mod+mod)%mod){}mymodint operator-(){ return (x==0)?0:mod-x; }mymodint operator+(mymodint rhs){ return mymodint(*this)+=rhs; }mymodint operator-(mymodint rhs){ return mymodint(*this)-=rhs; }mymodint operator*(mymodint rhs){ return mymodint(*this)*=rhs; }mymodint operator/(mymodint rhs){ return mymodint(*this)/=rhs; }mymodint pow(ll rhs){mymodint res=1,now=(*this);while(rhs){res*=((rhs&1)?now:1),now*=now,rhs>>=1;}return res;}mymodint& operator+=(mymodint rhs){x+=rhs.x,x-=((x>=mod)?mod:0);return (*this);}mymodint& operator-=(mymodint rhs){x-=rhs.x;x+=((x<0)?mod:0);return (*this);}mymodint& operator*=(mymodint rhs){x=x*rhs.x%mod;return (*this);}mymodint& operator/=(mymodint rhs){ return (*this)*=rhs.pow(mod-2); }bool operator==(mymodint rhs){ return x==rhs.x; }bool operator!=(mymodint rhs){ return x!=rhs.x; }};template<int mod> using modint=#if __has_include(<atcoder/all>)atcoder::static_modint<mod>;#elsemymodint<mod>;#endiftemplate<int mod> std::ostream& operator<<(std::ostream& os,modint<mod> x){return os<<(x.val());}template<int mod> std::istream& operator>>(std::istream& is,modint<mod>& x){ll t;is>>t,x=t;return is;}template<class T> struct cmb{vc<T> fac,ifac;cmb(int mx=3000000):fac(mx+1,1),ifac(mx+1,1){for(int i=1;i<=mx;++i){ fac[i]=fac[i-1]*i; }ifac[mx]/=fac[mx];for(int i=mx;i>0;--i){ ifac[i-1]=ifac[i]*i; }}T operator()(ll n,ll k){if(n<0||k<0||n<k){ return 0; }return fac[n]*ifac[k]*ifac[n-k];}T f(ll n){return n<0?T(0):fac[n];}T fi(ll n){return n<0?T(0):ifac[n];}};int main(){using fp=modint<998244353>;cmb<fp> C;INT(n,m);VEC(ll,b,n);vl c(n-1);c[0]=b[1];rep(i,1,n-1){c[i]=b[i+1]-b[i];}auto f=mvec<fp>(n-1,m+1,0);rep(j,m+1){f[0][j]=C.fi(j)*C.fi(j+b[0]-c[0]);}rep(i,1,n-1){rep(j,0,m+1){f[i][j]=C.fi(j)*C.fi(j-c[i]);}}vc<fp> g(m+1);g[0]=1;rep(i,n-1){g=atcoder::convolution(f[i],g);g.resize(m+1);}int s=SUM(c);fp ans=0;rep(i,m+1){ans+=g[i]*C.fi(m-b[0]-i)*C.fi(s-i);}prt((ans*C.f(b[0])*C.f(m-b[0])*C(m,b[0])).val());}