結果
| 問題 | No.502 階乗を計算するだけ |
| ユーザー |
 ゆうき
|
| 提出日時 | 2023-10-11 15:25:34 |
| 言語 | Java (openjdk 23) |
| 結果 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 52 |
ソースコード
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());
}
}