結果
| 問題 |
No.997 Jumping Kangaroo
|
| コンテスト | |
| ユーザー |
 kissshot7
|
| 提出日時 | 2020-12-05 03:24:17 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 6 ms / 2,000 ms |
| コード長 | 6,574 bytes |
| コンパイル時間 | 2,560 ms |
| コンパイル使用メモリ | 177,096 KB |
| 実行使用メモリ | 7,552 KB |
| 最終ジャッジ日時 | 2024-09-15 10:19:28 |
| 合計ジャッジ時間 | 3,078 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
// const ll mod = 998244353;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;
//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
ll res = 1;
while (n) {
if (n & 1)res = res * a%m;
a = a * a%m; n >>= 1;
}
return res;
}
struct modint {
ll n;
modint() :n(0) { ; }
modint(ll m) :n(m) {
if (n >= mod)n %= mod;
else if (n < 0)n = (n%mod + mod) % mod;
}
operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
if (n == 0)return modint(1);
modint res = (a*a) ^ (n / 2);
if (n % 2)res = res * a;
return res;
}
//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
fact[0] = modint(1);
for (int i = 0; i < max_n - 1; i++) {
fact[i + 1] = fact[i] * modint(i + 1);
}
factinv[max_n - 1] = modint(1) / fact[max_n - 1];
for (int i = max_n - 2; i >= 0; i--) {
factinv[i] = factinv[i + 1] * modint(i + 1);
}
}
modint comb(int a, int b) {
if (a < 0 || b < 0 || a < b)return 0;
return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
template< class T >
struct Matrix {
std::vector< std::vector< T > > A;
Matrix() {}
Matrix(size_t n, size_t m) : A(n, std::vector< T >(m, 0)) {}
Matrix(size_t n) : A(n, std::vector< T >(n, 0)) {};
size_t height() const {
return (A.size());
}
size_t width() const {
return (A[0].size());
}
inline const std::vector< T > &operator[](int k) const {
return (A.at(k));
}
inline std::vector< T > &operator[](int k) {
return (A.at(k));
}
static Matrix I(size_t n) {
Matrix mat(n);
for (int i = 0; i < n; i++) mat[i][i] = 1;
return (mat);
}
Matrix &operator+=(const Matrix &B) {
size_t n = height(), m = width();
assert(n == B.height() && m == B.width());
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
(*this)[i][j] += B[i][j];
return (*this);
}
Matrix &operator-=(const Matrix &B) {
size_t n = height(), m = width();
assert(n == B.height() && m == B.width());
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
(*this)[i][j] -= B[i][j];
return (*this);
}
Matrix &operator*=(const Matrix &B) {
size_t n = height(), m = B.width(), p = width();
assert(p == B.height());
std::vector< std::vector< T > > C(n, std::vector< T >(m, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int k = 0; k < p; k++)
C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
A.swap(C);
return (*this);
}
Matrix operator+(const Matrix &B) const {
return (Matrix(*this) += B);
}
Matrix operator-(const Matrix &B) const {
return (Matrix(*this) -= B);
}
Matrix operator*(const Matrix &B) const {
return (Matrix(*this) *= B);
}
friend std::ostream &operator<<(std::ostream &os, Matrix &p) {
size_t n = p.height(), m = p.width();
for (int i = 0; i < n; i++) {
os << "[";
for (int j = 0; j < m; j++) {
os << p[i][j] << (j + 1 == m ? "]\n" : ",");
}
}
return (os);
}
T determinant() {
Matrix B(*this);
assert(width() == height());
T ret = 1;
for (int i = 0; i < width(); i++) {
int idx = -1;
for (int j = i; j < width(); j++) {
if (B[j][i] != 0) idx = j;
}
if (idx == -1) return (0);
if (i != idx) {
ret *= -1;
swap(B[i], B[idx]);
}
ret *= B[i][i];
T vv = B[i][i];
for (int j = 0; j < width(); j++) {
B[i][j] /= vv;
}
for (int j = i + 1; j < width(); j++) {
T a = B[j][i];
for (int k = 0; k < width(); k++) {
B[j][k] -= B[i][k] * a;
}
}
}
return (ret);
}
Matrix pow(int64_t k) const {
auto res = I(A.size());
auto M = *this;
while (k > 0) {
if (k & 1) {
res *= M;
}
M *= M;
k >>= 1;
}
return res;
}
};
modint dp1[50], dp2[100];
void solve() {
int n, w; ll k; cin >> n >> w >> k;
vec a(n); rep(i, n) cin >> a[i];
dp1[0] = 1;
rep(i, w){
rep(j, n){
if(i+a[j] <= w){
dp1[i+a[j]] += dp1[i];
}
}
}
dp2[0] = 1;
rep(i, 2*w){
rep(j, n){
if(i+a[j] == w) continue;
if(i+a[j] <= 2*w){
dp2[i+a[j]] += dp2[i];
}
}
}
Matrix<modint> mat(2);
mat[0][0] = dp1[w];
mat[0][1] = dp2[2*w];
mat[1][0] = 1;
auto res = mat.pow(k);
cout << res[0][0].n << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
//cout << fixed << setprecision(10);
//init_f();
//init();
//int t; cin >> t; rep(i, t)solve();
solve();
// stop
return 0;
}