結果
| 問題 | No.907 Continuous Kadomatu |
| ユーザー |
 uwi
|
| 提出日時 | 2019-10-11 22:30:43 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,455 ms / 2,000 ms |
| コード長 | 6,108 bytes |
| コンパイル時間 | 4,059 ms |
| コンパイル使用メモリ | 83,092 KB |
| 実行使用メモリ | 304,912 KB |
| 最終ジャッジ日時 | 2024-11-25 08:22:19 |
| 合計ジャッジ時間 | 19,374 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 25 |
ソースコード
package contest1910;import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.Arrays;import java.util.InputMismatchException;public class E {InputStream is;PrintWriter out;String INPUT = "";int mod = 1000000007;void solve(){// a1 b1// a3 b3// \int_{a2^b2} (x-a1)/(b1-a1)*(x-a3)*(b3-a3) dx// = abx-ax^2/2-bx^2/2+x^3/3// (x-1)/3*(x-1)/2 7/18*(7/18+5/6)/2// (\int_{a2^min(b1,b2)} (x-a1)/(b1-a1) dx// + \int_{min(b1,b2)^b2} 1 dx) / (b2-a2)// \int_{ } p(x)dxint n = ni();int[] a = new int[n];int[] b = new int[n];for(int i = 0;i < n;i++) {a[i] = ni();b[i] = ni();}int[] ys = new int[2*n];for(int i = 0;i < n;i++) {ys[i] = a[i];ys[i+n] = b[i];}Arrays.sort(ys);ys = uniq(ys);int m = ys.length-1;long[][][] dp = new long[n][m][n+1];for(int j = 0;j < m;j++) {if(a[0] <= ys[j] && ys[j+1] <= b[0]) {dp[0][j][0] = invl(b[0] - a[0], mod);}}// 1/4*x-1/4// 3/8 - (1/8*x^2-1/4*x)// -1/8*x^2 + 1/4*x + 3/8for(int i = 1;i < n;i++) {if(i % 2 == 1) {long cum = 0;long il = invl(b[i]-a[i], mod);for(int j = 0;j < m;j++) {// \int_{inf^y} p(x)dxlong[] ip = i(dp[i-1][j]);for(int k = 0;k < ip.length;k++) {ip[k] = ip[k] * il % mod;}long ipinf = sub(ip, ys[j]);long ipsup = sub(ip, ys[j+1]);ip[0] += mod - ipinf;ip[0] += cum;ip[0] %= mod;if(a[i] <= ys[j] && ys[j+1] <= b[i]) {dp[i][j] = ip;}cum += ipsup - ipinf;cum %= mod;if(cum < 0)cum += mod;}}else {long cum = 0;long il = invl(b[i]-a[i], mod);for(int j = m-1;j >= 0;j--) {// \int_{y^sup} p(x)dxlong[] ip = i(dp[i-1][j]);for(int k = 0;k < ip.length;k++) {ip[k] = ip[k] * il % mod;}long ipinf = sub(ip, ys[j]);long ipsup = sub(ip, ys[j+1]);for(int k = 0;k < n+1;k++) {ip[k] = mod-ip[k];}ip[0] += ipsup;ip[0] += cum;ip[0] %= mod;if(a[i] <= ys[j] && ys[j+1] <= b[i]) {dp[i][j] = ip;}cum += ipsup - ipinf;cum %= mod;if(cum < 0)cum += mod;}}}long ans = 0;for(int j = 0;j < m;j++) {ans += sub(i(dp[n-1][j]), ys[j+1]);ans += mod - sub(i(dp[n-1][j]), ys[j]);}out.println(ans%mod);}int[] invs = enumInvs(1000, mod);long[] i(long[] a){long[] b = new long[a.length];for(int i = 1;i < a.length;i++) {b[i] = a[i-1] * invs[i] % mod;}return b;}long sub(long[] a, long x){long v = 0;for(int i = a.length-1;i >= 0;i--) {v = v * x + a[i];v %= mod;}return v;}public static int[] enumInvs(int n, int mod) {int[] inv = new int[n + 1];inv[1] = 1;for (int i = 2; i <= n; i++) {inv[i] = (int) (inv[mod % i] * (long) (mod - mod / i) % mod);}return inv;}public static int[] uniq(int[] a){int n = a.length;int p = 0;for(int i = 0;i < n;i++) {if(i == 0 || a[i] != a[i-1])a[p++] = a[i];}return Arrays.copyOf(a, p);}public static long invl(long a, long mod) {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;}return p < 0 ? p + mod : p;}void run() throws Exception{is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());out = new PrintWriter(System.out);long s = System.currentTimeMillis();solve();out.flush();if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");// Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){// @Override// public void run() {// long s = System.currentTimeMillis();// solve();// out.flush();// if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");// }// };// t.start();// t.join();}public static void main(String[] args) throws Exception { new E().run(); }private byte[] inbuf = new byte[1024];public int lenbuf = 0, ptrbuf = 0;private int readByte(){if(lenbuf == -1)throw new InputMismatchException();if(ptrbuf >= lenbuf){ptrbuf = 0;try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }if(lenbuf <= 0)return -1;}return inbuf[ptrbuf++];}private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }private double nd() { return Double.parseDouble(ns()); }private char nc() { return (char)skip(); }private String ns(){int b = skip();StringBuilder sb = new StringBuilder();while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')sb.appendCodePoint(b);b = readByte();}return sb.toString();}private char[] ns(int n){char[] buf = new char[n];int b = skip(), p = 0;while(p < n && !(isSpaceChar(b))){buf[p++] = (char)b;b = readByte();}return n == p ? buf : Arrays.copyOf(buf, p);}private int[] na(int n){int[] a = new int[n];for(int i = 0;i < n;i++)a[i] = ni();return a;}private long[] nal(int n){long[] a = new long[n];for(int i = 0;i < n;i++)a[i] = nl();return a;}private char[][] nm(int n, int m) {char[][] map = new char[n][];for(int i = 0;i < n;i++)map[i] = ns(m);return map;}private int[][] nmi(int n, int m) {int[][] map = new int[n][];for(int i = 0;i < n;i++)map[i] = na(m);return map;}private int ni() { return (int)nl(); }private long nl(){long num = 0;int b;boolean minus = false;while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));if(b == '-'){minus = true;b = readByte();}while(true){if(b >= '0' && b <= '9'){num = num * 10 + (b - '0');}else{return minus ? -num : num;}b = readByte();}}private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }}