vijosP1289 老板娘的促销方案

vijosP1289 老板娘的促销方案

链接:https://vijos.org/p/1289

【思路】

  组合公式+高精度。

  如果n-m<2则无解。 

  否则对于第一个询问:ans=C(n-m,2)+C(n-m,3)=C(n-m+1,3)。对于第二个询问:

  由此可见,对于递推式的化简也是很重要的,可以有效简化求解。

不管有没有陷阱,反正我用高精度=_=。高精度一定要写熟练,如臂指使。

【代码】

 1 #include<iostream>
 2 using namespace std;
 3 struct Bign{
 4     int len;
 5     long long N[101];
 6     Bign() {
 7         for(int i=0;i<101;i++) N[i]=0;
 8     }
 9 };
10 int n,m;
11 
12 void multi(Bign& a,int x)
13 {
14     for(int j=0;j<a.len;j++) a.N[j] *= x;
15     int i=0;
16     while(i<a.len || a.N[i]>10) {
17         a.N[i+1] += a.N[i]/10;
18         a.N[i] %= 10;
19         i++;                    //i++
20     }
21     if(a.N[i]) a.len=i+1;
22     else a.len=i;
23 }
24 
25 void div(Bign& a,int x) {
26     for(int i=a.len-1;i>0;i--) {
27         a.N[i-1] += a.N[i]%x*10;
28         a.N[i] /= x;
29     }
30     while(a.N[a.len-1]==0) a.len--;
31     a.N[0]/=x;
32 }
33 
34 int main() {
35     Bign C; C.len=1; C.N[0]=1;
36      
37     cin>>n>>m;
38     if(n-m<2) cout<<"NO!
";
39     else  
40     {
41             int k=n-m+1;
42             for(int i=k-2;i<=k;i++) multi(C,i);
43             div(C,6);
44             for(int i=C.len-1;i>=0;i--) cout<<C.N[i];
45             cout<<"
";
46     }
47     Bign C2; C2.len=1; C2.N[0]=1;
48     for(int i=n-2;i<=n+1;i++) multi(C2,i);
49     div(C2,24);
50     
51     if(C2.N[0]==0) {
52         C2.N[1]--;
53         C2.N[0]+=10;
54     }
55     C2.N[0]-=1;
56     for(int i=1;i<C2.len;i++) if(C2.N[i]<0) {
57         C2.N[i]+=10;
58         C2.N[i+1]--;
59     }
60     for(int i=C2.len-1;i>=0;i--) cout<<C2.N[i];
61     return 0;
62 }
原文地址:https://www.cnblogs.com/lidaxin/p/4875595.html