# B - Barcode Kattis - barcode （组合数）（模意义下的组合数模板）

2019/06/19 10:51

## 题目链接：

https://cn.vjudge.net/problem/Kattis-barcode

## 具体思路：

`````` 1 ll fact[maxn];
2 ll qsm(ll t1,ll t2,ll mod)
3 {
4     ll ans=1ll;
5     while(t2)
6     {
7         if(t2&1)
8             ans=ans*t1%mod;
9         t2>>=1;
10         t1=t1*t1%mod;
11     }
12     return ans%mod;
13 }
14 ll mod_fact(ll n, ll p, ll &e)
15 {
16     if (n<=1)
17         return 1;
18     ll ret=mod_fact(n/p, p, e);
19     e+=n/p;
20     if ((n/p) &1)
21         return ret*(fact[n%p]*(p-1)%p)%p;
22     else
23         return ret*fact[n%p]%p;
24     /* (p-1)!=-1(mod p) */
25 }
26 ll calc_C(ll n, ll k, ll p)
27 {
28     ll e1=0, e2=0, e3=0;
29     ll a1=mod_fact(n, p, e1);
30     ll a2=mod_fact(k, p, e2);
31     ll a3=mod_fact(n-k, p, e3);
32     if (e1-(e2+e3)>0)
33         return 0;
34     return (a1*qsm(a2*a3%p, p-2, p)%p);
35 }
36 void init(int n,int p)
37 {
38   fact[1]=fact[0]=1ll;
39         for(ll i=2; i<=n; i++)
40         {
41             fact[i]=(fact[i-1]*i)%p;
42         }
43 }``````
View Code

AC代码：

`````` 1 #include<bits/stdc++.h>
2 using namespace std;
3 # define ll long long
4 # define inf 0x3f3f3f3f
5 # define LL_inf (1ll<<60)
6 const int maxn = 2e6+100;
7 ll dp[maxn][2];
8 ll fact[maxn];
9 ll qsm(ll t1,ll t2,ll mod)
10 {
11     ll ans=1ll;
12     while(t2)
13     {
14         if(t2&1)
15             ans=ans*t1%mod;
16         t2>>=1;
17         t1=t1*t1%mod;
18     }
19     return ans%mod;
20 }
21 ll mod_fact(ll n, ll p, ll &e)
22 {
23     if (n<=1)
24         return 1;
25     ll ret=mod_fact(n/p, p, e);
26     e+=n/p;
27     if ((n/p) &1)
28         return ret*(fact[n%p]*(p-1)%p)%p;
29     else
30         return ret*fact[n%p]%p;
31     /* (p-1)!=-1(mod p) */
32 }
33 ll calc_C(ll n, ll k, ll p)
34 {
35     ll e1=0, e2=0, e3=0;
36     ll a1=mod_fact(n, p, e1);
37     ll a2=mod_fact(k, p, e2);
38     ll a3=mod_fact(n-k, p, e3);
39     if (e1-(e2+e3)>0)
40         return 0;
41     return (a1*qsm(a2*a3%p, p-2, p)%p);
42 }
43 int main()
44 {
45     int T;
46     scanf("%d",&T);
47     while(T--)
48     {
49         ll n,p;
50         scanf("%lld %lld",&n,&p);
51         fact[1]=fact[0]=1ll;
52         for(ll i=2; i<=n; i++)
53         {
54             fact[i]=(fact[i-1]*i)%p;
55         }
56         dp[1][0]=1ll;
57         dp[1][1]=1ll;
58         for(int i=2; i<=n; i++)
59         {
60             dp[i][0]=(dp[i-1][0]+dp[i-1][1])%p;
61             dp[i][1]=dp[i-1][0]%p;
62         }
63         ll ans=(dp[n][0]+dp[n][1])%p;
64         if(n%2==0)
65         {
66             ans+=calc_C(n,n/2,p)%p;
67             ans%=p;
68             ans-=calc_C(n/2+1,n/2,p);
69         }
70         while(ans<0)
71             ans+=p;
72         ans%=p;
73         printf("%lld\n",ans);
74     }
75     return 0;
76 }``````

0
0 收藏

0 评论
0 收藏
0