結果

問題 No.1039 Project Euler でやれ
ユーザー LayCurseLayCurse
提出日時 2020-04-24 23:15:18
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 20 ms / 2,000 ms
コード長 13,029 bytes
コンパイル時間 3,437 ms
コンパイル使用メモリ 250,632 KB
実行使用メモリ 26,580 KB
最終ジャッジ日時 2024-04-25 15:51:46
合計ジャッジ時間 4,371 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
18,872 KB
testcase_01 AC 15 ms
21,244 KB
testcase_02 AC 17 ms
25,984 KB
testcase_03 AC 20 ms
25,596 KB
testcase_04 AC 20 ms
26,580 KB
testcase_05 AC 19 ms
26,232 KB
testcase_06 AC 16 ms
22,000 KB
testcase_07 AC 10 ms
18,984 KB
testcase_08 AC 12 ms
19,348 KB
testcase_09 AC 15 ms
20,708 KB
testcase_10 AC 10 ms
19,256 KB
testcase_11 AC 16 ms
22,048 KB
testcase_12 AC 11 ms
18,136 KB
testcase_13 AC 9 ms
18,688 KB
testcase_14 AC 14 ms
21,912 KB
testcase_15 AC 16 ms
21,756 KB
testcase_16 AC 10 ms
20,128 KB
testcase_17 AC 9 ms
17,108 KB
testcase_18 AC 10 ms
18,772 KB
testcase_19 AC 10 ms
17,096 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
In member function 'T Comb<T>::fac(int) [with T = Modint]',
    inlined from 'int main()' at main.cpp:630:14:
main.cpp:396:18: warning: 'c.Comb<Modint>::factri' may be used uninitialized [-Wmaybe-uninitialized]
  396 |     return factri[k];
      |            ~~~~~~^
main.cpp: In function 'int main()':
main.cpp:621:16: note: 'c.Comb<Modint>::factri' was declared here
  621 |   Comb<Modint> c;
      |                ^

ソースコード

diff # 

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define MD (1000000007U)
void *wmem;
char memarr[96000000];
template<class S, class T> inline S min_L(S a,T b){
  return a<=b?a:b;
}
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  (*arr)=(T*)(*mem);
  (*mem)=((*arr)+x);
}
struct Modint{
  unsigned val;
  Modint(){
    val=0;
  }
  Modint(int a){
    val = ord(a);
  }
  Modint(unsigned a){
    val = ord(a);
  }
  Modint(long long a){
    val = ord(a);
  }
  Modint(unsigned long long a){
    val = ord(a);
  }
  inline unsigned ord(unsigned a){
    return a%MD;
  }
  inline unsigned ord(int a){
    a %= (int)MD;
    if(a < 0){
      a += MD;
    }
    return a;
  }
  inline unsigned ord(unsigned long long a){
    return a%MD;
  }
  inline unsigned ord(long long a){
    a %= (int)MD;
    if(a < 0){
      a += MD;
    }
    return a;
  }
  inline unsigned get(){
    return val;
  }
  inline Modint &operator+=(Modint a){
    val += a.val;
    if(val >= MD){
      val -= MD;
    }
    return *this;
  }
  inline Modint &operator-=(Modint a){
    if(val < a.val){
      val = val + MD - a.val;
    }
    else{
      val -= a.val;
    }
    return *this;
  }
  inline Modint &operator*=(Modint a){
    val = ((unsigned long long)val*a.val)%MD;
    return *this;
  }
  inline Modint &operator/=(Modint a){
    return *this *= a.inverse();
  }
  inline Modint operator+(Modint a){
    return Modint(*this)+=a;
  }
  inline Modint operator-(Modint a){
    return Modint(*this)-=a;
  }
  inline Modint operator*(Modint a){
    return Modint(*this)*=a;
  }
  inline Modint operator/(Modint a){
    return Modint(*this)/=a;
  }
  inline Modint operator+(int a){
    return Modint(*this)+=Modint(a);
  }
  inline Modint operator-(int a){
    return Modint(*this)-=Modint(a);
  }
  inline Modint operator*(int a){
    return Modint(*this)*=Modint(a);
  }
  inline Modint operator/(int a){
    return Modint(*this)/=Modint(a);
  }
  inline Modint operator+(long long a){
    return Modint(*this)+=Modint(a);
  }
  inline Modint operator-(long long a){
    return Modint(*this)-=Modint(a);
  }
  inline Modint operator*(long long a){
    return Modint(*this)*=Modint(a);
  }
  inline Modint operator/(long long a){
    return Modint(*this)/=Modint(a);
  }
  inline Modint operator-(void){
    Modint res;
    if(val){
      res.val=MD-val;
    }
    else{
      res.val=0;
    }
    return res;
  }
  inline operator bool(void){
    return val!=0;
  }
  inline operator int(void){
    return get();
  }
  inline operator long long(void){
    return get();
  }
  inline Modint inverse(){
    int a = val;
    int b = MD;
    int u = 1;
    int v = 0;
    int t;
    Modint res;
    while(b){
      t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    if(u < 0){
      u += MD;
    }
    res.val = u;
    return res;
  }
  inline Modint pw(unsigned long long b){
    Modint a(*this);
    Modint res;
    res.val = 1;
    while(b){
      if(b&1){
        res *= a;
      }
      b >>= 1;
      a *= a;
    }
    return res;
  }
  inline bool operator==(int a){
    return ord(a)==val;
  }
  inline bool operator!=(int a){
    return ord(a)!=val;
  }
}
;
inline Modint operator+(int a, Modint b){
  return Modint(a)+=b;
}
inline Modint operator-(int a, Modint b){
  return Modint(a)-=b;
}
inline Modint operator*(int a, Modint b){
  return Modint(a)*=b;
}
inline Modint operator/(int a, Modint b){
  return Modint(a)/=b;
}
inline Modint operator+(long long a, Modint b){
  return Modint(a)+=b;
}
inline Modint operator-(long long a, Modint b){
  return Modint(a)-=b;
}
inline Modint operator*(long long a, Modint b){
  return Modint(a)*=b;
}
inline Modint operator/(long long a, Modint b){
  return Modint(a)/=b;
}
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(Modint x){
  int i;
  i = (int)x;
  wt_L(i);
}
template<class T> int Factor_L(T N, T fac[], int fs[]){
  T i;
  int sz = 0;
  if(N%2==0){
    fac[sz] = 2;
    fs[sz] = 1;
    N /= 2;
    while(N%2==0){
      N /= 2;
      fs[sz]++;
    }
    sz++;
  }
  for(i=3;i*i<=N;i+=2){
    if(N%i==0){
      fac[sz] = i;
      fs[sz] = 1;
      N /= i;
      while(N%i==0){
        N /= i;
        fs[sz]++;
      }
      sz++;
    }
  }
  if(N > 1){
    fac[sz] = N;
    fs[sz] = 1;
    sz++;
  }
  return sz;
}
template<class T, class S> inline T pow_L(T a, S b){
  T res = 1;
  res = 1;
  for(;;){
    if(b&1){
      res *= a;
    }
    b >>= 1;
    if(b==0){
      break;
    }
    a *= a;
  }
  return res;
}
inline double pow_L(double a, double b){
  return pow(a,b);
}
template<class S, class T> inline S chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
template<class T> struct Comb{
  int mem_fact;
  T *factri;
  T *ifactri;
  Comb(){
    mem_fact = 0;
  }
  inline void expand_fact(int k){
    if(k <= mem_fact){
      return;
    }
    chmax(k, 2* mem_fact);
    if(mem_fact == 0){
      int i;
      factri = (T*)malloc(k * sizeof(T));
      ifactri = (T*)malloc(k * sizeof(T));
      factri[0] = 1;
      for(i=(1);i<(k);i++){
        factri[i] = i * factri[i-1];
      }
      ifactri[k-1] = 1 / factri[k-1];
      for(i=(k-1)-1;i>=(0);i--){
        ifactri[i] = (i+1) * ifactri[i+1];
      }
    }
    else{
      int i;
      factri = (T*)realloc(factri, k * sizeof(T));
      ifactri = (T*)realloc(ifactri, k * sizeof(T));
      for(i=(mem_fact);i<(k);i++){
        factri[i] = i * factri[i-1];
      }
      ifactri[k-1] = 1 / factri[k-1];
      for(i=(k-1)-1;i>=(mem_fact);i--){
        ifactri[i] = (i+1) * ifactri[i+1];
      }
    }
    mem_fact = k;
  }
  inline T fac(int k){
    if(mem_fact < k+1){
      expand_fact(k+1);
    }
    return factri[k];
  }
  inline T ifac(int k){
    if(mem_fact < k+1){
      expand_fact(k+1);
    }
    return ifactri[k];
  }
  inline T C(int a, int b){
    if(b < 0 || b > a){
      return 0;
    }
    if(mem_fact < a+1){
      expand_fact(a+1);
    }
    return factri[a] * ifactri[b] * ifactri[a-b];
  }
  inline T P(int a, int b){
    if(b < 0 || b > a){
      return 0;
    }
    if(mem_fact < a+1){
      expand_fact(a+1);
    }
    return factri[a] * ifactri[a-b];
  }
  inline T H(int a, int b){
    if(a==0 && b==0){
      return 1;
    }
    if(a <= 0 || b < 0){
      return 0;
    }
    if(mem_fact < a+b){
      expand_fact(a+b);
    }
    return C(a+b-1, b);
  }
  inline T Multinomial(int sz, int a[]){
    int i;
    int s = 0;
    T res;
    for(i=(0);i<(sz);i++){
      s += a[i];
    }
    if(mem_fact < s+1){
      expand_fact(s+1);
    }
    res = factri[s];
    for(i=(0);i<(sz);i++){
      res *= ifactri[a[i]];
    }
    return 1;
  }
  inline T Multinomial(int a){
    return 1;
  }
  inline T Multinomial(int a, int b){
    if(mem_fact < a+b+1){
      expand_fact(a+b+1);
    }
    return factri[a+b] * ifactri[a] * ifactri[b];
  }
  inline T Multinomial(int a, int b, int c){
    if(mem_fact < a+b+c+1){
      expand_fact(a+b+c+1);
    }
    return factri[a+b+c] * ifactri[a] * ifactri[b] * ifactri[c];
  }
  inline T Multinomial(int a, int b, int c, int d){
    if(mem_fact < a+b+c+d+1){
      expand_fact(a+b+c+d+1);
    }
    return factri[a+b+c+d] * ifactri[a] * ifactri[b] * ifactri[c] * ifactri[d];
  }
  inline T Catalan(int n){
    if(n < 0){
      return 0;
    }
    if(mem_fact < 2*n+1){
      expand_fact(2*n+1);
    }
    return factri[2*n] * ifactri[n] * ifactri[n+1];
  }
  inline T C_s(long long a, long long b){
    long long i;
    T res;
    if(b < 0 || b > a){
      return 0;
    }
    if(b > a - b){
      b = a - b;
    }
    res = 1;
    for(i=(0);i<(b);i++){
      res *= a - i;
      res /= i + 1;
    }
    return res;
  }
  inline T P_s(long long a, long long b){
    long long i;
    T res;
    if(b < 0 || b > a){
      return 0;
    }
    res = 1;
    for(i=(0);i<(b);i++){
      res *= a - i;
    }
    return res;
  }
  inline T per_s(long long n, long long k){
    T d;
    int m;
    if(n < 0 || k < 0){
      return 0;
    }
    if(n == k  &&  k == 0){
      return 1;
    }
    if(n == 0 || k == 0){
      return 0;
    }
    if(k==1){
      return 1;
    }
    if(k==2){
      d = n / 2;
      return d;
    }
    if(k==3){
      d = (n-1) / 6;
      m = (n-1) % 6;
      if(m==0){
        return 3 * d * d + d;
      }
      if(m==1){
        return 3 * d * d + 2 * d;
      }
      if(m==2){
        return 3 * d * d + 3 * d + 1;
      }
      if(m==3){
        return 3 * d * d + 4 * d + 1;
      }
      if(m==4){
        return 3 * d * d + 5 * d + 2;
      }
      if(m==5){
        return 3 * d * d + 6 * d + 3;
      }
    }
    assert(0 && "per_s should be k <= 3");
    return -1;
  }
}
;
int M;
int fs;
int f[30];
int fn[30];
int p;
int n[30];
int k[30];
Modint arr[30][100000];
int sz[30];
int cur;
void solve(int dep, int prem, int mx){
  long long m;
  int i;
  int j;
  Modint res;
  Modint t1;
  Modint t2;
  Modint t3;
  Modint pp;
  if(prem==0){
    res = 1;
    pp = p;
    for(i=(0);i<(dep);i++){
      t1 =(pow_L(pp,((n[i] - 1) * k[i] * k[i])));
      t2 = t3 = 1;
      for(j=(0);j<(k[i]);j++){
        t2 *= ((pow_L(p,k[i]))) - ((pow_L(p,j)));
      }
      for(j=(0);j<(dep);j++){
        if(j!=i){
          t3 *=(pow_L(p,(min_L(n[i], n[j])* k[j] )));
        }
      }
      (t3 = pow_L(t3,k[i]));
      res *= t1 * t2 * t3;
    }
    arr[cur][sz[cur]++] = res;
  }
  chmin(mx, prem);
  for(i=(1);i<(mx+1);i++){
    for(j=1;;j++){
      if(i*j > prem){
        break;
      }
      n[dep] = i;
      k[dep] = j;
      solve(dep+1, prem-i*j, i-1);
    }
  }
}
Modint fct;
Modint solve2(int dep, Modint now){
  int i;
  Modint res = 0;
  if(dep==fs){
    res += fct / now;
    return res;
  }
  for(i=(0);i<(sz[dep]);i++){
    res += solve2(dep+1, now * arr[dep][i]);
  }
  return res;
}
int main(){
  int i;
  wmem = memarr;
  Modint res;
  Comb<Modint> c;
  rd(M);
  assert(1 <= M  &&  M <= 1000000);
  fs =Factor_L(M, f, fn);
  for(i=(0);i<(fs);i++){
    p = f[i];
    cur = i;
    solve(0, fn[i], fn[i]);
  }
  fct = c.fac(M);
  res = solve2(0, 1);
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200419-1

// --- original code ---
// int M;
// int fs, f[30], fn[30];
// 
// int p, n[30], k[30];
// Modint arr[30][100000]; int sz[30], cur;
// 
// void solve(int dep, int prem, int mx){
//   ll m;
//   int i, j;
//   Modint res, t1, t2, t3, pp;
// 
//   if(prem==0){
//     res = 1;
//     pp = p;
//     rep(i,dep){
//       t1 = pp ** ((n[i] - 1) * k[i] * k[i]);
//       t2 = t3 = 1;
//       rep(j,k[i]) t2 *= (p ** k[i]) - (p ** j);
//       rep(j,dep) if(j!=i) t3 *= p ** ( min(n[i], n[j]) * k[j] );
//       t3 **= k[i];
//       res *= t1 * t2 * t3;
//     }
// //    rep(i,dep) wt(i, n[i], k[i]);
//     arr[cur][sz[cur]++] = res;
//   }
// 
//   mx <?= prem;
//   rep(i,1,mx+1){
//     for(j=1;;j++){
//       if(i*j > prem) break;
//       n[dep] = i;
//       k[dep] = j;
//       solve(dep+1, prem-i*j, i-1);
//     }
//   }
// }
// 
// Modint fct;
// Modint solve2(int dep, Modint now){
//   Modint res = 0;
//   if(dep==fs){
//     res += fct / now;
//     return res;
//   }
//   rep(i,sz[dep]) res += solve2(dep+1, now * arr[dep][i]);
//   return res;
// }
// 
// {
//   Modint res;
//   Comb<Modint> c;
//   rd(M);
//   assert(1 <= M <= 1d6);
// 
//   fs = Factor(M, f, fn);
//   rep(i,fs){
//     p = f[i];
//     cur = i;
//     solve(0, fn[i], fn[i]);
//   }
// 
//   fct = c.fac(M);
//   res = solve2(0, 1);
// 
//   wt(res);
// }
0