Kattis

Kattis - barcode

题目原文：

To prepare for ACM-ICPC 2017 in Saigon, the host univeristy – Ho Chi Minh city University of Education (HCMUE) – decided to print barcodes on the participants’ t-shirts. The barcode requirement needs to be simple to reduce the cost but still show some scientific style. HCMUE decided that every barcode consists of red bars and blue bars satisfing at least one of the following conditions:

l The number of blue bars is equal to the number of red bars.

l There are no 22 consecutive blue bars.

Let K denote the number of different ways to create the required barcodes containing N bars. Given two integers N and M, where M is a prime number, your task is to help them identify the remainder of K divided by M.

Input

The input consists of several datasets. The first line of the input contains the number of datasets, which is a positive number and is not greater than 20. Each dataset is described by one line containing two numbers N and M (1≤N≤10⁶,1<M≤10⁷). M is a prime number.

Output

For each dataset, write in one line the remainder of K divided by M.

题目大意：

为一个长度为n的条形码制定一个涂色方案（红色和蓝色两种），要求满足下列条件之一：

红色和蓝色数量相等
蓝色条形码不连续

输出方案数（对素数M取余）

题目解析：

对于给出的样例很容易发现这是个Fibnaci数列的一部分，但是如果写出当N=4时的情况，发现结果为11，不是Fibnaci预期中的8。如果你继续验证会发现，当N为奇数时，结果是个Fibnaci数，当N为偶数，总比Fibnaci数大。
偶数与奇数的不同是偶数可以整除2，也就是偶数可以满足第一种情况，而奇数不可以；打表或者自己写出当N=4,6,8的情况，也可以验证多出的数字就是当红色等于蓝色时，条形码连续的情况。（注意当颜色相同时，也会有蓝色条形码不连续的情况，根据结果。这时默认是符合第二种情况的）
只需计算这个数即可。

　　　　得：数量相等且连续 = 数量相等 - 数量相等且不连续；

　　　　利用组合数： ans = C(n,n/2) - C(n/2+1,n/2)

　　　　　　　　　　　　 = C(n,n/2) - C(n/2+1,1)

　　　　　　　　　　　　 = C(n,n/2) - n/2 - 1

　　　　当N为奇数 res = F[n]%M（不是完整的Fibnaci，要从F[1] = 2,F[2] = 3开始计算）

　　　　当N为偶数 res = (F[n] + ans)%M

　　　　程序涉及了Lucas定理和逆元

　　　参考博客：https://www.cnblogs.com/fzl194/p/9095177.html

　　　　　　　　 https://www.cnblogs.com/scx2015noip-as-php/p/lucas.html

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 1e6 + 5;
 5 LL f[maxn];
 6 template<typename T>
 7 T pow_mod(T a,T b,T c)
 8 {
 9     T ans = 1;
10     a %= c;
11     while(b)
12     {
13         if(b&1) ans = (ans*a)%c;
14         b >>= 1;
15         a = (a*a)%c;
16     }
17     return ans;
18 }
19 template<typename T>
20 T inv(T x,T p)
21 {
22     return pow_mod(x,p-2,p);
23 }
24 template<typename T>
25 T C(T n,T m,T p)
26 {
27     if(m > n) return 0;
28     if(m == 0||m == n) return 1;
29     if(m == 1||m == n-1) return n;
30     m = min(m,n-m);
31     T up = 1,down = 1;
32     for(int i=n-m+1;i<=n;i++) up = (up*i)%p;
33     for(int i=1;i<=m;i++) down = (down*i)%p;
34     return (up * inv(down,p))%p;
35 }
36 template<typename T>
37 T Lucas(T n,T m,T p)
38 {
39     if(m == 0) return 1;//边界
40     return (Lucas(n/p,m/p,p) * C(n%p,m%p,p))%p;
41 }
42 //同下
43 //template<typename T>
44 //T Lucas(T n,T m,T p)
45 //{
46 //    T ans = 1;
47 //    while(m)
48 //    {
49 //        ans = (ans * C(n%p,m%p,p))%p;
50 //        n /= p;
51 //        m /= p;
52 //    }
53 //    return ans;
54 //}
55 LL Fibnaci(LL n,LL mod)
56 {
57     f[1] = 2;
58     f[2] = 3;
59     for(int i=3;i<=n;i++)
60         f[i] = (f[i-1] + f[i-2])%mod;
61     return f[n];
62 }
63 
64 int main()
65 {
66     int T;
67     LL n,m;
68     scanf("%d",&T);
69     while(T--)
70     {
71         scanf("%lld%lld",&n,&m);
72         if(n & 1)
73         {
74             cout << Fibnaci(n,m) << endl;
75         }
76         else
77         {
78             cout << (((Fibnaci(n,m) + Lucas(n,n/2,m) - (n/2 + 1))%m)+m)%m << endl;
79         }
80     }
81     return 0;
82 }