AtCoder ABC446_E: E - Multiple-Free Sequences Editorial

789 字

4 分钟

AtCoder ABC446_E: E - Multiple-Free Sequences Editorial

2026-03-07

次阅读

算法

AtCoder

/

算法

题目链接#

https://atcoder.jp/contests/abc446/tasks/abc446_e

题目大意#

给定三个整数 M, A, B。

对于任意初始二元组 (x, y)，其中 0 <= x, y < M，构造无限序列：

s_1 = x
s_2 = y
s_n = A s_{n-1} + B s_{n-2}（n >= 3）

要求统计有多少组 (x, y)，能使这个无限序列中 不存在任何一项是 M 的倍数。

也就是说，序列里不能出现满足 s_n mod M = 0 的项。

输出满足条件的初始二元组数量。

解题思路#

先把问题放到模 M 的意义下来看。

因为我们只关心某一项是否是 M 的倍数，所以只需要考虑每一项对 M 取模后的结果。于是每个数都可以看成 0 ~ M-1 之间的值。

设当前连续两项为 (u, v)，那么下一项就是：

next = (A * v + B * u) mod M

因此状态 (u, v) 会转移到：

(v, (A * v + B * u) mod M)

也就是说，我们可以把“连续两项”当成图上的一个点。由于 u, v 都只有 M 种取值，所以总状态数只有 M^2 个。

如果某个状态中有一项为 0，那么就说明序列里已经出现了 M 的倍数，因此这类状态都是坏状态。代码里直接把 (u, v) 中满足 u = 0 或 v = 0 的状态全部作为起点。

题目要求的是：有多少个初始状态 (x, y)，在不断转移后永远不会走到坏状态。

正向去判断每个起点会不会走到坏状态不太方便，但这个图的转移关系很规整，所以更适合反向建图。

如果正向有：

(i, j) -> (j, (A * j + B * i) mod M)

那么反向边就是：

(j, (A * j + B * i) mod M) -> (i, j)

这正对应代码中的：

1
ll k = (i * b + j * a) % m;
2
g[j * m + k].push_back(i * m + j);

接下来从所有坏状态出发，在反图上做一遍 BFS。这样所有能够被访问到的状态，都是“最终能走到坏状态”的状态，也就是不合法的初始状态；而没有被访问到的状态，就是答案。

最后统计所有没有被标记的 (x, y) 个数即可。

复杂度分析#

状态数为 M^2
每个状态恰好连出一条正向边，因此反图边数也是 M^2

所以总时间复杂度为 O(M^2)，空间复杂度也为 O(M^2)。

代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N=1010;
4
typedef long long ll;
5
ll m, a, b;
6
vector<ll> g[N*N];//建图
7
queue<ll> q;
8
bool st[N*N];//判断是不是会达到0的点
9
int main(){
10
    scanf("%lld%lld%lld", &m, &a, &b);
11
    for(int i=0;i<m;i++){
12
        for(int j=0;j<m;j++){
13
            //(i, j)<-(j, i*b+j*a)
14
            ll k=(i*b+j*a)%m;//反向建图
15
            g[j*m+k].push_back(i*m+j);//将二维的点压成一维(i, j)->i*m+j
16
        }
17
    }
18
    for(ll i=0;i<m;i++){
19
        for(ll j=0;j<m;j++){
20
            if(i==0||j==0){//凡是带0的, 都是不行的点, 都要计算其位置
21
                ll v=i*m+j;
22
                st[v]=true;
23
                q.push(v);//多源bfs
24
            }
25
        }
26
    }
27
    while(!q.empty()){
28
        ll t=q.front();
29
        q.pop();
30
        for(ll u:g[t]){
31
            if(!st[u]){//凡是被bfs遍历到的, 都是能变成%M==0的点, 都会被加入
32
                st[u]=true;
33
                q.push(u);
34
            }
35
        }
36
    }
37
    ll res=0;
38
    for(ll i=0;i<m;i++){
39
        for(ll j=0;j<m;j++){
40
            if(st[i*m+j]==0) res++;//st值为false的, 是答案, 要++
41
        }
42
    }
43
    printf("%lld\n", res);
44
    return 0;
45
}