結果

問題 No.997 Jumping Kangaroo
ユーザー monkukui2monkukui2
提出日時 2020-02-11 22:15:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 5,189 bytes
コンパイル時間 1,154 ms
コンパイル使用メモリ 109,480 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-04 01:59:03
合計ジャッジ時間 2,061 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */
template<typename T,T MOD = 1000000007>
struct Mint{
    T v;
    Mint():v(0){}
    Mint(signed v):v(v){}
    Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

    Mint pow(long long k){
        Mint res(1),tmp(v);
        while(k){
            if(k&1) res*=tmp;
            tmp*=tmp;
            k>>=1;
        }
        return res;
    }

    static Mint add_identity(){return Mint(0);}
    static Mint mul_identity(){return Mint(1);}

    Mint inv(){return pow(MOD-2);}

    Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
    Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
    Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
    Mint& operator/=(Mint a){return (*this)*=a.inv();}

    Mint operator+(Mint a) const{return Mint(v)+=a;};
    Mint operator-(Mint a) const{return Mint(v)-=a;};
    Mint operator*(Mint a) const{return Mint(v)*=a;};
    Mint operator/(Mint a) const{return Mint(v)/=a;};

    Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

    bool operator==(const Mint a)const{return v==a.v;}
    bool operator!=(const Mint a)const{return v!=a.v;}
    bool operator <(const Mint a)const{return v <a.v;}

    static Mint comb(long long n,int k){
        Mint res(1);
        for(int i=0;i<k;i++){
            res*=Mint(n-i);
            res/=Mint(i+1);
        }
        return res;
    }
};

// 逆元を求める. a と m は互いに素であることが要請される.
long long modinv(long long a, long long m) {
  long long b = m, u = 1, v = 0;
  while(b){
    long long t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m; 
  if (u < 0) u += m;
  return u;
}

// before your coding, you have to write a line "math_init()"

template<typename T>
struct SquareMatrix{
    
    vector<vector<T>> dat;
    size_t N;
    SquareMatrix() = default;
    SquareMatrix(size_t N, T val = T()):N(N){
        dat = vector<vector<T>> (N, vector<T> (N));
        for(size_t i=0;i<N;i++)
            for(size_t j=0;j<N;j++)
                dat[i][j]=val;
    }
    SquareMatrix& operator=(const SquareMatrix& a){
        dat=a.dat;
        return (*this);
    }
    bool operator==(const SquareMatrix& a) const{
        return dat==a.dat;
    }

    size_t size() const{return N;};
    vector<T>& operator[](size_t k){return dat[k];};
    const vector<T>& operator[](size_t k) const {return dat[k];};

    SquareMatrix operator*(const SquareMatrix &B) const{
        SquareMatrix res(N, 0);
        for(size_t i=0;i<N;i++)
            for(size_t j=0;j<N;j++)
                for(size_t k=0;k<N;k++)
                    res[i][j]=res[i][j]+(dat[i][k]*B[k][j]);
        return res;
    }

    SquareMatrix operator+(const SquareMatrix &B) const{
        SquareMatrix res(N, 0);
        for(size_t i=0;i<N;i++)
            for(size_t j=0;j<N;j++)
                res[i][j]=dat[i][j]+B[i][j];
        return res;
    }

    SquareMatrix pow(long long n) const{
        SquareMatrix a=*this;
        SquareMatrix res(N, 0);
        for(size_t i = 0; i < N; i++) res[i][i] = 1;    
        while(n){
            if(n&1) res=res*a;      
            a=a*a;
            n>>=1;
        }
        return res;
    }
};

using modint = Mint<lint>;
modint culc_sub1(vector<lint> &a, lint w) {
  vector<modint> dp(w + 1, 0);
  dp[0] = modint(1);
  // 配る dp
  for(int i = 0; i < w; i++) {
    if(dp[0] == 0) continue;
    for(auto delta : a) {
      lint nxt = delta + i;
      if(nxt > w) continue;
      dp[nxt] += dp[i];
    }
  }

  return dp[w];
}

modint culc_sub2(vector<lint> &a, lint w) {
  vector<modint> dp(2 * w + 1, 0);
  dp[0] = 1;
  for(int i = 0; i < 2 * w; i++) {
    for(auto delta : a) {
      lint nxt = delta + i;
      if(nxt > 2 * w) continue;
      if(nxt == w) continue;
      dp[nxt] += dp[i];
    }
  }

  return dp[2 * w];
}

int main() {
  
  lint n, w, k; cin >> n >> w >> k;
  vector<lint> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  modint w1 = culc_sub1(a, w);   // 次の島へ行く通り数
  modint w2 = culc_sub2(a, w);   // 次の島を踏まずに，次の次の島へ行く通り数．

  SquareMatrix<modint> mat(2);
  mat[0][0] = w1;
  mat[0][1] = w2;
  mat[1][0] = 1;
  mat[1][1] = 0;
  if(k == 1) {
    cout << w1.v << endl;
    return 0;
  }

  mat = mat.pow(k - 1);
  cout << (w1 * mat[0][0] + mat[0][1]).v << endl;


  return 0;
}
0