結果

問題 No.214 素数サイコロと合成数サイコロ (3-Medium)
ユーザー lumc_lumc_
提出日時 2018-09-12 13:22:51
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 6,991 bytes
コンパイル時間 1,674 ms
コンパイル使用メモリ 171,948 KB
実行使用メモリ 5,512 KB
最終ジャッジ日時 2023-09-09 03:17:12
合計ジャッジ時間 3,038 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// #undef DEBUG
// #define DEBUG
// DEBUG {{{
// clang-format off
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
template<class T, class U> ostream & operator<<(ostream &o, pair<T, U> const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; }
#ifdef DEBUG
#if !defined(DEBUG_OUT)
#define DEBUG_OUT cerr
#endif
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);DEBUG_OUT<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}()
template < class T > inline void dump2D(T &d, size_t sizey, size_t sizex) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << "\t"; for(size_t j = 0; j < sizex; j++) DEBUG_OUT << d[i][j] << (j + 1 == sizex ? "" : "\t"); DEBUG_OUT << endl; } }
template < class T, class = typename iterator_traits< typename T::iterator >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { o << "{"; for(auto ite = a.begin(); ite != a.end(); ++ite) o << (ite == a.begin() ? "" : ", ") << *ite; o << "}"; return o; }
#else
#define dump(...) (42)
#define dump2D(...) (42)
template < class T, class = typename iterator_traits< typename T::iterator >::value_type, class = typename enable_if<!is_same<T, string>::value>::type > ostream &operator<<(ostream &o, const T &a) { for(auto ite = a.begin(); ite != a.end(); ++ite) o << (ite == a.begin() ? "" : " ") << *ite; return o; }
#endif
// clang-format on
// }}}

/// --- 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 = 30;

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