結果

問題 No.8046 yukicoderの過去問
コンテスト
ユーザー eaB17kNZp05kZGI
提出日時 2020-10-08 12:24:03
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 5 RE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0