結果
問題 | No.695 square1001 and Permutation 4 |
ユーザー |
|
提出日時 | 2018-06-09 02:39:02 |
言語 | Java (openjdk 23) |
結果 |
MLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,167 bytes |
コンパイル時間 | 2,497 ms |
コンパイル使用メモリ | 81,704 KB |
実行使用メモリ | 96,364 KB |
最終ジャッジ日時 | 2024-07-22 19:25:34 |
合計ジャッジ時間 | 16,084 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 5 MLE * 7 |
ソースコード
import java.math.BigInteger;import java.util.Arrays;import java.util.Scanner;import java.util.concurrent.ConcurrentHashMap;public class Main {public static void main(String[] args) {new Main().run();}void run() {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[] x = new int[m];for (int i = 0; i < m; ++i)x[i] = sc.nextInt();dp = new int[(n + 1) / 2];long mo1 = 17 * 9920467;long mo2 = 592951213;long mo3 = mo1 * mo2;long ans1 = solve(mo1, n, m, x);long ans2 = solve(mo2, n, m, x);long f1 = ans1 % mo1 * inv(mo2, mo1) % mo1 * mo2 % mo3;long f2 = inv(mo1, mo2) % mo2 * (ans2 % mo2 - f1 % mo2 + mo2) % mo2 * mo1 % mo3;System.out.println((f1 + f2) % mo3);}long inv(long a, long mo) {a %= mo;// a + 0p = a// 0a + 1p =plong[] v = { 0, 1, mo };long[] u = { 1, 0, a };while (v[2] != 1) {if (v[2] < u[2]) {long[] tmp = Arrays.copyOf(v, v.length);v = u;u = tmp;continue;}long coe = v[2] / u[2];for (int i = 0; i < 3; ++i) {v[i] = v[i] - u[i] * coe;}}return v[0] < 0 ? v[0] + mo : v[0];}int[] dp;long solve(long mo, int n, int m, int[] x) {Arrays.fill(dp, 0);dp[0] = 1;for (int i = 0; i < dp.length; ++i) {for (int j = 0; j < x.length; ++j) {if (i + x[j] >= dp.length)continue;dp[i + x[j]] = (int) ((dp[i + x[j]] + dp[i]) % mo);}}long ret = 0;for (int i = 0; i < dp.length; ++i) {for (int j = 0; j < m; ++j) {if (x[j] + i < dp.length || (n - 1) - x[j] - i < 0)continue;ret = (ret + (long) dp[(n - 1) - x[j] - i] * dp[i] % mo) % mo;}}return ret;}class BIT {int n;int[] a;public BIT(int n_) {n = n_;a = new int[n + 1];}void add(int k, int add) {++k;while (k < a.length) {a[k] += add;k += k & -k;}}int sum(int k) {++k;int ret = 0;while (k > 0) {ret += a[k];k -= k & -k;}return ret;}int sum(int a, int b) {return sum(b - 1) - sum(a - 1);}}void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}}