A. 牛牛的 Fib 序列
题目形容
牛牛从新定义了斐波那契数列，牛牛定义 $f(n) = f(n-1) + f(n+1), f(1) = a, f(2) = b$，当初给定初始值 $a, b$，当初求第 $n$ 项 $f(n) \mod 1000000007$ 的值。
其中 $1 \le |a|, |b|, n \le 10^9$
输出
a,b,n输入
f(n) % 1000000007备注:
最终的答案应是一个非负整数，如 -1 % 1000000007 = 1000000006示例 1
输出
1, 2, 3输入
1阐明
f(2) = f(3) + f(1), 所以 f(3) = f(2) - f(1) = 2 - 1 = 1示例 2
输出
-1, -2, 3输入
1000000006阐明
同例 1：f(3)= -1 % 1000000007 = 1000000006解法
思路剖析
手写一下前几个数，就会发现这个数列 6 个数一循环。
工夫复杂度：O(1)
空间复杂度：O(1)
代码实现
public int solve (int a, int b, int n) {
final int mod = 1000000007;
int[] fib = new int[]{a, b, (b - a) % mod, -a, -b, (a - b) % mod};
return (fib[(n - 1) % 6] + mod) % mod ;
}B. 破译明码
题目形容
题面：
牛牛收到了一个工作，工作要求牛牛破译一个明码。牛牛将被给予两个字符串 s1 和 s2，均由四个小写字母形成。须要破译的明码为从 s1 变换到 s2 起码须要的变换次数。
变换的形式是这样：每次变换能够抉择以后字符串中的一个地位，而后剩下的三个地位的字符从左到右别离加上 2，3，5，若是超出 ‘z’，则从新从 ‘a’ 开始，例如：对于字符串 “abcd”，咱们抉择 ‘c’ 的地位进行变换，则变换之后的字符串为 “ceci”; 对于字符串 “qyzr”, 咱们抉择 ‘r’ 地位进行变换，则变换之后的字符串为 “sber”。
输出
s1, s2输入
s1 变换到 s2 起码须要的变换次数备注:
s1, s2 均由四个小写字母组成示例 1
输出
"aaaa", "ccgk"输入
2阐明
第一次变换抉择第一个 'a'，变成 "acdf"，第二次变换抉择第二个 'c'，变成 "ccgk"，故答案为 2 解法一：BFS
思路剖析
在之前的文章中，【魔法数字】一题也用到了 BFS。本题和那题的思路统一。穷举所有变换的可能性，通过备忘录剪枝来缩小搜寻空间。
对每一个字符串都有四种变换状况，即抉择第 $i$ 位 $(0 \le i \le 3)$ 进行变换。
这里能够自行画一下四叉树，更能直观的领会这种办法的流程。（才不是因为我懒得画图，【逃】）
第一次变换到 s2 的那一层 j，即为起码变换次数。（根节点 s1 所在层为 0）
工夫复杂度：$O(log_426^4)$. 最坏状况下把所有字符串 ($26^4$ 个) 都搜寻了一遍。
空间复杂度：$O(26^4)$. 额定空间次要是备忘录和队列的空间开销，最坏状况下把所有字符串都存进去了。
代码实现
int[] add = new int[] {2,3,5};
public int solve(String s1, String s2) {Set<String> visited = new HashSet();
Queue<String> q = new LinkedList();
q.offer(s1);
int res = 0;
while(!q.isEmpty()) {int size = q.size();
while(size-- > 0) {String cur = q.poll();
if(cur.equals(s2)) return res;
if(visited.contains(cur)) continue;
visited.add(cur);
for(int i = 0; i < 4; i++) q.offer(convert(cur,i));
}
res++;
}
return res;
}
public String convert(String s, int i) {char[] str = s.toCharArray();
int index = 0;
for(int j = 0; j < 4; j++) {if(j == i) continue;
str[j] = (char)('a' + (str[j] - 'a' + add[index]) % 26);
index++;
}
return String.valueOf(str);
}解法二：数学方法
思路剖析
因为 s1 到 s2 的间隔为固定值，因而能够用数组 dis[4] 记录四位字符别离的间隔。
记 a, b, c, d 别离为抉择第 i (0 <= i <= 3) 位字符的次数。以下四个公式成立，即可阐明这种状况下能够从 s1 变换到 s2：
$2 * (b + c + d) \mod 26 = dis[0]$
$(2 * a + 3* (c + d)) \mod 26 = dis[1]$
$(3 * (a + b) + 5 * d) \mod 26 = dis[2]$
$5 * (a + b + c) \mod 26 = dis[3]$
所需变换次数为 $cnt = a + b + c + d$，取其中后果最小的即可。
代码实现
public int solve (String s1, String s2) {int[] dis = new int[4];
for(int i = 0; i < 4; i++) dis[i] = (s2.charAt(i) - s1.charAt(i) + 26) % 26;
int res = 26 * 4;
for(int a = 0; a < 26; a++)
for(int b = 0; b < 26; b++)
for(int c = 0; c < 26; c++)
for(int d = 0; d < 26; d++)
if(dis[0] == 2 * (b + c + d) % 26 && dis[1] == (2 * a + 3* (c + d)) % 26 && dis[2] == (3 * (a + b) + 5 * d) % 26 && dis[3] == 5 * (a + b + c) % 26)
res = Math.min(res, a + b + c + d);
return res;
}C. 卡牌问题
问题形容
有 $n * m$ 张牌叠在一起，称之为旧牌库。
牌由旧牌库底部的第一张从 1 开始编号，旧牌库顶的牌编号就是 $n*m$.
每张牌上有一个数字，设编号为 $i$ 的牌上的数字为 $a[i]$, 保障满足 $a[i] = ((i – 1) \mod m) + 1$。
现给出 $a$ 和 $b$，进行两个操作：
1、每次将旧牌库最底下的一张牌拿进去，放到旧牌库顶，反复 $a$ 次。
2、建一个新牌库，初始新牌库没有卡牌，每次先将旧牌库最底下的牌拿进去，放在新牌库顶，再将旧牌库最顶上的牌拿进去，放到新牌库顶，反复 $b$ 次，保障 $2*b \le n*m$，最初将旧牌库所有残余卡牌间接放到新牌库顶。
再给出数字 $x$ 和 $y$，求新牌库从牌库底起第 $x$ 张牌到第 $y$ 张牌上的数字之和。
这个答案可能很大，输入答案对 998244353 取模后的后果。
备注:
输出蕴含 6 个整数 n, m, a, b, x, y，且保证数据肯定非法可行。输入一行，一个整数。n <= 1e9; m <= 1e5; a <= n * m; b * 2 <= n * m; x <= y <= n * m示例 1
输出
4, 5, 17, 6, 3, 14输入
39示例 2
输出
2, 3, 4, 1, 2, 5输入
7解法：前缀和
思路剖析
乍看本题的小伙伴可能一头雾水，待 本汪 花 3 分钟细细解说之后，小学生也能做进去！
咱们先剖析新牌堆是什么样的，晓得它长啥样，之后的计算思路就高深莫测了。
依题意，原牌堆 自底向上 看牌上数字是这样一个序列：$(1, 2, …, m)^n$。
通过操作 1 之后，变成了牌堆 A，序列为：$s_1, s_1 + 1, …, m, (1, 2, …, m)^{n-1}, 1, 2, …, s_1-1$。其中 $s_1 = a \mod m + 1$。
对牌堆 A 进行操作 2 之后，失去新牌堆。新牌堆可分成两个序列：$B_1,B_2$。
首先看 $B_1$，它蕴含了 $2b$ 张牌，并且奇数牌和偶数牌的法则如下：
- 奇数牌：自底向上的第 $2k – 1$ 张牌，对应牌堆 A 自底向上 的第 $k$ 张牌。
- 偶数牌：自底向上的第 $2k$ 张牌，对应牌堆 A 自顶向下 的第 $k$ 张牌。
$B_2$ 就很简略了，序列为：$s_2, s_2 + 1, …, m, 1, 2, …, m, 1, 2, …$。其中 $s_2 = (s_1 – 1 + b) \mod m + 1$。
当初晓得新牌堆长什么样了，很显然 $B_2$ 的局部和是很好计算的。
$B_1$ 相当于牌堆 A 前向和后向各数了 b 张牌。因而用 前缀和 + 后缀和 便能够计算出 $B_1$ 的局部和。
到这里，相熟 前缀和 的小伙伴就能够本人入手写代码体验 AC 的快感了。不相熟 前缀和 的小伙伴也别放心，贴心的 往西汪 只用 1 分钟就能给你讲的明明白白。
给定参数 $st, l$，别离代表序列的初始数字，和序列的长度。
- 前缀和，计算序列 $st, st + 1, …, m, 1, 2, …, m, 1, 2, …$ 的和。
- 后缀和，计算序列 $st, st − 1, …, 1, m, m−1, …, 1, m, m−1, …$ 的和。
针对序列 $B_1$，记 $sum(x)$ 示意区间 $[1, x]$ 的牌的数字和，$sum(x) = 前缀和(st = s_1, l = ⌈r/2⌉) + 后缀和(st = s_1 – 1, l = ⌊r/2⌋)$。
区间 $[x_1, x_2]$ 的和为：$sum(x_2) – sum(x_1 – 1)$。
至此本题再无难度。
代码实现
class Solution {
long m;
final long mod = 998244353;
public long work (long n, long m, long a, long b, long x, long y) {
this.m = m;
long res = 0;
long s1 = a % m + 1, s2 = (s1 - 1 + b) % m + 1;
if(x <= 2 * b){res = modAdd(res, mod - b1Sum(s1, x - 1));
res = modAdd(res, b1Sum(s1, Math.min(2 * b, y)));
}
if(y > 2 * b){res = modAdd(res, mod - b2Sum(s2, Math.max(2 * b, x - 1) - 2 * b));
res = modAdd(res, b2Sum(s2, y - 2 * b));
}
return res;
}
public long addTo(long l, long r){// 计算 [l, r] 的区间和
if(r < l) return 0;
return ((l + r) * (r - l + 1) >> 1) % mod;
}
public long modAdd(long n1, long n2){return (n1 + n2) < mod ? (n1 + n2) : (n1 + n2 - mod);
}
public long preSum(long st, long l){// 这里的 l 示意序列长度
if(l <= 0) return 0;
if(l <= m - st + 1) return addTo(st, st + l - 1);
long k = (l - (m - st + 1)) / m;
long end = (l - (m - st + 1)) % m;
long res = modAdd(addTo(st, m), addTo(1, end));
return modAdd(res, (k * addTo(1, m)) % mod);
}
public long backSum(long st, long l){if(l <= 0) return 0;
if(l <= st) return addTo(st - l + 1, st);
long k = (l - st) / m;
long end = m - ((l - st) % m) + 1;
long res = modAdd(addTo(1, st), addTo(end, m));
return modAdd(res, (k * addTo(1, m)) % mod);
}
public long b1Sum(long s1, long l){// l 示意序列长度
if(l <= 0) return 0;
long half = l >> 1;
return modAdd(preSum(s1, l - half), backSum(s1 - 1, half));
}
public long b2Sum(long s2, long l){if(l <= 0) return 0;
return preSum(s2, l);
}
}写在最初
大家好，我是往西汪，一位保持原创的新人博主。
如果本文对你有帮忙，请点赞、评论二连。你的反对是我创作路上的最大能源。
谢谢大家！
也欢送来公众号【往西汪】找我游玩～