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.2cto.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(a
      
       n/2) k=n-k; LL ans=(Lucas(n+1,k,p)+n-k)%p; printf("Case #%d: %I64d\n",cas++,ans); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：UVA 10465 Homer Simpson（贪心，..	下一篇：HDU2602Bone Collector

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: