結果

問題 No.1080 Strange Squared Score Sum
ユーザー uwiuwi
提出日時 2020-06-12 23:05:56
言語 Java21
(openjdk 21)
結果
AC  
実行時間 970 ms / 5,000 ms
コード長 8,665 bytes
コンパイル時間 4,886 ms
コンパイル使用メモリ 83,624 KB
実行使用メモリ 59,420 KB
最終ジャッジ日時 2024-06-24 05:49:07
合計ジャッジ時間 17,322 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 54 ms
50,104 KB
testcase_01 AC 53 ms
50,152 KB
testcase_02 AC 656 ms
59,360 KB
testcase_03 AC 747 ms
59,344 KB
testcase_04 AC 393 ms
58,972 KB
testcase_05 AC 483 ms
59,328 KB
testcase_06 AC 200 ms
56,988 KB
testcase_07 AC 310 ms
56,836 KB
testcase_08 AC 663 ms
58,172 KB
testcase_09 AC 493 ms
59,244 KB
testcase_10 AC 219 ms
56,652 KB
testcase_11 AC 739 ms
59,380 KB
testcase_12 AC 485 ms
59,248 KB
testcase_13 AC 773 ms
59,140 KB
testcase_14 AC 564 ms
59,252 KB
testcase_15 AC 55 ms
50,188 KB
testcase_16 AC 970 ms
59,140 KB
testcase_17 AC 732 ms
59,264 KB
testcase_18 AC 725 ms
59,420 KB
testcase_19 AC 724 ms
59,200 KB
testcase_20 AC 721 ms
59,272 KB
testcase_21 AC 728 ms
59,164 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package contest200612;
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 E2 {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni();
		int mod = 1000000009;
		int[][] fif = enumFIF(n, mod);
		int m = n > 2000 ? 100 : n;
		long[][] dp = new long[4][m+1];
		dp[0][0] = 1;
		for(int v = 1;v <= n;v++){
			long[][] ndp = new long[4][m+1];
			for(int f = 0;f*v <= m;f++){
				long M = pow(v+1, 2*f, mod) * fif[1][f] % mod;
				for(int i = 0;i < 4;i++){
					for(int j = 0;j+f*v <= m;j++){
						ndp[i+f&3][j+f*v] += dp[i][j] * M;
						ndp[i+f&3][j+f*v] %= mod;
					}
				}
			}
			dp = ndp;
		}
		long[] base = new long[m];
		for(int i = 1;i <= m;i++){
			long sum = 0;
			for(int j = 0;j < 4;j++){
				sum += (long)(j >= 2 ? mod-1 : 1) * dp[j][i];
				sum %= mod;
			}
			base[i-1] = sum;
		}
		
		if(n > m){
			long[][] res = guessLeaned(mod, base);
			base = Arrays.copyOf(base, n);
			int t = res.length;
			for(int i = m+1;i <= n;i++){
				base[i-1] = f(res, Arrays.copyOfRange(base, i-t, i-1), i-1, mod);
			}
		}
		
		for(int i = 0;i < n;i++){
			out.println(base[i]*fif[0][n]%mod);
		}
	}
	
	public static long f(long[][] ged, long[] prevs, long x, int mod)
	{
		int n = ged.length;
		assert prevs.length == n-1;
		x -= n-1;
		
		long s = 0;
		long tar = 0;
		for(int i = 0;i < n;i++){
			long co = 0;
			for(int j = ged[i].length-1;j >= 0;j--){
				co = (co * x + ged[i][j]) % mod;
			}
			if(i < n-1){
				s += co * prevs[i];
				s %= mod;
			}else{
				tar = co;
			}
		}
		
		long ret = -invl(tar, mod) * s % mod;
		if(ret < 0)ret += mod;
		return ret;
	}
	
	public static long[][] guessLeaned(int mod, long... a)
	{
		int n = a.length;
		
		// #formula >= #variable
		// n-r+2 >= r(r+1)/2
		for(int r = n;r >= 1;r--){
			if(n-r+2 < r*(r+1)/2)continue;
			int[][] M = new int[n-r+2][r*(r+1)/2];
			for(int i = 0;i < n-r+1;i++){
				int p = 0;
				for(int j = 0;j < r;j++){
					long prod = 1;
					for(int k = 0;k <= r-j-1;k++){
						M[i][p++] = (int)(prod*a[i+j]%mod);
						prod = prod * i % mod;
					}
				}
			}
			M[n-r+1][0] = 1;
			
			int[] v = new int[n-r+2];
			v[n-r+1] = 1;
			
			Result res = gaussElimination(M, v, mod);
			if(res.exists){
				long[][] ret = new long[r][];
				int p = 0;
				for(int i = 0;i < r;i++){
					ret[i] = new long[r-i];
					for(int j = 0;j < r-i;j++){
						ret[i][j] = res.sol[p++];
					}
				}
				
				// reformat
				int ilast = r;
				for(int i = r-1;i >= 0;i--){
					int last = ret[i].length;
					while(last > 0 && ret[i][last-1] == 0)last--;
					ret[i] = Arrays.copyOf(ret[i], last);
					if(last == 0 && i+1 == ilast){
						ilast--;
					}
				}
				ret = Arrays.copyOf(ret, ilast);
				
				return ret;
			}
		}
		return null;
	}
	
	
	
	public static int[][] enumFIF(int n, int mod) {
		int[] f = new int[n + 1];
		int[] invf = new int[n + 1];
		f[0] = 1;
		for (int i = 1; i <= n; i++) {
			f[i] = (int) ((long) f[i - 1] * i % mod);
		}
		long a = f[n];
		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;
		}
		invf[n] = (int) (p < 0 ? p + mod : p);
		for (int i = n - 1; i >= 0; i--) {
			invf[i] = (int) ((long) invf[i + 1] * (i + 1) % mod);
		}
		return new int[][] { f, invf };
	}
	
	public static Result gaussElimination(int[][] M, int[] v, int mod)
	{
		int n = M.length, m = M[0].length;
		int[] head = new int[n];
		
		// if not needed, comment out.
		for(int[] row : M){
			for(int i = 0;i < row.length;i++){
				row[i] %= mod;
				if(row[i] < 0)row[i] += mod;
			}
		}
		
		// Forward Elimination
		int row = 0;
		for(int col = 0;col < m;col++){
			// select pivot
			boolean pivotFound = false;
			out:
			for(int prow = row;prow < n;prow++){
				if(M[prow][col] != 0){
					// pivot found
					if(prow != row){
						// swap rows
						for(int k = 0;k < m;k++){
							int u = M[prow][k]; M[prow][k] = M[row][k]; M[row][k] = u;
						}
						int dum = v[prow]; v[prow] = v[row]; v[row] = dum;
					}
					pivotFound = true;
					break out;
				}
			}
			if(!pivotFound)continue;
			head[row] = col;
			
			// diag to 1
			long imul = invl(M[row][col], mod);
			for(int k = 0;k < m;k++){
				M[row][k] = (int)(M[row][k] * imul % mod);
			}
			v[row] = (int)(v[row] * imul % mod);
			
			for(int j = row+1;j < n;j++){
				if(M[j][col] != 0){
					long mul = mod-M[j][col];
					for(int k = col;k < m;k++){
						M[j][k] = (int)((M[j][k] + M[row][k] * mul) % mod);
					}
					v[j] = (int)((v[j] + v[row] * mul) % mod);
				}
			}
			row++;
		}
		
		Result ret = new Result();
		ret.mat = M;
		for(int i = row;i < n;i++){
			if(v[i] != 0){
				ret.rank = row;
				ret.exists = false;
				return ret;
			}
		}
		
		for(int i = row-1;i >= 0;i--){
			for(int j = i-1;j >= 0;j--){
				if(M[j][head[i]] != 0){
					long mul = mod-M[j][head[i]];
					for(int k = head[i];k < m;k++){
						M[j][k] = (int)((M[j][k] + M[i][k] * mul) % mod);
					}
					v[j] = (int)((v[j] + v[i] * mul) % mod);
				}
			}
		}
		
		int[] retv = new int[m];
		for(int i = 0;i < row;i++){
			retv[head[i]] = v[i];
		}
		
		ret.sol = retv;
		ret.rank = row;
		ret.exists = true;
		return ret;
	}
	
	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;
	}

	
	public static class Result
	{
		public int[][] mat;
		public int[] sol;
		public int rank;
		public boolean exists;
	}

	
	public static long pow(long a, long n, long mod) {
		//		a %= mod;
		long ret = 1;
		int x = 63 - Long.numberOfLeadingZeros(n);
		for (; x >= 0; x--) {
			ret = ret * ret % mod;
			if (n << 63 - x < 0)
				ret = ret * a % 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 E2().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