#914479 (C++17) No.2485 Add to Variables (Another)

提出ソース

結果

問題	No.2485 Add to Variables (Another)
ユーザー	ytqm3
提出日時	2023-09-22 00:08:01
言語	C++17 (gcc 12.3.0 + boost 1.83.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	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#endif

using 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>;
#else
  mymodint<mod>;
#endif

template<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());
}

yukicoder

結果

テストケース

ソースコード