Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-02-17SRM397 (Practice)

SRM 398 SumOfPowers

|  SRM 398 SumOfPowers - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 398 SumOfPowers - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8725


コーディングフェーズ

  • うわー、数学ゲーだ
    • f(n,k) = 1^k + 2^k + ... + n^k とおく
  • 式をこねくり回してみる・・・
    • f(n,k+1) = n * f(n,k) + f(n-1,k+1) - n * f(n-1, k) を得た
      • うーん、kが一方的に減っていかないと嬉しくない・・・
  • 気を取り直してとりあえず常套手段、f(n,k) を紙に書き出してみる

n\k1234567
11111111
2359173365129
361436982767942316
4103010035413004890・・・
  • うーむ、全然見えてこない
  • 詰んだ
    • MODの性質を利用するのかな?全然分からん
  • 時間切れ。

その後

  • editorialを読む。
  • 言われてみれば自然な発想だ・・・
    • 行列の形に持ち込めば累乗はlognで計算できるもんね

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class SumOfPowers {
	long MOD = 1000000007;
	
	public long[][] pow(long[][] a, long n, long mod) {
		long i = 1;
		long[][] res = E(a.length);
		long[][] ap = mul(E(a.length), a, mod);
		while (i <= n) {
			if ((n & i) >= 1) {
				res = mul(res, ap, mod);
			}
			i *= 2;
			ap = mul(ap, ap, mod);
		}
		return res;
	}
	
	public long[][] E(int n) {
		long[][] a = new long[n][n];
		for (int i = 0 ; i < n ; i++) {
			a[i][i] = 1;
		}
		return a;
	}
	
	public long[][] mul(long[][] a, long[][] b, long mod) {
		long[][] c = new long[a.length][b[0].length];
		if (a[0].length != b.length) {
			System.err.print("err");
		}
		for (int i = 0 ; i < a.length ; i++) {
			for (int j = 0 ; j < b[0].length ; j++) {
				long sum = 0;
				for (int k = 0 ; k < a[0].length ; k++) {
					sum = (sum + a[i][k] * b[k][j]) % mod;
				}
				c[i][j] = sum;
			}
		}
		return c;
	}
	
	public int value(int n, int k) {
		long[][] ncr = new long[100][100];
		ncr[0][0] = 1;
		for (int i = 1 ; i < 100 ; i++) {
			ncr[i][0] = 1;
			ncr[i][i] = 1;
			for (int j = 1 ; j < i ; j++) {
				ncr[i][j] = (ncr[i-1][j] + ncr[i-1][j-1]) % MOD;
			}
		}
		
		long[][] tbl = new long[k+2][k+2];
		tbl[0][0] = 1;
		for (int i = 1 ; i < k+2 ; i++) {
			tbl[0][i] = ncr[k][i-1];
		}
		for (int i = 1 ; i < k+2 ; i++) {
			for (int j = i ; j < k+2 ; j++) {
				tbl[i][j] = ncr[k+1-i][j-i];
			}
		}
		
		long[][] tbln = pow(tbl, n-1, MOD);
		long ans = 0;
		for (int i = 0 ; i < k+2 ; i++) {
			ans = (ans + tbln[0][i]) % MOD;
		}
		return (int)ans;
	}
}