結果

問題 No.271 next_permutation (2)
ユーザー uwiuwi
提出日時 2015-08-22 04:36:56
言語 Java21
(openjdk 21)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 9,728 bytes
コンパイル時間 6,433 ms
コンパイル使用メモリ 81,184 KB
実行使用メモリ 53,068 KB
最終ジャッジ日時 2023-09-25 15:53:13
合計ジャッジ時間 6,845 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 58 ms
50,416 KB
testcase_01 AC 77 ms
51,820 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 44 ms
49,056 KB
testcase_05 AC 45 ms
49,296 KB
testcase_06 AC 44 ms
49,160 KB
testcase_07 AC 45 ms
49,472 KB
testcase_08 AC 44 ms
49,136 KB
testcase_09 AC 44 ms
49,304 KB
testcase_10 AC 46 ms
49,068 KB
testcase_11 AC 45 ms
49,184 KB
testcase_12 AC 46 ms
49,560 KB
testcase_13 AC 100 ms
52,364 KB
testcase_14 AC 45 ms
49,132 KB
testcase_15 AC 44 ms
49,256 KB
testcase_16 AC 45 ms
49,140 KB
testcase_17 AC 45 ms
49,492 KB
testcase_18 AC 100 ms
52,344 KB
testcase_19 AC 95 ms
52,288 KB
testcase_20 AC 136 ms
53,068 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package contest;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;

public class Q336 {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni();;
		long K = nl();
		if(K == 0){
			out.println(0);
			return;
		}
		int[] P = na(n);
		for(int i = 0;i < n;i++)P[i]--;
		int[] ft = new int[n+1];
		long inv = 0;
		for(int i = 0;i < n;i++){
			inv += i-sumFenwick(ft, P[i]);
			addFenwick(ft, P[i], 1);
		}
		int mod = 1000000007;
		inv %= mod;
		long f = 1;
		long ret = 0;
		long right = 0;
		LST space = new LST(n);
		ret += inv;
		K--;
		
		// 04231 inv=5
		out:
		for(int d = n-1;d >= 0;d--){
			space.set(P[d]);
			int cur = P[d];
			while(true){
				addFenwick(ft, cur, -1);
				inv -= d-sumFenwick(ft, cur);
				if(inv < 0)inv += mod;
				right += d-sumFenwick(ft, cur);
				right -= cur-sumFenwick(ft, cur);
				if(right >= mod)right -= mod;
				if(right < 0)right += mod;
				int next = space.next(cur+1);
				if(next == -1){
					P[d] = -1;
					break;
				}
				cur = next;
				P[d] = cur;
				inv += d-sumFenwick(ft, cur);
				if(inv >= mod)inv -= mod;
				right -= d-sumFenwick(ft, cur);
				right += cur-sumFenwick(ft, cur);
				if(right >= mod)right -= mod;
				if(right < 0)right += mod;
				addFenwick(ft, cur, 1);
//				tr(K, d, f, cur, inv, right, P[d]);
				if(K - f < 0){
					space.unset(cur);
					break out;
				}
				
				ret += ((inv+right) * (f%mod) + f/2%mod*((long)(n-1-d)*(n-1-d-1)/2%mod))%mod;
				K -= f;
				cur = next;
			}
			f = f * (n-d);
		}
//		tr("K", K, ret);
		if(n <= 20){
			long F = 1;
			for(int u = 1;u <= n;u++){
				F *= u;
			}
			long m = K / F;
			ret += (F/2%mod)*((long)n*(n-1)/2%mod)%mod*(m%mod)%mod;
			K -= m*F;
		}
//		tr(P);
		
		f = 1;
		for(int d = Math.max(0, n-20), e = 1;d < n;d++, e++){
			f *= e;
		}
//		tr(inv, right);
		for(int d = Math.max(0, n-20);d < n;d++){
			int e = n-d;
			if(e > 0)f /= e;
//			tr("df", d, f, K, P);
			if(P[d] != -1){
				continue;
			}
			for(int j = space.next(0);j != -1;j = space.next(j+1)){
				int cur = j;
				P[d] = cur;
				inv += d-sumFenwick(ft, cur);
				if(inv >= mod)inv -= mod;
				right -= d-sumFenwick(ft, cur);
				right += cur-sumFenwick(ft, cur);
				if(right >= mod)right -= mod;
				if(right < 0)right += mod;
				addFenwick(ft, cur, 1);
//				tr(K, d, f, cur, inv, right);
				if(K-f < 0){
					space.unset(cur);
					break;
				}
				K -= f;
				ret += ((inv+right) * (f%mod) + f/2%mod*((long)(n-1-d)*(n-1-d-1)/2%mod))%mod;
				
				addFenwick(ft, cur, -1);
				inv -= d-sumFenwick(ft, cur);
				if(inv < 0)inv += mod;
				right += d-sumFenwick(ft, cur);
				right -= cur-sumFenwick(ft, cur);
				if(right < 0)right += mod;
				if(right >= mod)right -= mod;
			}
		}
//		tr(P);
//		tr("K", K);
		
		out.println(ret%mod);
	}
	
	public static class LST {
		public long[][] set;
		public int n;
//		public int size;
		
		public LST(int n) {
			this.n = n;
			int d = 1;
			for(int m = n;m > 1;m>>>=6, d++);
			
			set = new long[d][];
			for(int i = 0, m = n>>>6;i < d;i++, m>>>=6){
				set[i] = new long[m+1];
			}
//			size = 0;
		}
		
		// [0,r)
		public LST setRange(int r)
		{
			for(int i = 0;i < set.length;i++, r=r+63>>>6){
				for(int j = 0;j < r>>>6;j++){
					set[i][j] = -1L;
				}
				if((r&63) != 0)set[i][r>>>6] |= (1L<<r)-1;
			}
			return this;
		}
		
		// [0,r)
		public LST unsetRange(int r)
		{
			if(r >= 0){
				for(int i = 0;i < set.length;i++, r=r+63>>>6){
					for(int j = 0;j < r+63>>>6;j++){
						set[i][j] = 0;
					}
					if((r&63) != 0)set[i][r>>>6] &= ~((1L<<r)-1);
				}
			}
			return this;
		}
		
		public LST set(int pos)
		{
			if(pos >= 0 && pos < n){
//				if(!get(pos))size++;
				for(int i = 0;i < set.length;i++, pos>>>=6){
					set[i][pos>>>6] |= 1L<<pos;
				}
			}
			return this;
		}
		
		public LST unset(int pos)
		{
			if(pos >= 0 && pos < n){
//				if(get(pos))size--;
				for(int i = 0;i < set.length && (i == 0 || set[i-1][pos] == 0L);i++, pos>>>=6){
					set[i][pos>>>6] &= ~(1L<<pos);
				}
			}
			return this;
		}
		
		public boolean get(int pos)
		{
			return pos >= 0 && pos < n && set[0][pos>>>6]<<~pos<0;
		}
		
		public int prev(int pos)
		{
			for(int i = 0;i < set.length && pos >= 0;i++, pos>>>=6, pos--){
				int pre = prev(set[i][pos>>>6], pos&63);
				if(pre != -1){
					pos = pos>>>6<<6|pre;
					while(i > 0)pos = pos<<6|63-Long.numberOfLeadingZeros(set[--i][pos]);
					return pos;
				}
			}
			return -1;
		}
		
		public int next(int pos)
		{
			for(int i = 0;i < set.length && pos>>>6 < set[i].length;i++, pos>>>=6, pos++){
				int nex = next(set[i][pos>>>6], pos&63);
				if(nex != -1){
					pos = pos>>>6<<6|nex;
					while(i > 0)pos = pos<<6|Long.numberOfTrailingZeros(set[--i][pos]);
					return pos;
				}
			}
			return -1;
		}
		
		private static int prev(long set, int n)
		{
			long h = Long.highestOneBit(set<<~n);
			if(h == 0L)return -1;
			return Long.numberOfTrailingZeros(h)-(63-n);
		}
		
		private static int next(long set, int n)
		{
			long h = Long.lowestOneBit(set>>>n);
			if(h == 0L)return -1;
			return Long.numberOfTrailingZeros(h)+n;
		}
		
		@Override
		public String toString()
		{
			List<Integer> list = new ArrayList<Integer>();
			for(int pos = next(0);pos != -1;pos = next(pos+1)){
				list.add(pos);
			}
			return list.toString();
		}
	}

	
	public static int sumFenwick(int[] ft, int i) {
		int sum = 0;
		for (i++; i > 0; i -= i & -i)
			sum += ft[i];
		return sum;
	}

	public static void addFenwick(int[] ft, int i, int v) {
		if (v == 0 || i < 0)
			return;
		int n = ft.length;
		for (i++; i < n; i += i & -i)
			ft[i] += v;
	}

	public static int findGFenwick(int[] ft, int v) {
		int i = 0;
		int n = ft.length;
		for (int b = Integer.highestOneBit(n); b != 0 && i < n; b >>= 1) {
			if (i + b < n) {
				int t = i + b;
				if (v >= ft[t]) {
					i = t;
					v -= ft[t];
				}
			}
		}
		return v != 0 ? -(i + 1) : i - 1;
	}

	public static int valFenwick(int[] ft, int i) {
		return sumFenwick(ft, i) - sumFenwick(ft, i - 1);
	}

	public static int[] restoreFenwick(int[] ft) {
		int n = ft.length - 1;
		int[] ret = new int[n];
		for (int i = 0; i < n; i++)
			ret[i] = sumFenwick(ft, i);
		for (int i = n - 1; i >= 1; i--)
			ret[i] -= ret[i - 1];
		return ret;
	}

	public static int before(int[] ft, int x) {
		int u = sumFenwick(ft, x - 1);
		if (u == 0)
			return -1;
		return findGFenwick(ft, u - 1) + 1;
	}

	public static int after(int[] ft, int x) {
		int u = sumFenwick(ft, x);
		int f = findGFenwick(ft, u);
		if (f + 1 >= ft.length - 1)
			return -1;
		return f + 1;
	}

	public static int[] buildFenwick(int[] a) {
		int n = a.length;
		int[] ft = new int[n + 1];
		System.arraycopy(a, 0, ft, 1, n);
		for (int k = 2, h = 1; k <= n; k *= 2, h *= 2) {
			for (int i = k; i <= n; i += k) {
				ft[i] += ft[i - h];
			}
		}
		return ft;
	}

	public static int[] buildFenwick(int n, int v) {
		int[] ft = new int[n + 1];
		Arrays.fill(ft, 1, n + 1, v);
		for (int k = 2, h = 1; k <= n; k *= 2, h *= 2) {
			for (int i = k; i <= n; i += k) {
				ft[i] += ft[i - h];
			}
		}
		return ft;
	}
	
	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");
	}
	
	public static void main(String[] args) throws Exception { new Q336().run(); }
	
	private byte[] inbuf = new byte[1024];
	private 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 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[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private int ni()
	{
		int num = 0, 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 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