結果
問題 | No.1035 Color Box |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:23:40 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 167 ms / 2,000 ms |
コード長 | 5,361 bytes |
コンパイル時間 | 2,586 ms |
コンパイル使用メモリ | 81,296 KB |
実行使用メモリ | 50,992 KB |
最終ジャッジ日時 | 2024-10-15 03:06:55 |
合計ジャッジ時間 | 8,718 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.net.ConnectException;import java.rmi.dgc.Lease;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.Deque;import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.NoSuchElementException;import java.util.Objects;import java.util.Set;import java.util.Stack;import java.util.TreeMap;import java.util.TreeSet;import static java.util.Comparator.*;public class Main {public static void main(String[] args) {Main main = new Main();main.solve();main.out.close();}// ======================================================================public void solve() {int N = ni();int M = ni();COMinit();long ans = 0, tmp;for (int i = 0; i <= M; i++) {tmp = (COM(M, i) * modpow(i, N)) % MOD;if((M - i) % 2 == 1) ans = (ans - tmp + MOD) % MOD;else ans = (ans + tmp) % MOD;}out.println(ans);}// a の p 乗を求めるアルゴリズム// p = 30 の時、p の変化は 30 -> 15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0// と、半分半分になっていくので、計算量は O(log p) となるint mod = (int) (1e9) + 7;long modpow(long a, int p) {if (p == 0)return 1;if (p % 2 == 0) {int halfP = p / 2; // 偶数ならlong half = modpow(a, halfP); // 乗数を半分にするreturn half * half % mod; // 計算結果を2回かける → 乗数を戻す} else {return a * modpow(a, p - 1) % mod; // 乗数から1を引いた結果に a を掛ける}}int MAX = 510000;int MOD = (int) (1e9) + 7;;long[] fac, finv, inv; // a! (fac[a]) (a!)の-1乗 (finv[a])// テーブルを作る前処理 → これを呼んでから COM() を呼ぶvoid COMinit() {fac = new long[MAX];finv = new long[MAX];inv = new long[MAX];fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++) {fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}// 組み合わせの数を計算する(a個の中からb個を選ぶ)long COM(int n, int k) {if (n < k)return 0;if (n < 0 || k < 0)return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}// ------------------------------------------// ライブラリ// ------------------------------------------private PrintWriter out = new PrintWriter(System.out);// Scannerprivate FastScanner scan = new FastScanner();int ni() {return scan.nextInt();}int[] ni(int n) {int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = ni();}return a;}int[][] ni(int y, int x) {int[][] a = new int[y][x];for (int i = 0; i < y; i++) {for (int j = 0; j < x; j++) {a[i][j] = ni();}}return a;}long nl() {return scan.nextLong();}long[] nl(int n) {long[] a = new long[n];for (int i = 0; i < n; i++) {a[i] = nl();}return a;}long[][] nl(int y, int x) {long[][] a = new long[y][x];for (int i = 0; i < y; i++) {for (int j = 0; j < x; j++) {a[i][j] = nl();}}return a;}String ns() {return scan.next();}String[] ns(int n) {String[] a = new String[n];for (int i = 0; i < n; i++) {a[i] = ns();}return a;}String[][] ns(int y, int x) {String[][] a = new String[y][x];for (int i = 0; i < y; i++) {for (int j = 0; j < x; j++) {a[i][j] = ns();}}return a;}}class FastScanner {private final InputStream in = System.in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;private boolean hasNextByte() {if (ptr < buflen) {return true;} else {ptr = 0;try {buflen = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (buflen <= 0) {return false;}}return true;}private int readByte() {if (hasNextByte())return buffer[ptr++];elsereturn -1;}private static boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}public boolean hasNext() {while (hasNextByte() && !isPrintableChar(buffer[ptr]))ptr++;return hasNextByte();}public String next() {if (!hasNext())throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public long nextLong() {if (!hasNext())throw new NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while (true) {if ('0' <= b && b <= '9') {n *= 10;n += b - '0';} else if (b == -1 || !isPrintableChar(b)) {return minus ? -n : n;} else {throw new NumberFormatException();}b = readByte();}}public int nextInt() {long nl = nextLong();if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)throw new NumberFormatException();return (int) nl;}public double nextDouble() {return Double.parseDouble(next());}}