結果
問題 | No.767 配られたジャパリまん |
ユーザー |
|
提出日時 | 2020-04-10 00:51:10 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 559 ms / 2,000 ms |
コード長 | 4,126 bytes |
コンパイル時間 | 3,281 ms |
コンパイル使用メモリ | 85,536 KB |
実行使用メモリ | 61,772 KB |
最終ジャッジ日時 | 2024-09-14 03:44:19 |
合計ジャッジ時間 | 7,962 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 15 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.Arrays;import java.util.Comparator;import java.util.NoSuchElementException;public class Main {public static void main(String[] args) {new Main().run();}final long MOD=(long)1e8+7;int MAX=(int)3e5+1;long[] fac=new long[MAX];long[] inv=new long[MAX];long[] ifac=new long[MAX];{fac[0]=fac[1]=ifac[0]=ifac[1]=inv[0]=inv[1]=1;for (int i=2;i<MAX;++i) {fac[i]=fac[i-1]*i%MOD;inv[i]=MOD-inv[(int)MOD%i]*(MOD/i)%MOD;ifac[i]=inv[i]*ifac[i-1]%MOD;}}long binom(int n,int k) {if(n<0||k<0||n-k<0) return 0;return fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;}long f(int H, int W, int[][] P, int s, int K) {long ans=1;int prey=0,prex=0;for (int i=0;i<=K;++i) {if ((s>>P[i][2])%2==0) continue;if (!(P[i][0]>=prey&&P[i][1]>=prex)) return 0;int dy=P[i][0]-prey;int dx=P[i][1]-prex;ans=ans*binom(dy+dx,dy)%MOD;prey=P[i][0];prex=P[i][1];}return ans;}void run() {FastScanner sc=new FastScanner();int H=sc.nextInt();int W=sc.nextInt();int K=sc.nextInt();int[][] P=new int[K+1][3];for (int i=0;i<K;++i) {P[i][0]=sc.nextInt();P[i][1]=sc.nextInt();P[i][2]=i;}P[K][0]=H;P[K][1]=W;P[K][2]=K;Arrays.sort(P, Comparator.comparing((int[] a)->a[0]).thenComparing(a->a[1]));long[] dist=new long[1<<K];//必ず1の立っている箇所を通る。for (int s=0;s<1<<K;++s) {dist[s]=f(H, W, P, s|1<<K, K);}for (int s=0;s<1<<K;++s) {dist[s]*=(Integer.bitCount(s)%2==0?1:MOD-1);dist[s]%=MOD;}for (int i=0;i<K;++i) {for (int s=(1<<K)-1;s>=0;--s) {if ((s>>i)%2==1) continue;dist[s|1<<i]+=dist[s];dist[s|1<<i]%=MOD;}}//1の立っている場所をどこか通る。PrintWriter pw=new PrintWriter(System.out);for (int s=0;s<1<<K;++s) {pw.println(dist[s]);}pw.close();}void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}}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++]; else return -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());}}