【2020年杭电暑假第二场】6768 The Oculus

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6768

题意

一个斐波那契数列，每一位是可取或不可取，这取决于输入的b的大小，为0不可取，为1可取，这可以称为广义斐波那契数列。 给A、B、C的广义斐波那契数列，使得C = Ａ＊Ｂ，然后改变Ｃ中数列中的一个bi使其从1变为0，并把这三个数列给你，问C中是第几bi改变了，输出它。

思路

首先预处理2e6以内的斐波那契数字，记得要mod，但是标准答案没有mod，导致longlong开的数字溢出变为负数，但也能过，可能是数据太弱了。

然后输入A和B和C，把b=1的位置累加并且mod，本来C = A * B，然后改了一个位置，所以就变成C+bi=A*B，所以只要找到这个bi后输出他在C中的位置即可。

但是越往后的斐波那契数字，mod一个数后可能相同，就不好判断了到底该取哪一个位置，这时候就要利用斐波那契编码的性质：斐波那契编码。

斐波那契编码性质，除了最后两位都是1以外，任意相邻位置的编码乘积都为0，就是不可能在由11这一对，所以在判断bi时候要判断一下他更改的位置是否合法。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x7f7f7f
##define mem(a,b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

const ll mod = 998244353;
// const int maxn = 1e5;
// const double eps = 1e-6;

ll vis[2000010];
bool f[2000010];

void init()
{
    vis[1] = 1;
    vis[2] = 2;
    for (int i = 3; i <= 2000001; i++)
    {
        vis[i] = (vis[i - 1] + vis[i - 2]) % mod;
    }
}

void solve()
{
    ll a, bb, c;
    int b;
    ll A = 0, B = 0, C = 0;
    scanf("%lld", &a);
    for (int i = 1; i <= a; i++)
    {
        scanf("%d", &b);
        if (b)
            A = (A + vis[i]) % mod;
    }
    scanf("%lld", &bb);
    for (int i = 1; i <= bb; i++)
    {
        scanf("%d", &b);
        if (b)
            B = (B + vis[i]) % mod;
    }
    A = A * B % mod;
    scanf("%lld", &c);
    f[0] = 0;
    f[c + 1] = 0;
    for (int i = 1; i <= c; i++)
    {
        scanf("%d",&f[i]);
        if (f[i])
            C = (C + vis[i]) % mod;
    }
    for (int i = 1; i <= c; i++)
    {
        if (f[i] == 0 && f[i + 1] == 0 && f[i - 1] == 0) // 判断位置是否合法
        {
            if ((vis[i] + C) % mod == A) // 判断bi
            {
                printf("%d\n", i);
                return;
            }
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
   // freopen("in.txt", "r", stdin);
   // freopen("out.txt", "w", stdout);
##else
    ios::sync_with_stdio(false);
    int T = 1;
    scanf("%d",&T);
    init();
    while (T--)
        solve();
##endif
    return 0;
}

赛后感谢牌王的亲切指导

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/07/23/hdu-6768/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！