#include <iostream>#include <cstring>using namespace std;const int N = 1e6 + 10, MOD = 1e9 + 7;int n;int dp[N];int main(){ cin >> n; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i ++) dp[i] = (dp[i - 1] + dp[i - 2]) % MOD; cout << dp[n] << endl; return 0;}请将这段代码时间复杂度降低并展示给我

这段代码已经是 $O(n)$ 的时间复杂度，不过可以使用滚动数组进一步优化空间复杂度，将空间复杂度降为 $O(1)$。如下所示：

#include <iostream>
#include <cstring>
using namespace std;

const int MOD = 1e9 + 7;

int n;
int a = 1, b = 1, c;

int main() {
    cin >> n;
    if (n == 0) cout << 1 << endl;
    else if (n == 1) cout << 1 << endl;
    else {
        for (int i = 2; i <= n; i++) {
            c = (a + b) % MOD;
            a = b;
            b = c;
        }
        cout << b << endl;
    }
    return 0;
}

在这个版本中，我们只使用了三个变量 a、b 和 c，避免了使用数组来存储所有的 dp 值，从而将空间复杂度降低为 $O(1)$。

相关问题

#include<cstdio>#include<vector>#include<iostream>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;typedef unsigned long long ull;const int maxn = 1e6 + 10;const int inf = 0x3f3f3f3f;const int mod = 1e9 + 7;const int base = 998544323;ull a[maxn];char s[maxn];vector<ull> v; int main(){ int n, m; scanf("%d%d", &n, &m); scanf("%s", s); ull p = 1e9 + 9, r = 1, h = 0; int len = strlen(s); for(int i = 0; i < n && i < len; i++) // 计算出前n位 h = h * p + s[i], r *= p; if(len >= n) // 该串长度大于n， 加进去 v.push_back(h); for(int i = n; i < len; i++) h = h * p + s[i] - s[i - n] * r, v.push_back(h);// 计算其他串的hash值 sort(v.begin(), v.end()); int tot = unique(v.begin(), v.end()) - v.begin(); printf("%d\n", tot); return 0;}

这段代码是用来计算一个字符串中所有长度为n的子串的哈希值，并统计不同哈希值的个数。

具体的实现方式是：先计算出前n位的哈希值，然后依次计算后面每个长度为n的子串的哈希值，并将哈希值存入vector中。最后对vector进行排序和去重，得到不同哈希值的个数。

其中使用了无符号长整型ull和vector容器，以及STL中的sort和unique函数进行排序和去重操作。

需要注意的是，该算法使用的是字符串哈希方法，需要选取一个合适的哈希函数，比如本代码中使用的是常用的多项式哈希函数。同时，对于哈希冲突的情况，可以采用开放地址法或链表法等解决方案。

我这份求组合数的代码全都输出0是怎么回事？输入为3 2 4 2 5 2 10 5 1000 500 1000 1000 1000 10000 10000 1000 10000 5000 40000 20000#include <iostream> #include <cstring> using namespace std; typedef __int128 ll; const int N = 1e5 + 10; const ll mod = 1000000000000000007; int fact[N], infact[N]; int qmi(int a, ll b, ll p) { int res = 1; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; } ll read() { ll x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } void write(ll x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) write(x / 10); putchar(x % 10 + '0'); } int main() { fact[0] = infact[0] = 1; for (int i = 1; i < N; ++ i ) { fact[i] = (ll)fact[i - 1] * i % mod; infact[i] = (ll)infact[i - 1] * qmi(i, mod - 2, mod) % mod; } int T = 10; while ( T -- ) { int a = read(), b = read(); if (a < b) { puts("0"); continue; } ll res = (ll)fact[a] * infact[b] % mod * infact[a - b] % mod; write(res); puts(""); } return 0; }

你的代码中使用了 __int128 类型，这是一个可以存储非常大的整数的数据类型，但是一般的编译器都不支持这个类型。因此，你需要使用一些特殊的编译器或者库来编译这个程序。如果你使用的是普通的编译器，那么代码中的 __int128 类型会被当做未定义的类型，从而导致编译错误。如果你使用了特殊的编译器或者库来编译这个程序，那么可能是你的输入数据有误，导致程序输出了0。建议你检查一下输入数据是否正确。