結果

問題 No.3046 yukicoderの過去問
ユーザー 霊夢の３分ハッキング霊夢の３分ハッキング
提出日時 2023-11-26 16:07:27
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 8,451 bytes
コンパイル時間 6,423 ms
コンパイル使用メモリ 306,980 KB
実行使用メモリ 17,664 KB
最終ジャッジ日時 2024-09-26 11:47:34
合計ジャッジ時間 9,277 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,752 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 15 ms
11,904 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 9 ms
11,904 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i=0; i<n; i++)
#define ll long long
#define str string
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vs vector<string>

int gi() {
  int i;
  cin >> i;
  return i;
}

ll gl() {
  ll l;
  cin >> l;
  return l;
}

double gd() {
  double d;
  cin >> d;
  return d;
}

string gs() {
  string s;
  cin >> s;
  return s;
}

vector<int> gia(int n) {
  vector<int> A(n);
  rep(i,n) {
    cin >> A[i];
  }
  return A;
}

vector<ll> gla(int n) {
  vector<ll> A(n);
  rep(i,n) {
    cin >> A[i];
  }
  return A;
}

vector<string> gsa(int n) {
  vector<string> A(n);
  rep(i,n) {
    cin >> A[i];
  }
  return A;
}

vector<vector<int>> gsi2(int n, int m) {
  vector<vector<int>> A(n, vector<int>(m));
  rep(i,n) {
    rep(j,m) {
        cin >> A[i][j];
    }
  }
  return A;
}

vector<vector<int>> readGraph(int n, int m, bool f=false) {
  vector<vector<int>> G(n);
  rep(i,m){
    int a=gi();
    int b=gi();
    a--;
    b--;
    G[a].push_back(b);
    if(!f){
      G[b].push_back(a);
    }
  }
  return G;
}

vector<vector<pair<ll,int>>> readGraphWithWeight(int n, int m, bool f=false) {
  vector<vector<pair<ll,int>>> G(n);
  rep(i,m){
    int a=gi();
    int b=gi();
    ll c=gi();
    a--;
    b--;
    pair<ll,int> p=make_pair(c,b);
    G[a].push_back(p);
    if(!f){
      pair<ll,int> p2=make_pair(c,a);
      G[b].push_back(p2);
    }
  }
  return G;
}

void ov(vector<int> v) {
  if((int)v.size()==0)return;
  rep(i,(int)v.size()-1) {
    cout << v[i] << ' ';
  }
  cout << v[v.size()-1] << endl;
}

// 二分グラフ判定
bool isBipartite(vector<pair<ll,pair<int,int>>>& E, int N) {
  dsu uf(N*2);
  rep(i,E.size()) {
    int a=E[i].second.first;
    int b=E[i].second.second;
    ll w=E[i].first;
    uf.merge(a,b+N);
    uf.merge(a+N,b);
  }

  rep(i,N) {
    if(uf.same(i,i+N))return false;
  }
  return true;
}

vector<vl> matrixMulti(vector<vl>& A, vector<vl>& B) {
  int AR=A.size();
  int AC=A[0].size();
  int BC=B[0].size();
  vector<vl> ans(AR,vl(BC,0));
  rep(i,AR) {
    rep(j,BC) {
      rep(k,AC) {
        ans[i][k]+=A[i][j]*B[j][k];
      }
    }
  } 
  return ans;
}

vector<vl> matrixPow(vector<vl>& A, int p) {
  int q=p;
  int cnt=0;
  while(q>0) {
    cnt++;
    q=q>>1;
  }
  vector<vector<vl>> PAS;
  PAS.push_back(A);
  rep(i,cnt-1) {
    PAS.push_back(matrixMulti(PAS[i],PAS[i]));
  }

  vector ans(A.size(),vl(A.size(),0));
  rep(i,ans.size()) {
    ans[i][i]=1;
  }
  rep(i,cnt) {
    if((p>>i & 1) == 0)continue;
    ans=matrixMulti(ans,PAS[i]);
  }
  return ans;
}

vector<string> split(const string &s, char delim) {
    vector<string> elems;
    string item;
    for (char ch: s) {
        if (ch == delim) {
            if (!item.empty())
                elems.push_back(item);
            item.clear();
        }
        else {
            item += ch;
        }
    }
    if (!item.empty())
        elems.push_back(item);
    return elems;
}

// private
void recursive_comb(int *indexes, int s, int rest, std::function<void(int *)> f) {
  if (rest == 0) {
    f(indexes);
  } else {
    if (s < 0) return;
    recursive_comb(indexes, s - 1, rest, f);
    indexes[rest - 1] = s;
    recursive_comb(indexes, s - 1, rest - 1, f);
  }
}

// nCkの組み合わせに対して処理を実行する
void foreach_comb(int n, int k, std::function<void(int *)> f) {
  int indexes[k];
  recursive_comb(indexes, n - 1, k, f);
}

vector<long long> fact, fact_inv, inv;

// nCkの前計算
void init_nCk(int SIZE, int mod) {
    fact.resize(SIZE + 5);
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}
/*  nCk :MODでの二項係数を求める(前処理 int_nCk が必要)
    計算量:O(1)
*/
long long nCk(int n, int k, int mod) {
    if(n<k)return 0;
    return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) % mod;
}

int lis(vector<int> A) {
  int MAX=INT_MAX;
  vector<int> dp((int)A.size(), MAX);
  rep(i, (int)A.size()) {
    int a=A[i];
    int mn=-1;
    int mx=(int)A.size();
    while(mx-mn>1){
      int idx=(mx+mn)/2;
      int v=dp[idx];
      if(a>v) {
        mn=idx;
      } else {
        mx=idx;
      }
    }
    dp[mx]=a;
  }

  int ans=0;
  rep(i, (int)A.size()) {
    if(dp[i]!=MAX){
      ans+=1;
    } else {
      break;
    }
  }
  return ans;
}

ll uclid(ll m, ll n) {
  if(n==0) {
    return m;
  } else {
    return uclid(n,m%n);
  }
}

vector<ll> yakusu(ll N) {
  vector<ll> ans;
  for(ll i=1;i<N+1;i++) {
    if(i*i>N)break;
    if(N%i==0) {
      ans.push_back(i);
      if(N/i!=i) {
        ans.push_back(N/i);
      }
    }
  }
  return ans;
}

vector<ll> insuB(ll N) {
  vector<ll> ans;
  ll i=2;
  while(i*i<=N) {
    if(N%i==0) {
      ans.push_back(i);
      N=N/i;
    } else {
      i++;
    }
  }
  if(N!=1) {
    ans.push_back(N);
  }
  return ans;
}

map<ll,ll> insuBm(ll N) {
  map<ll,ll> ans;
  for(ll i=2;i<N;i++){
    if(i*i>N)break;
    while(N%i==0) {
      ans[i]++;
      N=N/i;
    }
  }
  if(N!=1) {
    ans[N]++;
  }
  return ans;
}


void rotate(vector<vector<ll>>& A) {
  vector<vector<ll>> ra(A[0].size(),vector<ll>(A.size(),0));

  rep(i, (int)A[0].size()) {
    rep(j,(int)A.size()) {
      ra[i][j]=A[A.size()-j-1][i];
    }
  }
  A=ra;
}

vector<bool> eratostenes(int N) {
  vector<bool> ans(N+1,true);
  ans[0]=false;
  ans[1]=false;
  for(int i=2; i<=N; i++) {
    if(ans[i]==false)continue;
    for(int j=2*i; j<=N; j+=i) {
      ans[j]=false;
    }
  }
  return ans;
}

pair<ll,ll> invGcd(ll a,ll b) {
  a%=b;
  if(a==0)return make_pair(b,0);
  ll s=b;
  ll t=a;
  ll m0=0;
  ll m1=1;
  while(t>0) {
    ll u=s/t;
    s-=t*u;
    m0-=m1*u;
    ll tmp=s;
    s=t;
    t=tmp;
    tmp=m0;
    m0=m1;
    m1=tmp;
  }
  if(m0<0)m0+=b/s;
  return make_pair(s,m0);
}

vector<pair<ll,pair<int,int>>> kruskal(int N, vector<pair<ll,pair<int,int>>> edges) {
  sort(edges.begin(), edges.end());
  dsu uf(N);
  vector<pair<ll,pair<int,int>>> ans;
  rep(i,(int)edges.size()) {
    pair<ll,pair<int,int>> edge=edges[i];
    int u=edge.second.first;
    int v=edge.second.second;
    if(!uf.same(u,v)) {
      uf.merge(u,v);
      ans.push_back(edge);
    }
  }
  return ans;
}

vector<ll> dijkstra(vector<vector<pair<ll,int>>>& G, int s) {
  ll MAX=999999999999999999LL;
  vector<ll> dist(G.size(),MAX);
  priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
  dist[s]=0;
  pq.push(make_pair(0,s));
  while((int)pq.size()>0) {
    pair<ll,int> p= pq.top();
    pq.pop();
    ll d = p.first;
    ll v = p.second;
    if(dist[v]<d) {
      continue;
    }
    vector<pair<ll,int>> el=G[v];
    rep(i,(int)el.size()) {
      ll nd=dist[v]+el[i].first;
      if(nd<dist[el[i].second]) {
        dist[el[i].second]=nd;
        pq.push(make_pair(dist[el[i].second],el[i].second));
      }
    }
  }

  return dist;
}

vector<int> topologicalSort(vector<vector<int>>& G) {
  vector<int> result;
  vector<int> inn((int)G.size(),0);

  rep(i,(int)G.size()){
    vector<int> es=G[i];
    rep(j,(int)es.size()) {
      int e=es[j];
      inn[e]++;
    }
  }

  deque<int> deq;
  rep(i,(int)G.size()){
    if(inn[i]==0)deq.push_back(i);
  }
  while((int)deq.size()>0) {
    int v=deq.front();
    deq.pop_front();
    result.push_back(v);
    vector<int> es=G[v];
    rep(j,(int)es.size()) {
      int e=es[j];
      inn[e]--;
      if(inn[e]==0){
        deq.push_back(e);
      }
    }
  }

  return result;
}

int search_with_suffix_array(str s, str t) {
  vi sa =suffix_array(s);
  int mn=-1;
  int mx=s.length();
  while(mx-mn>1) {
    int idx=(mx+mn)/2;
    int si=sa[idx];
    str ts=s.substr(si,min(t.length(),s.length()-si));
    if(ts<t) {
      mn=idx;
    } else{
      mx=idx;
    }
  }

  if(s.substr(sa[mx],t.length())==t)return sa[mx];

  return -1;
}

vl dp;
int mod=1000000007;

ll f(int K,vi& X) {
  if(dp[K]!=-1) {
    return dp[K];
  }
  ll tmp=0;
  rep(i,X.size()) {
    int x=X[i];
    if(K<x)break;
    tmp+=f(K-x,X);
    tmp%=mod;
  }
  dp[K]=tmp;
  return dp[K];
}

int main(){
  int K=gi();
  int N=gi();
  vi X=gia(N);
  dp=vl(K+1,-1);
  dp[0]=1;
  
  ll ans=f(K,X);
  cout << ans << endl;
}
0