semiexpの問題 - uwicoder

リンク

http://d.hatena.ne.jp/semiexp/20111220/1324361030

問題概要

を求めよ。

制約

n<=10^18, k<=100, 2<=P<=10^9

状態

('A`)

ポイント

いろいろな解き方があるのですべて紹介する。

解き方

...

超愚直

O(nk). しぬ。

愚直

累乗を繰り返し2乗して求める。nが小さくkが大きい場合に有効。O(nlog k).

Pが大きい素数の場合

Pが大きい素数の場合、k乗和の公式を求めた後それに代入する。k乗和の公式を求めるのはO(k^3), そしてその公式はたかだかk+2次なので、O(klog k)、全体でO(k^3)で求められる。が、この公式には除算がはいっているため、Pが素数でないとき非常に難しくなる。
から、
これをx=1～nで足して

semiexp式

二項定理より、
が成り立つので、からはじめて行列(Pascal Matrix)をk乗すればよい。O(k^3log n).
Pascal Matrixは、k乗すると、各要素についてk^(対角成分からの距離)倍したのと同様の値になるので、これを利用するとO(k^2log n)でできる。

Loner式

http://community.topcoder.com/stat?c=problem_solution&cr=22285847&rd=12169&pm=8725
求める式をS(n,k)とする。nの繰り返し2乗法で求める。S(a,k)からS(a+1,k), S(a,0)～S(a,k)からS(2a,k)が求まれば良い。前者は簡単で、(a+1)^kを足すだけで良い。
S(2a,k)の(a+x)^kの項に注目すると、(a+x)^kは二項展開できて、
と表せる。これをx=1,2,...,aについて辺々足すと
となる。

DPでもかける。直前の項しか参照しないのでDP用のメモリは2*(k+1)で済む。*2をメインにして+1があれば一律にプラスするようにして成長させていく。

コード

...

public static long powerSum(long n, int k, int mod)
	{
		int[][] C = new int[k+1][k+1];
		for(int i = 0;i <= k;i++){
			C[i][0] = 1;
			for(int j = 1;j <= i;j++){
				C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
			}
		}
 
		int u = 63-Long.numberOfLeadingZeros(n); // 監視対象ビット
		long[][] dp = new long[2][k+1];
		int cur = 1, prev = 0;
		Arrays.fill(dp[0], 1);
 
		u--;
		long c = 1; // もりもり成長
		while(u >= 0){
			// c->2c
			for(int i = 0;i <= k;i++){
				long ret = 2*dp[prev][i];
				long mul = c;
				for(int j = 1;j <= i;j++){
					ret += C[i][j]*mul%mod*dp[prev][i-j]%mod;
					mul = mul*c%mod;
				}
				dp[cur][i] = ret;
			}
			c *= 2;
 
			if(n<<63-u<0){
				// c->c+1
				c++;
				long plus = 1;
				for(int i = 0;i <= k;i++){
					dp[cur][i] += plus;
					plus = plus * c % mod;
				}
			}
			for(int i = 0;i <= k;i++){
				dp[cur][i] %= mod;
			}
			u--;
			cur ^= 1; prev ^= 1;
		}
		return dp[prev][k];
	}