HDU DP？（Lucas + 帕森斯定理）
來源：程序員人生 發布時間：2014-10-12 22:51:30 閱讀次數：4175次
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
