結果
問題 | No.8046 yukicoderの過去問 |
ユーザー | eaB17kNZp05kZGI |
提出日時 | 2020-10-08 12:24:03 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,134 bytes |
コンパイル時間 | 1,416 ms |
コンパイル使用メモリ | 170,192 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 05:53:09 |
合計ジャッジ時間 | 2,657 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
ソースコード
#include <bits/stdc++.h> using ll = long long; using namespace std; #define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++) #define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++) #define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--) #define rreps(i,n) for(int i=((int)(n));i>0;i--) #define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++) #define all(x) (x).begin(), (x).end() #define F first #define S second #define mp make_pair #define mt make_tuple #define pb push_back #define eb emplace_back string solve(bool a) { return ((a) ? "Yes" : "No"); } typedef vector<int> Vi; typedef vector<Vi> VVi; typedef pair<int , int> Pi; typedef vector<Pi> VPi; typedef vector<long long> V; typedef vector<V> VV; typedef pair<long long , long long> P; typedef vector<P> VP; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;} template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;} template <class T, class U>ostream& operator<<(ostream& os, const pair<T, U>& p) { os << "(" << p.first << "," << p.second << ")"; return os; } template <class T>ostream& operator<<(ostream& os, const vector<T>& v) { os << "{"; rep(i, v.size()) { if (i) os << ","; os << v[i]; } os << "}"; return os; } template <class T, class U>istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >>p.second ; return is; } template <class T>istream& operator>>(istream& is, vector<T>& v) { rep(i, v.size()) { is >> v[i]; } return is; } template <int MOD> class modint { private: long long val; public: constexpr modint(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; } constexpr int getmod() { return MOD;} constexpr modint operator-() const noexcept { return val ? MOD - val : 0;} constexpr modint operator+(const modint& r) const noexcept {return modint(*this) += r;} constexpr modint operator-(const modint& r) const noexcept {return modint(*this) -= r;} constexpr modint operator*(const modint& r) const noexcept {return modint(*this) *= r;} constexpr modint operator/(const modint& r) const noexcept {return modint(*this) /= r;} constexpr modint& operator+=(const modint& r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr modint& operator-=(const modint& r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr modint& operator*=(const modint& r) noexcept { val = val * r.val % MOD; return *this; } constexpr modint& operator/=(const modint& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator==(const modint& r) const noexcept {return this->val == r.val;} constexpr bool operator!=(const modint& r) const noexcept {return this->val != r.val;} constexpr bool operator<(const modint& r) const noexcept {return this->val < r.val;} constexpr bool operator>(const modint& r) const noexcept {return this->val > r.val;} constexpr bool operator<=(const modint& r) const noexcept {return this->val < r.val or this->val == r.val;} constexpr bool operator>=(const modint& r) const noexcept {return this->val > r.val or this->val == r.val;} friend constexpr istream& operator>>(istream& is,modint<MOD>& x) noexcept { ll t; is >> t; x=modint(t); return is; } friend constexpr ostream& operator<<(ostream& os,const modint<MOD>& x) noexcept {return os << x.val;} friend constexpr modint<MOD> modpow(const modint<MOD>& a,long long n) noexcept { if (n == 0) return 1; auto t = modpow(a, n / 2); t = t * t; if (n & 1) t = t * a; return t; } }; const long long INFLL = 1LL<<60; const int INF = 1<<30; const double PI=acos(-1); int main(){ int k,n; int ans=0; cin >>k>>n; Vi x(n); cin>>x; vector<modint<1000000007>>dp(k+1,0LL); dp[0]=1LL; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i+x[i]>=k){ break; } dp[i+x[j]]+=dp[i]; } } cout<<dp[k]<<endl; }