HDU DP？（Lucas + 帕森斯定理）
来源：程序员人生 发布时间：2014-10-12 22:51:30 阅读次数：3935次
DP?
题目链接：Click Here~
题目分析：
给出一个终点坐标，求出(0,0)开始的到(n,k)的最小权重和。
算法分析：
根据杨辉三角的性质可以知道，只要往两边走则得到的值会更小。因为,C(N,M) = C(N,N-M)。所以，我们尽量的斜向的往旁边走。但是，在斜向走k步后就已经到达边界了，此时只要顺着1一直往上走就可以了。所以，经过的最短路和为:C(n,k) + C(n-1,k-1) + C(n-2,k-2) + ...... C(n - k + 1,1)+ C(n - k,0) + (n - k)[走1的个数].
而这样直接算肯定超时，所以我们要想办法优化。这个优化呢？
我么发现可以运用帕森斯定理C(N,M) = C(N-1,M) + C(N - 1,M-1)
我们可以将C(n-k,0) 变为 C(n-k+1,0)则，
C(n-k+2,1) = C(n-k+1,0) + C(n-k+1,1)
C(n-k+3,2) = C(n-k+2,1) + C(n-k+2,2)
.
.
.
.
C(n+1,k) = C(n,k-1) + C(n,k)
所以，最后总和为：C(n+1,k) + (n - k)
然后，根据自己的需要运用可以在限制时间内求出组合数的算法就可以了。
我运用的是Lucas加预处理阶乘打表。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef __int64 LL;
const int MAXN = 10000 + 10;
LL fact[1500][MAXN];
LL primes[1500];
bool vst[MAXN];
int hash[MAXN];
int K;
//预处理阶乘
void init(){
int top = 0;
memset(vst,0,sizeof(vst));
for(LL i = 2;i < MAXN;++i)if(!vst[i]){
hash[i] = top;
primes[top++] = i;
for(LL j = i + i;j < MAXN;j += i) vst[j] = 1;
}
for(LL i = 0;i < top;++i){
LL p = primes[i];
fact[i][0] = 1;
for(LL j = 1;j <= p;++j){
fact[i][j] = fact[i][j - 1] * j % p;
}
}
}
//扩展欧几里得
LL extgcd(LL a,LL b,LL& x,LL& y){
LL d = a;
if(b != 0){
d = extgcd(b,a%b,y,x);
y -= (a / b) * x;
} else {
x = 1; y = 0;
}
return d;
}
//求解逆元
LL mod_inverse(LL a,LL m){
LL x,y;
extgcd(a,m,x,y);
return (m + x % m) % m;
}
LL mod_fact(LL n,LL p,LL& e){
e = 0;
if(n == 0) return 1;
LL res = mod_fact(n / p,p,e);
e += n / p;
if(n / p % 2 != 0) return res*(p - fact[K][n % p]) % p;
return res * fact[K][n % p] % p;
}
LL mod_comb(LL n,LL k,LL p){
if(n < 0||k < 0 || n < k) return 0;
LL e1,e2,e3;
LL a1 = mod_fact(n,p,e1),a2 = mod_fact(k,p,e2),a3 = mod_fact(n - k,p,e3);
if(e1 > e2 + e3) return 0;
return a1 * mod_inverse(a2 * a3 % p,p) % p;
}
int main()
{
init();
int kase = 1;
LL N,M,p;
while(cin >> N >> M >> p){
K = hash[p];
if(M > N / 2)
M = N - M;
cout << "Case #" << kase++ <<": ";
cout << (mod_comb(N + 1,M,p) % p + (N - M) % p) % p << endl;
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
