結果

問題 No.502 階乗を計算するだけ
ユーザー ゆうきゆうき
提出日時 2023-10-11 15:25:34
言語 Java21
(openjdk 21)
結果
AC  
実行時間 120 ms / 1,000 ms
コード長 15,257 bytes
コンパイル時間 3,503 ms
コンパイル使用メモリ 96,448 KB
実行使用メモリ 51,028 KB
最終ジャッジ日時 2024-09-13 14:14:42
合計ジャッジ時間 8,391 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 56 ms
50,416 KB
testcase_01 AC 56 ms
49,756 KB
testcase_02 AC 55 ms
50,236 KB
testcase_03 AC 56 ms
50,200 KB
testcase_04 AC 55 ms
49,916 KB
testcase_05 AC 56 ms
50,308 KB
testcase_06 AC 56 ms
49,880 KB
testcase_07 AC 56 ms
50,308 KB
testcase_08 AC 55 ms
50,320 KB
testcase_09 AC 56 ms
50,216 KB
testcase_10 AC 55 ms
49,868 KB
testcase_11 AC 56 ms
50,340 KB
testcase_12 AC 55 ms
49,756 KB
testcase_13 AC 55 ms
50,224 KB
testcase_14 AC 55 ms
50,184 KB
testcase_15 AC 55 ms
50,392 KB
testcase_16 AC 56 ms
50,152 KB
testcase_17 AC 56 ms
50,016 KB
testcase_18 AC 56 ms
50,124 KB
testcase_19 AC 55 ms
50,316 KB
testcase_20 AC 56 ms
50,312 KB
testcase_21 AC 56 ms
49,872 KB
testcase_22 AC 74 ms
50,676 KB
testcase_23 AC 66 ms
49,892 KB
testcase_24 AC 71 ms
50,964 KB
testcase_25 AC 58 ms
50,216 KB
testcase_26 AC 77 ms
50,508 KB
testcase_27 AC 65 ms
50,380 KB
testcase_28 AC 66 ms
50,296 KB
testcase_29 AC 59 ms
50,260 KB
testcase_30 AC 71 ms
50,824 KB
testcase_31 AC 69 ms
50,956 KB
testcase_32 AC 98 ms
50,612 KB
testcase_33 AC 120 ms
50,816 KB
testcase_34 AC 118 ms
50,660 KB
testcase_35 AC 120 ms
50,952 KB
testcase_36 AC 96 ms
50,640 KB
testcase_37 AC 120 ms
50,928 KB
testcase_38 AC 90 ms
51,028 KB
testcase_39 AC 113 ms
50,944 KB
testcase_40 AC 74 ms
50,808 KB
testcase_41 AC 55 ms
50,228 KB
testcase_42 AC 55 ms
50,268 KB
testcase_43 AC 55 ms
49,980 KB
testcase_44 AC 55 ms
50,228 KB
testcase_45 AC 55 ms
49,972 KB
testcase_46 AC 55 ms
50,164 KB
testcase_47 AC 55 ms
50,244 KB
testcase_48 AC 55 ms
50,040 KB
testcase_49 AC 56 ms
50,232 KB
testcase_50 AC 55 ms
50,264 KB
testcase_51 AC 54 ms
50,256 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import static java.lang.Math.*;
import static java.util.Arrays.*;
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;
import java.util.function.*;
import java.util.stream.IntStream;

class Solver{
  long st = System.currentTimeMillis();

  long elapsed(){ return System.currentTimeMillis() -st; }

  void reset(){ st = System.currentTimeMillis(); }

  final static int infI = (1 <<30) -1;
  final static long infL = 1L <<60;
  final static long mod = (int) 1e9 +7;
  // final static long mod = 998244353;
  final static String yes = "Yes";
  final static String no = "No";

  MyReader in = new MyReader(System.in);
  MyWriter out = new MyWriter(System.out);
  MyWriter log = new MyWriter(System.err){
    @Override
    void println(Object obj){ super.println(obj == null ? "null" : obj); };

    @Override
    protected void ln(){
      super.ln();
      flush();
    };
  };
  long[] memo = {1, 682498929, 491101308, 76479948, 723816384, 67347853, 27368307, 625544428, 199888908, 888050723,
      927880474, 281863274, 661224977, 623534362, 970055531, 261384175, 195888993, 66404266, 547665832, 109838563,
      933245637, 724691727, 368925948, 268838846, 136026497, 112390913, 135498044, 217544623, 419363534, 500780548,
      668123525, 128487469, 30977140, 522049725, 309058615, 386027524, 189239124, 148528617, 940567523, 917084264,
      429277690, 996164327, 358655417, 568392357, 780072518, 462639908, 275105629, 909210595, 99199382, 703397904,
      733333339, 97830135, 608823837, 256141983, 141827977, 696628828, 637939935, 811575797, 848924691, 131772368,
      724464507, 272814771, 326159309, 456152084, 903466878, 92255682, 769795511, 373745190, 606241871, 825871994,
      957939114, 435887178, 852304035, 663307737, 375297772, 217598709, 624148346, 671734977, 624500515, 748510389,
      203191898, 423951674, 629786193, 672850561, 814362881, 823845496, 116667533, 256473217, 627655552, 245795606,
      586445753, 172114298, 193781724, 778983779, 83868974, 315103615, 965785236, 492741665, 377329025, 847549272,
      698611116
  };

  Object solve(){
    long N = in.lg();
    if (mod <= N)
      return 0;
    long ans = memo[(int) (N /10_000_000)];
    for (long i = N /10_000_000 *10_000_000 +1;i <= N;i++)
      ans = ans *i %mod;
    return ans;
    //    long n = 1;
    //    List<Long> list = new ArrayList<>();
    //    for (int i = 1;i <= 1_000_000_000;i++) {
    //      n = n *i %mod;
    //      if (i %10_000_000 == 0)
    //        list.add(n);
    //    }
    //
    //    StringBuilder ret = new StringBuilder("1");
    //    for (var a:list)
    //      ret.append(",").append(a);
    //
    //    return ret.toString();
  }

  private long keta(long n,int k){
    while (k-- > 0)
      n /= 10;

    return n %10;
  }

  long inv(long x,long mod){ return pow(x,mod -2,mod); }

  long pow(long x,long n){ return pow(x,n,mod); }

  long pow(long x,long n,long mod){
    x %= mod;
    long ret = 1;
    do {
      if ((n &1) == 1)
        ret = ret *x %mod;
      x = x *x %mod;
    } while (0 < (n >>= 1));

    return ret;
  }
}

class Prime{
  BitSet primes;
  private int[] spf;
  private long[] AInt;
  private BigInteger[] ALng;

  Prime(){ this(10_000_000); }

  Prime(int n){
    primes = new BitSet();
    primes.set(2,n +1);
    spf = Util.arrI(n +1,i -> i);

    for (int p = 2;p *p <= n;p++)
      if (primes.get(p))
        for (int nn = p *p;nn <= n;primes.clear(nn),nn += p)
          spf[nn] = p;
    AInt = new long[]{2, 7, 61};
    ALng = IntStream.of(2,325,9375,28178,450775,9780504,1795265022).mapToObj(BigInteger::valueOf)
        .toArray(nn -> new BigInteger[nn]);
  }

  boolean isPrime(long n){
    if (n < spf.length)
      return primes.get((int) n);
    if ((n &1) == 0)
      return false;
    long lsb = Long.lowestOneBit(n -1);
    if (n < 3e9) {
      long m = (n -1) /lsb;
      a:for (var a:AInt) {
        long z = pow(a,m,n);
        if (z <= 1)
          continue;
        for (long k = 1;k <= lsb;k <<= 1) {
          if (z == n -1)
            continue a;
          z = z *z %n;
        }
        return false;
      }
    } else {
      BigInteger bn = BigInteger.valueOf(n);
      BigInteger m = BigInteger.valueOf((n -1) /lsb);
      a:for (var ba:ALng) {
        BigInteger z = ba.modPow(m,bn);
        if (z.longValue() <= 1)
          continue;
        for (long k = 1;k <= lsb;k <<= 1) {
          if (z.longValue() == n -1)
            continue a;
          z = z.modPow(BigInteger.TWO,bn);
        }
        return false;
      }
    }
    return true;
  }

  List<long[]> factorize(long n){
    if (n < 2)
      return List.of();
    Map<Long, Integer> map = new HashMap<>();
    long[] stk = new long[100];
    int s = 0;
    stk[++s] = n;
    while (0 < s) {
      long cur = stk[s--];
      if (isPrime(cur))
        map.merge(cur,1,Integer::sum);
      else {
        var p = pollard(cur);
        stk[++s] = p;
        stk[++s] = cur /p;
      }
    }

    List<long[]> ret = new ArrayList<>();
    for (var e:map.entrySet())
      ret.add(new long[]{e.getKey(), e.getValue()});
    ret.sort(Comparator.comparing(t -> t[0]));
    return ret;
  }

  long[] divisors(long n){
    List<long[]> facts = factorize(n);
    int l = 1;
    for (var f:facts)
      l *= f[1] +1;

    long[] ret = new long[l];
    int id = 1;
    ret[0] = 1;
    for (var f:facts) {
      long p = f[0];
      for (;f[1]-- > 0;p *= f[0])
        for (int j = 0;ret[j] != f[0];j++)
          ret[id++] = ret[j] *p;
    }

    return ret;
  }

  private long pollard(long n){
    if (n < spf.length)
      return spf[(int) n];
    BigInteger bn = BigInteger.valueOf(n);
    for (long s = 0;;s++)
      for (long x = s,y = f(x,n,bn);;x = f(x,n,bn),y = f(f(y,n,bn),n,bn)) {
        long p = gcd(y -x +n,n);
        if (p == 0 || p == n)
          break;
        if (p != 1)
          return p;
      }
  }

  private long f(long x,long n,BigInteger bn){
    return x < 3e9 ? x *x %n
        : BigInteger.valueOf(x).modPow(BigInteger.TWO,bn).longValue();
  }

  private long pow(long x,long n,long mod){
    x %= mod;
    long ret = 1;
    do {
      if ((n &1) == 1)
        ret = ret *x %mod;
      x = x *x %mod;
    } while (0 < (n >>= 1));

    return ret;
  }

  private long gcd(long a,long b){
    while (0 < b) {
      long t = a;
      a = b;
      b = t %b;
    }
    return a;
  }
}

class Combin{
  int n = 2;
  long[] fac,finv,inv;
  long mod = Solver.mod;

  Combin(){ fac = finv = inv = new long[]{1, 1}; }

  void grow(int n){
    fac = copyOf(fac,n);
    finv = copyOf(finv,n);
    inv = copyOf(inv,n);
    for (int i = this.n;i < n;i++) {
      fac[i] = fac[i -1] *i %mod;
      inv[i] = mod -inv[(int) (mod %i)] *(mod /i) %mod;
      finv[i] = finv[i -1] *inv[i] %mod;
    }
    this.n = n;
  }

  long nHr(int n,int r){ return r < 0 ? 0 : nCr(n +r -1,r); }

  long nCr(int n,int r){
    if (r < 0 || n -r < 0)
      return 0;

    if (this.n <= n)
      grow(n <<1);
    return fac[n] *(finv[r] *finv[n -r] %mod) %mod;
  }

}

abstract class SegmentTree<V, F> extends Seg<V, F>{

  SegmentTree(int n,V e){ this(n,e,i -> e); }

  SegmentTree(int n,V e,IntFunction<V> sup){ super(n,e,sup); }

  @Override
  protected F comp(F f0,F f1){ return null; }

  @Override
  protected void upd(int i,F f){
    super.upd(i,f);
    up(i,i +1);
  }

}

abstract class DualSegmentTree<V, F> extends Seg<V, F>{

  DualSegmentTree(int n,V e){ this(n,e,i -> e); }

  DualSegmentTree(int n,V e,IntFunction<V> sup){ super(n,e,sup); }

  @Override
  V agg(V v0,V v1){ return null; }

  @Override
  protected void rangeMap(int i){}

  @Override
  protected void upd(int i,F f){ upd(i,i +1,f); }

  @Override
  protected void upd(int l,int r,F f){
    down(l,r);
    super.upd(l,r,f);
  }

  @Override
  protected V get(int i){
    down(i,i +1);
    return super.get(i);
  }

}

abstract class LazySegmentTree<V, F> extends Seg<V, F>{

  LazySegmentTree(int n,V e){ this(n,e,i -> e); }

  LazySegmentTree(int n,V e,IntFunction<V> sup){ super(n,e,sup); }

  @Override
  protected void upd(int i,F f){ upd(i,i +1,f); }

  @Override
  protected void upd(int l,int r,F f){
    down(l,r);
    super.upd(l,r,f);
    up(l,r);
  }

  @Override
  protected V get(int i){ return get(i,i +1); }

  @Override
  protected V get(int l,int r){
    down(l,r);
    return super.get(l,r);
  }
}

abstract class Seg<V, F> {
  protected int n;
  private V e;
  private V[] val;
  private F[] lazy;
  private int[] l,r,stk;

  @SuppressWarnings("unchecked")
  Seg(int n,V e,IntFunction<V> sup){
    this.n = n;
    this.e = e;
    val = (V[]) new Object[n <<1];
    lazy = (F[]) new Object[n];
    l = new int[n <<1];
    r = new int[n <<1];
    stk = new int[100];

    for (int i = -1;++i < n;l[i +n] = i,r[i +n] = i +1)
      val[i +n] = sup.apply(i);
    for (int i = n;--i > 0;l[i] = l[i <<1],r[i] = r[i <<1 |1])
      merge(i);
  }

  abstract V agg(V v0,V v1);

  abstract V map(V v,F f,int l,int r);

  abstract F comp(F f0,F f1);

  private void merge(int i){ val[i] = agg(eval(i <<1),eval(i <<1 |1)); }

  protected void rangeMap(int i){ val[i] = map(val[i],lazy[i],l[i],r[i]); }

  protected V eval(int i){
    if (i < n && lazy[i] != null) {
      rangeMap(i);
      prop(i <<1,lazy[i]);
      prop(i <<1 |1,lazy[i]);
      lazy[i] = null;
    }

    return val[i];
  }

  protected void prop(int i,F f){
    if (i < n)
      lazy[i] = lazy[i] == null ? f : comp(lazy[i],f);
    else
      val[i] = map(val[i],f,l[i],r[i]);
  }

  protected void up(int l,int r){
    l = oddPart(l +n);
    r = oddPart(r +n);
    while (1 < l)
      merge(l >>= 1);
    while (1 < r)
      merge(r >>= 1);
  }

  protected void down(int l,int r){
    int s = 0;
    stk[++s] = l = oddPart(l +n);
    stk[++s] = r = oddPart(r +n);
    while (1 < l)
      stk[++s] = l >>= 1;
    while (1 < r)
      stk[++s] = r >>= 1;
    while (0 < s)
      eval(stk[s--]);
  }

  private int oddPart(int i){ return i /(i &-i); }

  protected void upd(int i,F f){ prop(i +n,f); }

  protected void upd(int l,int r,F f){
    l += n;
    r += n;
    do {
      if ((l &1) == 1)
        prop(l++,f);
      if ((r &1) == 1)
        prop(--r,f);
    } while ((l >>= 1) < (r >>= 1));
  }

  protected V get(int i){ return val[i +n]; }

  protected V get(int l,int r){
    l += n;
    r += n;
    V vl = e;
    V vr = e;
    do {
      if ((l &1) == 1)
        vl = agg(vl,eval(l++));
      if ((r &1) == 1)
        vr = agg(eval(--r),vr);
    } while ((l >>= 1) < (r >>= 1));

    return agg(vl,vr);
  }

}

class Util{
  static int[] arrI(int N,IntUnaryOperator f){
    int[] ret = new int[N];
    setAll(ret,f);
    return ret;
  }

  static long[] arrL(int N,IntToLongFunction f){
    long[] ret = new long[N];
    setAll(ret,f);
    return ret;
  }

  static double[] arrD(int N,IntToDoubleFunction f){
    double[] ret = new double[N];
    setAll(ret,f);
    return ret;
  }

  static <T> T[] arr(T[] arr,IntFunction<T> f){
    setAll(arr,f);
    return arr;
  }

}

class MyReader{
  private byte[] buf = new byte[1 <<16];
  private int ptr = 0;
  private int tail = 0;
  private InputStream in;

  MyReader(InputStream in){ this.in = in; }

  private byte read(){
    if (ptr == tail)
      try {
        tail = in.read(buf);
        ptr = 0;
      } catch (IOException e) {}
    return buf[ptr++];
  }

  private boolean isPrintable(byte c){ return 32 < c && c < 127; }

  private byte nextPrintable(){
    byte ret = read();
    while (!isPrintable(ret))
      ret = read();
    return ret;
  }

  int it(){ return toIntExact(lg()); }

  int[] it(int N){ return Util.arrI(N,i -> it()); }

  int[][] it(int H,int W){ return Util.arr(new int[H][],i -> it(W)); }

  int idx(){ return it() -1; }

  int[] idx(int N){ return Util.arrI(N,i -> idx()); }

  int[][] idx(int H,int W){ return Util.arr(new int[H][],i -> idx(W)); }

  long lg(){
    byte i = nextPrintable();
    boolean negative = i == 45;
    long n = negative ? 0 : i -'0';
    while (isPrintable(i = read()))
      n = 10 *n +i -'0';
    return negative ? -n : n;
  }

  long[] lg(int N){ return Util.arrL(N,i -> lg()); }

  long[][] lg(int H,int W){ return Util.arr(new long[H][],i -> lg(W)); }

  double dbl(){ return Double.parseDouble(str()); }

  double[] dbl(int N){ return Util.arrD(N,i -> dbl()); }

  double[][] dbl(int H,int W){ return Util.arr(new double[H][],i -> dbl(W)); }

  char[] ch(){ return str().toCharArray(); }

  char[][] ch(int H){ return Util.arr(new char[H][],i -> ch()); }

  String line(){
    StringBuilder sb = new StringBuilder();

    for (byte c;(c = read()) != '\n';)
      sb.append((char) c);
    return sb.toString();
  }

  String str(){
    StringBuilder sb = new StringBuilder();
    sb.append((char) nextPrintable());

    for (byte c;isPrintable(c = read());)
      sb.append((char) c);
    return sb.toString();
  }

  String[] str(int N){ return Util.arr(new String[N],i -> str()); }

}

class MyWriter{
  OutputStream out;
  byte[] buf = new byte[1 <<16];
  byte[] ibuf = new byte[20];
  int tail = 0;

  MyWriter(OutputStream out){ this.out = out; }

  void flush(){
    try {
      out.write(buf,0,tail);
      tail = 0;
    } catch (IOException e) {
      e.printStackTrace();
    }
  }

  protected void ln(){ write((byte) '\n'); }

  private void write(byte b){
    buf[tail++] = b;
    if (tail == buf.length)
      flush();
  }

  private void write(byte[] b,int off,int len){
    for (int i = off;i < off +len;i++)
      write(b[i]);
  }

  private void write(long n){
    if (n < 0) {
      n = -n;
      write((byte) '-');
    }

    int i = ibuf.length;
    do {
      ibuf[--i] = (byte) (n %10 +'0');
      n /= 10;
    } while (n > 0);

    write(ibuf,i,ibuf.length -i);
  }

  private void print(Object obj){
    if (obj instanceof Boolean)
      print((boolean) obj ? Solver.yes : Solver.no);
    else if (obj instanceof Character)
      write((byte) (char) obj);
    else if (obj instanceof Integer)
      write((int) obj);
    else if (obj instanceof Long)
      write((long) obj);
    else if (obj instanceof char[])
      for (char b:(char[]) obj)
        write((byte) b);
    else if (obj.getClass().isArray()) {
      int l = Array.getLength(obj);
      for (int i = 0;i < l;i++) {
        print(Array.get(obj,i));
        if (i +1 < l)
          write((byte) ' ');
      }
    } else
      for (char b:Objects.toString(obj).toCharArray())
        write((byte) b);
  }

  void printlns(Object... o){
    print(Util.arr(new Object[o.length],i -> o[i]));
    ln();
  }

  void println(Object obj){
    if (obj == null)
      return;

    if (obj instanceof Collection<?>)
      for (Object e:(Collection<?>) obj)
        println(e);
    else if (obj.getClass().isArray() && Array.getLength(obj) > 0 && !(Array.get(obj,0) instanceof char[])
        && Array.get(obj,0).getClass().isArray()) {
      int l = Array.getLength(obj);
      for (int i = 0;i < l;i++)
        println(Array.get(obj,i));
    } else {
      print(obj);
      ln();
    }
  }
}

class Main{
  public static void main(String[] args) throws Exception{
    Solver solver = new Solver();
    solver.out.println(solver.solve());
    solver.out.flush();
    solver.log.println(solver.elapsed());
  }
}
0