結果

問題 No.645 Count Permutation
ユーザー uwi
提出日時 2018-02-02 21:46:12
言語 Java8
(openjdk 1.8.0.191)
結果
AC  
実行時間 334 ms
コード長 3,733 Byte
コンパイル時間 2,602 ms
使用メモリ 23,520 KB
最終ジャッジ日時 2019-07-21 00:04:47

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
Sample1.txt AC 75 ms
19,200 KB
Sample2.txt AC 74 ms
19,208 KB
Sample3.txt AC 90 ms
20,440 KB
Sample4.txt AC 77 ms
19,304 KB
test1.txt AC 75 ms
19,212 KB
test2.txt AC 76 ms
19,208 KB
test3.txt AC 75 ms
19,244 KB
test4.txt AC 77 ms
19,304 KB
test5.txt AC 75 ms
19,252 KB
test6.txt AC 84 ms
20,236 KB
test7.txt AC 79 ms
19,552 KB
test8.txt AC 123 ms
23,500 KB
test9.txt AC 111 ms
23,204 KB
test10.txt AC 121 ms
23,500 KB
test11.txt AC 95 ms
21,112 KB
test12.txt AC 156 ms
23,512 KB
test13.txt AC 187 ms
23,516 KB
test14.txt AC 325 ms
23,520 KB
test15.txt AC 173 ms
23,516 KB
test16.txt AC 334 ms
23,520 KB
test17.txt AC 334 ms
23,512 KB
test18.txt AC 190 ms
23,508 KB
test19.txt AC 77 ms
19,200 KB
test20.txt AC 75 ms
19,200 KB
test21.txt AC 218 ms
23,512 KB
test22.txt AC 223 ms
23,512 KB
test23.txt AC 295 ms
23,520 KB
test24.txt AC 204 ms
23,512 KB
test25.txt AC 171 ms
23,516 KB
test26.txt AC 274 ms
23,512 KB
test27.txt AC 279 ms
23,516 KB
test28.txt AC 298 ms
23,508 KB
test29.txt AC 158 ms
23,520 KB
test30.txt AC 155 ms
23,508 KB
テストケース一括ダウンロード

ソースコード

diff #
package contest180202;
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 D {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni();
		long L = nl(), R = nl();
		long ret = count(R, n) - count(L-1, n);
		if(ret < 0)ret += 1000000007;
		out.println(ret);
	}
	
	long count(long R, int n)
	{
		if(R < 0)return 0;
		long[] c = new long[65];
		c[0] = 1;
		int mod = 1000000007;
		long F = 1;
		for(int i = 1;i <= n-2;i++){
			long[] d = new long[65];
			for(int j = 64;j >= 1;j--){
				d[j] = c[j-1];
			}
			for(int j = 64;j >= 0;j--){
				d[j] += c[j] * i;
			}
			for(int j = 0;j < 65;j++){
				d[j] %= mod;
			}
			c = d;
			F = F * i % mod;
		}
		F = F * (n-1) % mod;
		long G = F * n % mod;
		long ret = 0;
		for(int i = 60;i >= 1;i--){
			if(R >= 1L<<i){
				ret += c[i-1];
			}
		}
		ret += G + (mod-F);
		ret %= mod;
		return ret;
	}
	
	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 D().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)); }
}
0