結果
| 問題 |
No.980 Fibonacci Convolution Hard
|
| ユーザー |
 37zigen
|
| 提出日時 | 2020-01-31 22:14:08 |
| 言語 | Java (openjdk 23) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 5,805 bytes |
| コンパイル時間 | 2,479 ms |
| コンパイル使用メモリ | 82,236 KB |
| 実行使用メモリ | 658,324 KB |
| 最終ジャッジ日時 | 2024-09-17 08:33:10 |
| 合計ジャッジ時間 | 9,575 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | MLE * 1 -- * 16 |
ソースコード
import java.util.Arrays;
import java.util.Scanner;
import java.io.*;
class Main {
public static void main(String[] args) {
new Main().run();
}
int MAX = 3123456;
long[] fac = new long[MAX];
long[] ifac = new long[MAX];
long[] inv = new long[MAX];
long[] pw2 = new long[MAX];
long MOD = (long) 1e9 + 7;
{
fac[0] = fac[1] = ifac[0] = ifac[1] = inv[0] = inv[1] = pw2[0] = 1;
pw2[1] = 2;
for (int i = 2; i < fac.length; ++i) {
fac[i] = i * fac[i - 1] % MOD;
inv[i] = MOD - inv[(int) (MOD % i)] * (MOD / i) % MOD;
ifac[i] = inv[i] * ifac[i - 1] % MOD;
pw2[i] = 2 * pw2[i - 1] % MOD;
}
}
void run() {
Scanner sc = new Scanner(System.in);
long p=sc.nextLong();
long[] a=new long[(int)2e6+1];
a[2]=1;
for(int i=3;i<a.length;++i)a[i]=(p*a[i-1]%MOD+a[i-2])%MOD;
a=mul(a,a,MOD);
int Q=sc.nextInt();
int[] q=new int[Q];
PrintWriter pw=new PrintWriter(System.out);
for(int i=0;i<Q;++i){
q[i]=sc.nextInt();
pw.println(a[q[i]]);
}
pw.close();
}
long comb(int n, int k, long mod) {
return fac[n] * ifac[k] % mod * ifac[n - k] % mod;
}
long[] inv(long[] F, long mod0) {
long[] G = new long[1];
G[0] = 1;
while (G.length < F.length) {
int len = G.length;
G = subtract(mul(G, 2, mod0), mul(Arrays.copyOf(F, 2 * len), mul(G, G, mod0), mod0), mod0);
G = Arrays.copyOf(G, 2 * len);
}
return G;
}
long[] mul(long[] a, long coe, long mod0) {
long[] ret = new long[a.length];
for (int i = 0; i < ret.length; ++i) {
ret[i] = coe * a[i] % mod0;
}
return ret;
}
long[] subtract(long[] a, long[] b, long mod0) {
long[] ret = new long[Math.max(a.length, b.length)];
for (int i = 0; i < ret.length; ++i) {
ret[i] = (i < a.length ? a[i] : 0) - (i < b.length ? b[i] : 0);
ret[i] = (ret[i] + mod0) % mod0;
}
return ret;
}
long[] mul(long[] a, long[] b, long mod0) {
if (a.length == 1) {
long[] ret = new long[b.length];
for (int i = 0; i < b.length; ++i) {
ret[i] = a[0] * b[i] % mod0;
}
return ret;
} else if (b.length == 1) {
long[] ret = new long[a.length];
for (int i = 0; i < a.length; ++i) {
ret[i] = a[i] * b[0] % mod0;
}
return ret;
}
// 2^25*5+1, 2^24*73+1, 2^26*7+1
long[] MOD = new long[] { 167772161, 1224736769, 469762049 };
long[] gen = new long[] { 3, 3, 3 };
long[][] c = new long[3][];
for (int i = 0; i < 3; ++i) {
c[i] = mul(Arrays.copyOf(a, a.length), Arrays.copyOf(b, b.length), MOD[i], gen[i]);
}
for (int i = 0; i < c[0].length; ++i) {
c[0][i] = garner(new long[] { c[0][i], c[1][i], c[2][i] }, MOD, mod0);
}
return c[0];
}
long[] mul(long[] a, long[] b, long mod, long gen) {
int degree = Math.max(a.length - 1, b.length - 1);
int level = Long.numberOfTrailingZeros(mod - 1);
long root = gen;
long omega = pow(root, (mod - 1) >> level, mod);
int n = Integer.highestOneBit(2 * degree) << 1;
long[] roots = new long[level];
long[] iroots = new long[level];
roots[0] = omega;
iroots[0] = inv(omega, mod);
for (int i = 1; i < level; ++i) {
roots[i] = roots[i - 1] * roots[i - 1] % mod;
iroots[i] = iroots[i - 1] * iroots[i - 1] % mod;
}
a = Arrays.copyOf(a, n);
b = Arrays.copyOf(b, n);
a = fft(a, false, mod, roots, iroots);
b = fft(b, false, mod, roots, iroots);
for (int i = 0; i < n; ++i)
a[i] = a[i] * b[i] % mod;
a = fft(a, true, mod, roots, iroots);
long inv = inv(n, mod);
for (int i = 0; i < n; ++i) {
a[i] = a[i] * inv % mod;
}
return a;
}
long[] fft(long[] a, boolean inv, long mod, long[] roots, long[] iroots) {
int n = a.length;
int c = 0;
for (int i = 1; i < n; ++i) {
for (int j = n >> 1; j > (c ^= j); j >>= 1)
;
if (c > i) {
long d = a[i];
a[i] = a[c];
a[c] = d;
}
}
int level = Long.numberOfTrailingZeros(mod - 1);
for (int i = 1; i < n; i *= 2) {
long w;
if (!inv)
w = roots[level - Integer.numberOfTrailingZeros(i) - 1];
else
w = iroots[level - Integer.numberOfTrailingZeros(i) - 1];
for (int j = 0; j < n; j += 2 * i) {
long wn = 1;
for (int k = 0; k < i; ++k) {
long u = a[j + k];
long v = a[j + k + i] * wn % mod;
a[j + k] = u + v;
a[j + k + i] = u - v;
if (a[j + k] >= mod)
a[j + k] -= mod;
if (a[j + k + i] < 0)
a[j + k + i] += mod;
wn = wn * w % mod;
}
}
}
return a;
}
long inv(long a, long mod) {
a %= mod;
if (a < 0)
a += mod;
if (a == 0) {
throw new AssertionError();
// return 1;
}
long b = mod;
long p = 1, q = 0;
while (b > 0) {
long c = a / b;
long d;
d = a;
a = b;
b = d % b;
d = p;
p = q;
q = d - c * q;
}
long ret = p < 0 ? (p + mod) : p;
return ret;
}
long garner(long[] x, long[] mod, long mod0) {
assert x.length == mod.length;
int n = x.length;
long[] gamma = new long[n];
for (int i = 0; i < n; i++) {
long prod = 1;
for (int j = 0; j < i; j++) {
prod = prod * mod[j] % mod[i];
}
gamma[i] = inv(prod, mod[i]);
}
long[] v = new long[n];
v[0] = x[0];
for (int i = 1; i < n; i++) {
long tmp = v[i - 1];
for (int j = i - 2; j >= 0; j--) {
tmp = (tmp * mod[j] + v[j]) % mod[i];
}
v[i] = (x[i] - tmp) * gamma[i] % mod[i];
while (v[i] < 0)
v[i] += mod[i];
}
long ret = 0;
for (int i = v.length - 1; i >= 0; i--) {
ret = (ret * mod[i] + v[i]) % mod0;
}
return ret;
}
long pow(long a, long n, long mod) {
long ret = 1;
for (; n > 0; n >>= 1, a = a * a % mod) {
if (n % 2 == 1)
ret = ret * a % mod;
}
return ret;
}
void tr(Object... objects) {
System.out.println(Arrays.deepToString(objects));
}
}