【例67.2】 昆虫繁殖

解题思路

按月份维护成虫A与当月卵E。初始第1月A=1。第i月成虫为上月成虫加两个月前的卵；当月能产卵的成虫来自i-x月，所以E[i]=A[i-x]×y。过z个月对应初始之后的第z+1月。

正确性说明

成虫不会死亡，只可能由成熟卵增加；产卵延迟与卵成熟延迟分别由两个下标体现。每月都根据更早月份的已知事实计算，因此归纳得各月份成虫总数。

易错点

先更新成虫再计算本月卵；卵不是成虫；用十进制大整数防止快速繁殖溢出。

复杂度

z月、最大D位，时间O(zD)，空间O(zD)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

string plusBig(string a, string b) {
    string s;
    int i = a.size() - 1, j = b.size() - 1, c = 0;
    while (i >= 0 || j >= 0 || c) {
        int v = c;
        if (i >= 0)
            v += a[i--] - '0';
        if (j >= 0)
            v += b[j--] - '0';
        s += char('0' + v % 10);
        c = v / 10;
    }
    reverse(s.begin(), s.end());
    return s;
}
string timesSmall(string s, int k) {
    int c = 0;
    for (int i = s.size() - 1; i >= 0; i--) {
        int v = (s[i] - '0') * k + c;
        s[i] = char('0' + v % 10);
        c = v / 10;
    }
    while (c) {
        s = char('0' + c % 10) + s;
        c /= 10;
    }
    return s;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int x, y, z;
    cin >> x >> y >> z;
    vector<string> A(z + 3, "0"), E(z + 3, "0");
    A[1] = "1";
    for (int i = 2; i <= z + 1; i++) {
        A[i] = plusBig(A[i - 1], i >= 3 ? E[i - 2] : "0");
        if (i > x)
            E[i] = timesSmall(A[i - x], y);
    }
    cout << A[z + 1] << "\n";
    return 0;
}