HDOJ 4349 DP?

盡量沿著邊走距離最短，化減後 C（n+1，k）+ n - k，

預處理階乘，Lucas定理組合數取模

DP?

Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 128000/128000 K (Java/Others)
Total Submission(s): 1899 Accepted Submission(s): 633


Problem Description
Figure 1 shows the Yang Hui Triangle. We number the row from tZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcCB0byBib3R0b20gMCwxLDIsoa1hbmQgdGhlIGNvbHVtbiBmcm9tIGxlZnQgdG8gcmlnaHQgMCwxLDIsoa0uSWYgdXNpbmcgQyhuLGspIHJlcHJlc2VudHMgdGhlIG51bWJlciBvZiByb3cgbiwgY29sdW1uIGsuIFRoZSBZYW5nIEh1aSBUcmlhbmdsZSBoYXMgYSByZWd1bGFyIHBhdHRlcm4gYXMgZm9sbG93cy48YnI+CkMobiwwKT1DKG4sbik9MSAobiCh3SAwKSA8YnI+CkMobixrKT1DKG4tMSxrLTEpJiM0MztDKG4tMSxrKSAoMDxrPG4pPGJyPgpXcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBtaW5pbXVtIHN1bSBvZiBudW1iZXJzIHBhc3NlZCBvbiBhIHJvdXRlIHRoYXQgc3RhcnRzIGF0IHRoZSB0b3AgYW5kIGVuZHMgYXQgcm93IG4sIGNvbHVtbiBrLiBFYWNoIHN0ZXAgY2FuIGdvIGVpdGhlciBzdHJhaWdodCBkb3duIG9yIGRpYWdvbmFsbHkgZG93biB0byB0aGUgcmlnaHQgbGlrZSBmaWd1cmUgMi48YnI+CkFzIHRoZSBhbnN3ZXIgbWF5IGJlIHZlcnkgbGFyZ2UsIHlvdSBvbmx5IG5lZWQgdG8gb3V0cHV0IHRoZSBhbnN3ZXIgbW9kIHAgd2hpY2ggaXMgYSBwcmltZS4KCiAKPGJyPgoKSW5wdXQKCklucHV0IHRvIHRoZSBwcm9ibGVtIHdpbGwgY29uc2lzdHMgb2Ygc2VyaWVzIG9mIHVwIHRvIDEwMDAwMCBkYXRhIHNldHMuIEZvciBlYWNoIGRhdGEgdGhlcmUgaXMgYSBsaW5lIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIG4sIGsoMDw9azw9bjwxMF45KSBwKHA8MTBeNCBhbmQgcCBpcyBhIHByaW1lKSAuIElucHV0IGlzIHRlcm1pbmF0ZWQgYnkgZW5kLW9mLWZpbGUuCgogCjxicj4KCk91dHB1dAoKRm9yIGV2ZXJ5IHRlc3QgY2FzZSwgeW91IHNob3VsZCBvdXRwdXQg"Case #C: " first, where C indicates the case number and starts at 1.Then output the minimum sum mod p.

Sample Input

1 1 2
4 2 7

Sample Output

Case #1: 0
Case #2: 5

Author phyxnj@UESTC
Source 2011 Multi-University Training Contest 11 - Host by UESTC

#include 
#include 
#include 
#include 

using namespace std;

typedef long long int LL;

LL n,k,p;

LL fact[1300][11000];

LL QuickPow(LL x,LL t,LL m)
{
	if(t==0) return 1LL;
	LL e=x,ret=1LL;
	while(t)
	{
		if(t&1LL) ret=(ret*e)%m;
		e=(e*e)%m;
		t>>=1LL;
	}
	return ret%m;
}

int prime[2000],pr;
bool vis[10100];

void get_prime()
{
	for(int i=2;i<10100;i++)
	{
		if(vis[i]==false)	
			prime[pr++]=i;
		for(int j=2*i;j<10100;j+=i)
			vis[j]=true;
	}
}

void get_fact()
{
	for(int i=0;i<1240;i++)
	{
		fact[i][0]=1LL;
		for(int j=1;j<=prime[i]+10;j++)	
		{
			fact[i][j]=(fact[i][j-1]*j)%prime[i];	
		}
	}
}

LL Lucas(LL n,LL m,LL p)
{
	LL ret=1LL;
	int id=lower_bound(prime,prime+pr,p)-prime;
	while(n&&m)
	{
		LL a=n%p,b=m%p;
		if(an/2) k=n-k;
		LL ans=(Lucas(n+1,k,p)+n-k)%p;
		printf("Case #%d: %I64d\n",cas++,ans);
	}
	return 0;
}