結果

問題 No.214 素数サイコロと合成数サイコロ (3-Medium)
コンテスト
ユーザー lumc_
提出日時 2018-09-12 13:25:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,814 ms / 3,000 ms
コード長 5,217 bytes
コンパイル時間 1,736 ms
コンパイル使用メモリ 175,408 KB
実行使用メモリ 9,956 KB
最終ジャッジ日時 2024-06-26 20:30:48
合計ジャッジ時間 8,491 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

/// --- ModInt Library {{{ ///
template < ll mod = (ll) 1e9 + 7 >
struct ModInt {
  static ll extgcd(ll a, ll b, ll &x, ll &y) {
    ll d;
    return b == 0 ? (x = 1, y = 0, a)
      : (d = extgcd(b, a % b, y, x), y -= a / b * x, d);
  }
  static ll modinv(ll a) {
    ll x = 0, y = 0;
    extgcd(a, mod, x, y);
    return (x + mod) % mod;
  }
  ll val;
  constexpr ModInt() : val(0) {}
  constexpr ModInt(ll val) : val((val % mod + mod) % mod) {}
  ModInt operator+(ModInt const &rhs) const { return ModInt(val + rhs.val); }
  ModInt operator-(ModInt const &rhs) const { return ModInt(val - rhs.val); }
  ModInt operator*(ModInt const &rhs) const { return ModInt(val * rhs.val); }
  ModInt operator/(ModInt const &rhs) const {
    return ModInt(val * rhs.inv().val);
  }
  ModInt &operator+=(ModInt const &rhs) {
    val = ((val + rhs.val) % mod + mod) % mod;
    return *this;
  }
  ModInt &operator-=(ModInt const &rhs) {
    val = ((val - rhs.val) % mod + mod) % mod;
    return *this;
  }
  ModInt &operator*=(ModInt const &rhs) {
    val = (val * rhs.val % mod + mod) % mod;
    return *this;
  }
  ModInt &operator/=(ModInt const &rhs) {
    val = (val * rhs.inv().val % mod + mod) % mod;
    return *this;
  }
  ModInt operator++(int) {
    ModInt tmp = *this;
    val = val + 1;
    if(val >= mod) val = 0;
    return tmp;
  }
  ModInt operator--(int) {
    ModInt tmp = *this;
    val = val == 0 ? mod - 1 : val - 1;
    return tmp;
  }
  ModInt &operator++() {
    val = val + 1;
    if(val >= mod) val = 0;
    return *this;
  }
  ModInt &operator--() {
    val = val == 0 ? mod - 1 : val - 1;
    return *this;
  }
  ModInt operator-() const { return ModInt(-val); }
  template < typename T >
    ModInt operator+(T const &rhs) const {
      return ModInt(val + rhs % mod);
    }
  template < typename T >
    ModInt operator-(T const &rhs) const {
      return ModInt(val - rhs % mod);
    }
  template < typename T >
    ModInt operator*(T const &rhs) const {
      return ModInt(val * (rhs % mod));
    }
  template < typename T >
    ModInt operator/(T const &rhs) const {
      return ModInt(val * modinv(rhs));
    }
  template < typename T >
    ModInt &operator+=(T const &rhs) {
      val = ((val + rhs % mod) % mod + mod) % mod;
      return *this;
    }
  template < typename T >
    ModInt &operator-=(T const &rhs) {
      val = ((val - rhs % mod) % mod + mod) % mod;
      return *this;
    }
  template < typename T >
    ModInt &operator*=(T const &rhs) {
      val = (val * (rhs % mod) % mod + mod) % mod;
      return *this;
    }
  template < typename T >
    ModInt &operator/=(T const &rhs) {
      val = (val * modinv(rhs, mod) % mod + mod) % mod;
      return *this;
    }
  ModInt inv() const { return ModInt(modinv(val)); }
  friend ostream &operator<<(ostream &os, ModInt const &mv) {
    os << mv.val;
    return os;
  }
  friend constexpr ModInt operator+(ll a, ModInt const &mv) {
    return ModInt(a % mod + mv.val);
  }
  friend constexpr ModInt operator-(ll a, ModInt const &mv) {
    return ModInt(a % mod - mv.val);
  }
  friend constexpr ModInt operator*(ll a, ModInt const &mv) {
    return ModInt(a % mod * mv.val);
  }
  friend constexpr ModInt operator/(ll a, ModInt const &mv) {
    return ModInt(a % mod * mv.inv().val);
  }
};
/// }}}--- ///

using Int = ModInt<>;

template < class T >
vector< T > kitamasa(const vector< T > &c, const vector< T > &u,
    const vector< T > &v) {
  int k = c.size();
  vector< T > r(2 * k - 1);
  for(int i = 0; i < k; i++)
    for(int j = 0; j < k; j++) r[i + j] += u[i] * v[j];
  for(int i = 2 * k - 2; i >= k; i--)
    for(int j = 0; j < k; j++) r[i - k + j] += r[i] * c[j];
  r.resize(k);
  return r;
}

int P[] = {2,3,5,7,11,13};
int C[] = {4,6,8,9,10,12};
const int PS = 6;

const int N = 1e5;
const int K = 1250 + 10; // 13P + 12C

const int PN = 50;

Int dpP[PS + 1][PN + 1][K];
Int dpC[PS + 1][PN + 1][K];

vector<Int> dp2(K);

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  ll n, p, c;
  cin >> n >> p >> c;
  dpP[0][0][0] = 1;
  dpC[0][0][0] = 1;

  for(int i = 1; i <= PS; i++) {
    for(int j = 0; j <= p; j++) {
      for(int k = 0; k <= p; k++) {
        for(int l = 0; l < K; l++) {
          if(k-j>=0 && l - P[i-1]*j >= 0) dpP[i][k][l] += dpP[i-1][k-j][l - P[i-1] * j];
        }
      }
    }
  }
  for(int i = 1; i <= PS; i++) {
    for(int j = 0; j <= c; j++) {
      for(int k = 0; k <= c; k++) {
        for(int l = 0; l < K; l++) {
          if(k-j>=0 && l - C[i-1]*j >= 0) dpC[i][k][l] += dpC[i-1][k-j][l - C[i-1] * j];
        }
      }
    }
  }

  for(int i = 0; i < K; i++){
    for(int j = 0; j < K; j++) {
      if(i + j < K) dp2[i + j] += dpP[PS][p][i] * dpC[PS][c][j];
    }
  }
  reverse(begin(dp2), end(dp2));
  dp2.pop_back();

  // aa(i) = a(i+K-2) とする
  // aa(n) = a(n+K-2)

  vector<Int> r(K-1, 0); r[0] = 1;
  vector<Int> t(K-1, 0); t[1] = 1;

  ll tn = n+K-2;
  while(tn) {
    if(tn&1) r = kitamasa(dp2, r, t);
    t = kitamasa(dp2, t, t);
    tn >>= 1;
  }
  Int ans = 0;
  for(int i = 0; i < K-1; i++) ans += r[i]; // a[i] = 1 としてやるといい

  cout << ans << endl;
  return 0;
}
0