这道题我是先算出N=2的通解然后猜测其他情况AC的(N=2还能手工算通解，因为所有的d=Image(a[])都是一个整数，不是向量)。
其中数学上算出来是f(2,k) = (k*k*(k-1)) - (k*(k-1)*(2*k-1))/3 + (k*(k+1))/2，
其实第一项是2*k*(1+2+..._(k-1)), 第二项是2*(1^2+2^2+...+(k-1)^2), 第三项是1+2+...+k)。
(2,1) = 1
(2,1) = 5
(2,1) = 14
(2,1) = 30

但是N=3,4的时候通解太复杂了，半猜半证的有f(3, K)是个关于K的五次多项式，根据前面6个点
(3,1) = 1
(3,2) = 13
(3,3) = 70
(3,4) = 246
(3,5) = 671
(3,6) = 1547
用高斯消去法求出
f(3,k) = (k + 5*k*k + 10*k*k*k + 10*k*k*k*k + 4*k*k*k*k*k)/30

N=4是关于K的7次多项式，根据前8个点
(4,1) = 1
(4,2) = 34
(4,3) = 353
(4,4) = 2037
(4,5) = 8272
(4,6) = 26585
(4,7) = 72302
(4,8) = 173502
用高斯消去法求出
f(4,k) = (18*k + 119*k*k + 364*k*k*k + 665*k*k*k*k + 742*k*k*k*k*k +476*k*k*k*k*k*k + 136*k*k*k*k*k*k*k)/2520
但是最后一项在计算过程会溢出2^63，我的做法是拆开来找到a,b,c,d,使得：(a*2520+b) = 136*k*k*k
(c*2520+d) = k*k*k*k
然后商就等于(a*c*2520 + b*c + a*d),余数就等于b*d，再和前面的商相加，余相加就不溢出了。
==============================================================
至于那几个点的值我是先写一个很慢的程序暴力求出真实的值：
#include <iostream>
using namespace std;
typedef unsigned long long lld;
lld a[4], d[3], ans;
void DFS(lld depth, lld degree, lld range)
{
	if(depth == degree)
	{
		lld product = 1;
		for(int i = 0; i < degree-1; i++)
		{
			d[i] = min(a[i], a[i+1]) + 1;
			product *= d[i];
		}
		ans += product;
		return;
	}
	for(lld i = 0; i < range; i++)
	{
		a[depth] = i;
		DFS(depth+1, degree, range);
	}
}
int main()
{
	lld n, k;
	while(cin>>n>>k)
	{
		ans = 0;
		DFS(0, n, k);
		cout<<"("<<n<<", "<<k<<") = "<<ans<<endl;
	}
}

• Re:回馈社会 (106) Los_Angelos_Laycurse 2012-11-01 17:29:10