結果

問題 No.997 Jumping Kangaroo
コンテスト
ユーザー theory_and_me
提出日時 2020-02-23 14:51:17
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,565 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,628 ms
コンパイル使用メモリ 177,008 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-10 01:58:19
合計ジャッジ時間 2,696 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

typedef vector<ll> arr;
typedef vector<arr> mat;

mat eye(ll n){
	mat I(n, arr(n, 0));
	REP(i, n) I[i][i] = 1;
	return I;
}

mat mul(const mat &A, const mat &B){
	mat C(A.size(), arr(B[0].size(), 0));
	REP(i, C.size()){
		REP(j, C[0].size()){
			REP(k, A[0].size()){
				C[i][j] += A[i][k]*B[k][j];
				C[i][j] %= mod;
			}
		}
	}
	return C;
}

mat matpow(const mat &A, ll k){
	mat res = eye(A.size());
	mat tmp = A;
	REP(i, 64){ // 64より大きい値にするとバグるので注意．long long が64バイトで表現されていることに依存する．65とかでも一見まともに動くがバグってる．
		if(k>>i&1) res = mul(res, tmp);
		tmp = mul(tmp, tmp);
	}
	return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N, W, K;
    cin >> N >> W >> K;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];

    vector<ll> T(2*W+1, 0);
    T[0] = 1;
    REP(i, 2*W+1){
    	REP(j, N){
    		if(i+A[j]<=2*W){
    			T[i+A[j]] += T[i];
    			T[i+A[j]] %= mod;
    		}
    	}
    }

   	ll X = T[W];
   	ll Y = T[2*W];
   	ll Z = (Y - X*X%mod + mod)%mod;

   	mat P(2, arr(2, 0));
	P[0][0] = X;
	P[0][1] = Z;
	P[1][0] = 1;
	P[1][1] = 0;
	mat Q = matpow(P, K);
	mat R(2, arr(1, 0));
	R[0][0] = X;
	R[1][0] = 1;
	mat S = mul(Q, R);
	cout << S[1][0] << endl;
    return 0;
}
0