結果
| 問題 |
No.997 Jumping Kangaroo
|
| コンテスト | |
| ユーザー |
 jell
|
| 提出日時 | 2020-03-16 17:10:08 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 9 ms / 2,000 ms |
| コード長 | 9,490 bytes |
| コンパイル時間 | 1,979 ms |
| コンパイル使用メモリ | 122,648 KB |
| 最終ジャッジ日時 | 2025-01-09 07:22:50 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 |
コンパイルメッセージ
main.cpp:206:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
206 | main()
| ^~~~
ソースコード
#include <iostream>
#include <vector>
#include <bitset>
#include <functional>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>
using namespace std;
template <class T> void chmax(T &x, T y) {if(x<y) x=y;}
template <class T> void chmin(T &x, T y) {if(x>y) x=y;}
#ifndef Modint_hpp
#define Modint_hpp
#include <cassert>
#include <iostream>
template <int mod>
class modint
{
int val;
public:
constexpr modint() noexcept : val{0} {}
constexpr modint(long long x) noexcept : val((x %= mod) < 0 ? mod + x : x) {}
constexpr long long value() const noexcept { return val; }
constexpr modint operator++(int) noexcept { modint t = *this; return ++val, t; }
constexpr modint operator--(int) noexcept { modint t = *this; return --val, t; }
constexpr modint &operator++() noexcept { return ++val, *this; }
constexpr modint &operator--() noexcept { return --val, *this; }
constexpr modint operator-() const noexcept { return modint(-val); }
constexpr modint &operator+=(const modint &other) noexcept { return (val += other.val) < mod ? 0 : val -= mod, *this; }
constexpr modint &operator-=(const modint &other) noexcept { return (val += mod - other.val) < mod ? 0 : val -= mod, *this; }
constexpr modint &operator*=(const modint &other) noexcept { return val = (long long)val * other.val % mod, *this; }
constexpr modint &operator/=(const modint &other) noexcept { return *this *= inverse(other); }
constexpr modint operator+(const modint &other) const noexcept { return modint(*this) += other; }
constexpr modint operator-(const modint &other) const noexcept { return modint(*this) -= other; }
constexpr modint operator*(const modint &other) const noexcept { return modint(*this) *= other; }
constexpr modint operator/(const modint &other) const noexcept { return modint(*this) /= other; }
constexpr bool operator==(const modint &other) const noexcept { return val == other.val; }
constexpr bool operator!=(const modint &other) const noexcept { return val != other.val; }
constexpr bool operator!() const noexcept { return !val; }
friend constexpr modint operator+(long long x, modint y) noexcept { return modint(x) + y; }
friend constexpr modint operator-(long long x, modint y) noexcept { return modint(x) - y; }
friend constexpr modint operator*(long long x, modint y) noexcept { return modint(x) * y; }
friend constexpr modint operator/(long long x, modint y) noexcept { return modint(x) / y; }
static constexpr modint inverse(const modint &other) noexcept
{
assert(other != 0);
int a{mod}, b{other.val}, u{}, v{1}, t{};
while(b) t = a / b, a ^= b ^= (a -= t * b) ^= b, u ^= v ^= (u -= t * v) ^= v;
return {u};
}
static constexpr modint pow(modint other, long long e) noexcept
{
if(e < 0) e = e % (mod - 1) + mod - 1;
modint res{1};
while(e) { if(e & 1) res *= other; other *= other, e >>= 1; }
return res;
}
friend std::ostream &operator<<(std::ostream &os, const modint &other) noexcept { return os << other.val; }
friend std::istream &operator>>(std::istream &is, modint &other) noexcept { long long val; other = {(is >> val, val)}; return is; }
}; // class modint
template <>
class modint<2>
{
bool val;
public:
constexpr modint(bool x = false) noexcept : val{x} {}
constexpr modint(int x) noexcept : val(x & 1) {}
constexpr modint(long long x) noexcept : val(x & 1) {}
constexpr operator bool() const noexcept { return val; }
constexpr bool value() const noexcept { return val; }
constexpr modint &operator+=(const modint &other) noexcept { return val ^= other.val, *this; }
constexpr modint &operator-=(const modint &other) noexcept { return val ^= other.val, *this; }
constexpr modint &operator*=(const modint &other) noexcept { return val &= other.val, *this; }
constexpr modint &operator/=(const modint &other) noexcept { assert(other.val); return *this; }
constexpr modint operator!() const noexcept { return !val; }
constexpr modint operator-() const noexcept { return *this; }
constexpr modint operator+(const modint &other) const noexcept { return val != other.val; }
constexpr modint operator-(const modint &other) const noexcept { return val != other.val; }
constexpr modint operator*(const modint &other) const noexcept { return val && other.val; }
constexpr modint operator/(const modint &other) const noexcept { assert(other.val); return *this; }
constexpr bool operator==(const modint &other) const noexcept { return val == other.val; }
constexpr bool operator!=(const modint &other) const noexcept { return val != other.val; }
friend constexpr modint operator+(long long x, modint y) noexcept { return x & 1 ? !y : y; }
friend constexpr modint operator-(long long x, modint y) noexcept { return x & 1 ? !y : y; }
friend constexpr modint operator*(long long x, modint y) noexcept { return x & 1 ? y : modint<2>{0}; }
friend constexpr modint operator/(long long x, modint y) noexcept { assert(y.val); return x & 1 ? y : modint<2>{0}; }
friend std::ostream &operator<<(std::ostream &os, const modint &other) noexcept { return os << other.val; }
friend std::istream &operator>>(std::istream &is, modint &other) noexcept { long long val; other.val = (is >> val, val & 1); return is; }
}; // class modint specialization
#endif // Modint_hpp
#include <cassert>
#include <iostream>
#include <valarray>
template <class Ring>
class matrix
{
struct identity_wrapper
{
template <bool arith, class = void>
struct check { static Ring identity() { return Ring::identity(); } };
template <class void_t>
struct check<true, void_t> { static Ring identity() { return 1; } };
operator Ring() { return check<std::is_arithmetic<Ring>::value>::identity(); }
};
using row_type = std::valarray<Ring>;
using data_type = std::valarray<row_type>;
data_type data;
friend std::istream &operator>>(std::istream &is, matrix &mat)
{
for(size_t i = 0; i != mat.rows(); ++i)
for(size_t j = 0; j != mat.columns(); ++j)
is >> mat[i][j];
return is;
}
friend std::ostream &operator<<(std::ostream &os, const matrix &mat)
{
for(size_t i = 0; i != mat.rows(); ++i)
{
if(i) os << "\n";
for(size_t j = 0; j != mat.columns(); ++j) os << (j ? " " : "") << mat[i][j];
}
return os;
}
friend matrix transpose(const matrix &mat)
{
matrix res(mat.columns(), mat.rows());
for(size_t i{mat.columns()}; i--;)
for(size_t j{mat.rows()}; j--;)
res[i][j] = mat[j][i];
return res;
}
public:
explicit matrix(size_t _n = 1) : matrix(_n, _n) {}
matrix(size_t _r, size_t _c) : data(row_type(_c), _r) {}
matrix(const data_type &_data) : data(_data) {}
size_t rows() const { return data.size(); }
size_t columns() const { return data[0].size(); }
row_type &operator[](const size_t i) { assert(i < data.size()); return data[i]; }
const row_type &operator[](const size_t i) const { assert(i < data.size()); return data[i]; }
matrix operator-() const { return {-data}; }
matrix &operator+=(const matrix &rhs) { data += rhs.data; return *this; }
matrix &operator-=(const matrix &rhs) { data -= rhs.data; return *this; }
matrix &operator*=(matrix rhs) noexcept
{
assert(columns() == rhs.rows());
rhs = transpose(rhs);
for(row_type &row : data)
{
const row_type copied{row};
for(size_t j{rhs.rows()}; j--;) row[j] = (copied * rhs[j]).sum();
}
return *this;
}
matrix operator+(const matrix &rhs) const { return matrix{*this} += rhs; }
matrix operator-(const matrix &rhs) const { return matrix{*this} -= rhs; }
matrix operator*(const matrix &rhs) const { return matrix{*this} *= rhs; }
friend row_type &operator*=(row_type &lhs, const matrix &rhs) { return lhs = lhs * rhs; }
friend row_type operator*(row_type &lhs, const matrix &rhs)
{
assert(lhs.size() == rhs.rows());
row_type res(rhs.columns());
for(size_t k{lhs.size()}; k--;)
for(size_t j{rhs.columns()}; j--;)
res[j] += lhs[k] * rhs[k][j];
return res;
}
static matrix identity(const size_t _n)
{
matrix ide(_n);
for(size_t i{_n}; i--;) ide[i][i] = identity_wrapper();
return ide;
}
friend matrix pow(matrix mat, unsigned long long exp)
{
matrix res{identity(mat.rows())};
for(assert(mat.rows() == mat.columns()); exp; mat *= mat, exp >>= 1) if(exp & 1) res *= mat;
return res;
}
}; // class matrix
main()
{
ios::sync_with_stdio(false), cin.tie(nullptr);
using mint=modint<1000000007>;
int n,w; long long k; cin>>n>>w>>k;
vector<int> a(n);
for(auto &e:a) cin>>e;
mint dp[200];
dp[0]=1;
for(int i=0;i<100;++i)
{
for(int e:a)
{
dp[i+e]+=dp[i];
}
}
mint p=dp[w];
mint q=dp[w*2]-p*p;
matrix<mint> res({{1,0},{0,1}});
matrix<mint> coef({{p,q},{1,0}});
while(k)
{
if(k&1)
{
res*=coef;
}
coef*=coef;
k>>=1;
}
cout << res[1][0]*p+res[1][1] << "\n";
}