Submission #3254895

Source Code Expand

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

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<ll, ll> llll;
typedef pair<double, double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a) int((a).size())
#define pb push_back
#define FOR(var, from, to) for (int var = (from); var <= (to); ++var)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define rep1(var, n) for (int var = 1; var <= (n); ++var)
#define repC2(vari, varj, n)               \
  for (int vari = 0; vari < (n)-1; ++vari) \
    for (int varj = vari + 1; varj < (n); ++varj)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define tr(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define found(s, e) ((s).find(e) != (s).end())
#define mset(arr, val) memset(arr, val, sizeof(arr))
#define mid(x, y) ((x) + ((y) - (x)) / 2)
#define IN(x, a, b) ((a) <= (x) && (x) <= (b))
#define cons make_pair

ll gcd(ll a, ll b) {
  while (a) swap(a, b %= a);
  return b;
}

const ll MOD = 1000000007LL;

ll ADD(ll x, ll y) { return (x + y) % MOD; }
ll SUB(ll x, ll y) { return (x - y + MOD) % MOD; }
ll MUL(ll x, ll y) { return x * y % MOD; }
ll POW(ll x, ll e) {
  ll v = 1;
  for (; e; x = MUL(x, x), e >>= 1)
    if (e & 1) v = MUL(v, x);
  return v;
}
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/
  return MUL(x, POW(y, MOD - 2));
}
// ll comb(ll n, ll k) { ll v=1; for(ll i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }

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


template <typename T>
void mat_pp(vector<vector<T>>& A) {
  int n = A.size(), m = A[0].size();
  printf("_ matrix %dx%d\n", n, m);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      printf(" %5g", (double)A[i][j]);
    }
    printf("\n");
  }
}

// assign
template <typename T>
void mat_assign(vector<vector<T>>& dest, vector<vector<T>>& src) {
  int n = src.size(), m = src[0].size();
  dest.resize(n);
  for (int i = 0; i < n; ++i) {
    dest[i] = src[i];
  }
}

template <typename T>
void mat_assign_zero(vector<vector<T>>& dest, int n, int m) {
  dest.resize(n);
  for (int i = 0; i < n; ++i) {
    dest[i].assign(m, (T)0);
  }
}

template <typename T>
void mat_assign_eye(vector<vector<T>>& dest, int n) {
  dest.resize(n);
  for (int i = 0; i < n; ++i) {
    dest[i].assign(n, (T)0);
    dest[i][i] = (T)1;
  }
}

// mul
template <typename T>
void mat_assign_mul(vector<vector<T>>& dest, vector<vector<T>>& A, vector<vector<T>>& B) {
  int an = A.size(), am = A[0].size();
  int bn = B.size(), bm = B[0].size();
  assert(am == bn);
  // vector<vector<T>> C(an, vector<T>(bm, (T)0));
  // printf("* mat mul (%d %d)x(%d %d)\n", an,am, bn,bm);
  // mat_pp(A); mat_pp(B);

  mat_assign_zero(dest, an, bm);
  for (int i = 0; i < an; ++i) {
    for (int j = 0; j < bm; ++j) {
      for (int k = 0; k < am; ++k) {
        // dest[i][j] += A[i][k] * B[k][j];
        dest[i][j] = ADD(dest[i][j], MUL(A[i][k], B[k][j]));
      }
    }
  }
  // mat_pp(dest);
}

template <typename T>
vector<vector<T>> mat_mul(vector<vector<T>>& A, vector<vector<T>>& B) {
  int an = A.size(), am = A[0].size();
  int bn = B.size(), bm = B[0].size();
  assert(am == bn);
  vector<vector<T>> C;  // (an, vector<T>(bm, (T)0));
  mat_assign_mul(C, A, B);
  return C;
}

template <typename T>
void mat_s_mul(vector<vector<T>>& A, vector<vector<T>>& B) {
  int an = A.size(), am = A[0].size();
  int bn = B.size(), bm = B[0].size();
  assert(am == bn);

  vector<vector<T>> A_copy;
  mat_assign(A_copy, A);
  mat_assign_mul(A, A_copy, B);
}

template <typename T>
void mat_s_pow2(vector<vector<T>>& A) {
  int an = A.size(), am = A[0].size();
  assert(an == am);

  vector<vector<T>> A_copy;
  mat_assign(A_copy, A);
  mat_assign_mul(A, A_copy, A_copy);
}


template <typename T>
vector<T> mat_mul(vector<vector<T>>& A, vector<T>& x) {
  int an = A.size(), am = A[0].size();
  int xn = x.size();
  assert(am == xn);
  vector<T> y(an, (T)0);
  for (int i = 0; i < an; ++i) {
    for (int k = 0; k < am; ++k) {
    //   y[i] += A[i][k] * x[k];
      y[i] = ADD(y[i], MUL(A[i][k], x[k]));
    }
  }
  return y;
}

template <typename T>
vector<vector<T>> mat_pow(vector<vector<T>>& A, long long p = 2) {  // A^p
  int an = A.size(), am = A[0].size();
  assert(an == am);
  // printf("mat pow\n");
  // mat_pp(A);
  // printf("^ %lld =\n", p);

  if (p == 0) {
    vector<vector<T>> E;
    mat_assign_eye(E, an);
    // mat_pp(E);
    return E;
  }

  vector<vector<T>> U;
  mat_assign(U, A);
  if (p == 1) {
    // mat_pp(U);
    return U;
  }

  vector<vector<T>> R;
  mat_assign_eye(R, an);

  while (p) {
    if (p % 2) {
      mat_s_mul(R, U);  // v *= u
      --p;
    } else {
      mat_s_pow2(U);  // u ^= 2
      p /= 2;
    }
  }
  // mat_pp(R);
  return R;
}


vi factorize(int M) {
  set<int> s;
  int sq = sqrt(M);
  for (int d = 1; d <= sq; ++d) {
    if (M % d == 0) {
      s.insert(d);
      s.insert(M / d);
    }
  }
  return vi(ALL(s));
}

ll solve(int N, int M) {
  vi fac = factorize(M);
  int F = fac.size();
#ifdef DEBUG
  cerr << M << fac << F << endl;
#endif

  vector<vll> A(F, vll(F, 0));
  // mat_assign_zero(A, F, F);
  for (int j = F - 1; j >= 0; --j) {
    for (int k = j; k >= 0; --k) {
      if (fac[j] % fac[k]) continue;
      // dp2[k] += dp[j]
      A[k][j] = 1;
    }
  }
  vector<vll> An = mat_pow(A, N);
  vll x(F, 0);
  x[F - 1] = 1LL;
  vll y = mat_mul(An, x);
  return y[0];
}

int main() {
  int N, M;
  cin >> N >> M;
  cout << solve(N, M) << endl;
  return 0;
}

Submission Info

Submission Time
Task D - Factorization
User naoya_t
Language C++14 (GCC 5.4.1)
Score 0
Code Size 6090 Byte
Status

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 400 0_small_1, 0_small_2, 0_small_3, 1_large_1, 1_large_2, 1_large_3, 2_large_1, 2_large_2, 3_prime_1, 3_prime_10, 3_prime_11, 3_prime_12, 3_prime_13, 3_prime_14, 3_prime_15, 3_prime_16, 3_prime_17, 3_prime_18, 3_prime_19, 3_prime_2, 3_prime_20, 3_prime_21, 3_prime_22, 3_prime_3, 3_prime_4, 3_prime_5, 3_prime_6, 3_prime_7, 3_prime_8, 3_prime_9, 4_hand_1, 4_hand_2, 4_hand_3, sample_01, sample_02, sample_03
Sample 0 / 0 sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
0_small_1 1 ms 256 KB
0_small_2 1 ms 256 KB
0_small_3 1 ms 256 KB
1_large_1 1 ms 256 KB
1_large_2 1 ms 256 KB
1_large_3 7 ms 256 KB
2_large_1 2 ms 256 KB
2_large_2 1 ms 256 KB
3_prime_1
3_prime_10
3_prime_11
3_prime_12
3_prime_13
3_prime_14
3_prime_15
3_prime_16
3_prime_17
3_prime_18
3_prime_19
3_prime_2
3_prime_20
3_prime_21
3_prime_22 4 ms 256 KB
3_prime_3 1191 ms 1796 KB
3_prime_4
3_prime_5
3_prime_6
3_prime_7
3_prime_8
3_prime_9
4_hand_1 3 ms 256 KB
4_hand_2 1 ms 256 KB
4_hand_3 1 ms 384 KB
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB
sample_03 98 ms 512 KB