#767392 (C++17) No.1693 Invasion

提出ソース

結果

問題	No.1693 Invasion
ユーザー	eQe
提出日時	2022-06-01 04:29:06
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	28 ms / 2,000 ms
コード長	4,984 bytes
コンパイル時間	4,416 ms
コンパイル使用メモリ	286,332 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-09-21 01:26:57
合計ジャッジ時間	5,624 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	1 ms 6,944 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	3 ms 6,944 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	21 ms 6,948 KB
testcase_10	AC	20 ms 6,940 KB
testcase_11	AC	10 ms 6,944 KB
testcase_12	AC	21 ms 6,940 KB
testcase_13	AC	9 ms 6,940 KB
testcase_14	AC	11 ms 6,940 KB
testcase_15	AC	7 ms 6,944 KB
testcase_16	AC	12 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	28 ms 6,944 KB
testcase_19	AC	16 ms 6,940 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	27 ms 6,940 KB
testcase_22	AC	27 ms 6,940 KB
testcase_23	AC	27 ms 6,940 KB

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

ソースコード

raw source code

#include<atcoder/all>
#include<bits/stdc++.h>
using namespace atcoder;
using namespace std;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fin(a) return pt(a)
using ll=long long;
using ld=long double;
using v1=vector<ll>;
using v2=vector<v1>;
using v3=vector<v2>;
using v4=vector<v3>;
using pll=pair<ll,ll>;
using mll=map<ll,ll>;
ll inf=3e18;
ld pi=acos(-1);
ld eps=1e-10;
template<class T>using ascending_priority_queue=std::priority_queue<T,vector<T>,greater<T>>;
template<class T>using descending_priority_queue=std::priority_queue<T>;
template<class T>bool chmax(T&a,const T&b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,const T&b){if(b<a){a=b;return 1;}return 0;}
template<class T>T max(const vector<T>&a){return *max_element(all(a));}
template<class T>T min(const vector<T>&a){return *min_element(all(a));}
template<class T>T sum(const vector<T>&a){return accumulate(all(a),T(0));}
template<class T>T popcnt(T a){return __builtin_popcountll(a);}
template<class T>pll mima(const T&a,const T&b){return {min(a,b),max(a,b)};}
ostream&operator<<(ostream&os,const modint1000000007&x){os<<x.val();return os;}
ostream&operator<<(ostream&os,const modint998244353&x){os<<x.val();return os;}
ostream&operator<<(ostream&os,const modint&x){os<<x.val();return os;}
template<class T1,class T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<class T1,class T2>ostream&operator<<(ostream&os,const pair<T1,T2>&p){os<<p.first<<" "<<p.second;return os;}
template<class T>istream&operator>>(istream&is,vector<T>&v){for(T&x:v)is>>x;return is;}
template<class T>ostream&operator<<(ostream&os,const vector<T>&v){for(int i=0;i<(int)v.size();i++){os<<v[i]<<(i+1==(int)v.size()?"":" ");}return os;}
template<class...A>int pt_rest(){cout<<'\n';return 0;}
template<class...A>int pt(){cout<<'\n';return 0;}
template<class T,class...A>int pt_rest(const T&first,const A&...rest){cout<<" "<<first;pt_rest(rest...);return 0;}
template<class T,class...A>int pt(const T&first,const A&...rest){cout<<first;pt_rest(rest...);return 0;}
template<class V,class H>void resize(vector<V>&vec,const H head){vec.resize(head);}
template<class V,class H,class...T>void resize(vector<V>&vec,const H&head,const T...tail){vec.resize(head);for(auto&v:vec)resize(v,tail...);}
template<class V,class T>void fill(V&x,const T&val){x=val;}
template<class V,class T>void fill(vector<V>&vec,const T&val){for(auto&v:vec)fill(v,val);}
template<class H>void vin(istream&is,const int idx,vector<H>&head){is>>head[idx];}
template<class H,class...T>void vin(istream&is,const int idx,vector<H>&head,T&...tail){vin(is>>head[idx],idx,tail...);}
template<class H,class...T>void vin(istream&is,vector<H>&head,T&...tail){for(int i=0;i<(int)head.size();i++)vin(is,i,head,tail...);}
template<class H,class...T>void vin(vector<H>&head,T&...tail){vin(cin,head,tail...);}
template<class H>void sin(istream&is,H&head){is>>head;}
template<class H,class...T>void sin(istream&is,H&head,T&...tail){sin(is>>head,tail...);}
template<class H,class...T>void sin(H&head,T&...tail){sin(cin,head,tail...);}
v1 divisor(ll n){mll m;for(ll i=1;i*i<=n;i++)if(n%i==0){m[i]++;m[n/i]++;}v1 v;for(auto[x,_]:m)v.emplace_back(x);return v;}
mll factor(ll n){mll m;for(ll i=2;i*i<=n;i++)while(n%i==0){m[i]++;n/=i;}if(n>1)m[n]++;return m;}
ll lsqrt(ll x){assert(x>=0);if(x<=1)return x;ll r=sqrt(x)-1;while((r+1)<=x/(r+1))r++;return r;};
using S=ll;
S op(S a,S b){return a+b;}
S e(){return 0;}

template<class T>struct Combination{
  vector<T>fa,rfa,bs;
  vector<vector<pair<bool,T>>>mp;
  ll LIM=5000;
  Combination(ll n){
    fa.resize(n+1);
    rfa.resize(n+1);
    fa[0]=rfa[0]=1;
    for(ll i=1;i<=n;i++)fa[i]=fa[i-1]*i;
    for(ll i=1;i<=n;i++)rfa[i]=rfa[i-1]/i;
    
    bs.resize(n+1);
    bs[0]=1;
    for(ll i=1;i<=n;i++)bs[i]=bs[i-1]+T(-1).pow(i&1)*rfa[i];
    
    if(n<=LIM)mp.resize(n+1,vector<pair<bool,T>>(n+1));
  }
  T C(ll n,ll k){return n<k||n<0||k<0?0:fa[n]*rfa[k]*rfa[n-k];}
  T P(ll n,ll k){return C(n,k)*fa[k];}
  T H(ll n,ll k){return C(n-1+k,k);}
  T S(ll n,ll k){
    T res=0;
    for(ll i=0;i<=k;i++)res+=T(-1).pow((k-i)&1)*C(k,i)*T(i).pow(n);
    res*=rfa[k];
    return res;
  }
  T B(ll n,ll k){
    T res=0;
    for(ll i=0;i<=k;i++)res+=T(i).pow(n)*rfa[i]*bs[k-i];
    return res;
  }
  T p(ll n,ll k){//自然数nをk個の"0"以上の整数に分割する方法
    if(n==0 and k==0)return 1;
    if(k==0)return 0;
    if(mp[n][k].first)return mp[n][k].second;
    if(n-k>=0)return (mp[n][k]={true,p(n,k-1)+p(n-k,k)}).second;
    return (mp[n][k]={true,p(n,k-1)}).second;
  }
};

int main(void){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  ll N,M;sin(N,M);
  v1 a(N);cin>>a;
  sort(all(a));
  
  v1 dp(M+1,inf);
  dp[0]=0;
  for(ll i=0;i<N;i++)for(ll j=0;j<=M;j++)if(j+a[i]<=M)chmin(dp[j+a[i]],dp[j]+1);
  
  using mint=modint998244353;
  Combination<mint>com(M);
  mint ans=0;
  for(ll k=0;k<=M;k++)ans+=com.C(M-dp[k],k-dp[k]);
  pt(ans);
}

yukicoder

結果

テストケース

ソースコード