简答题
偏难
#7559
红蓝串 小红有两条珠串,一条有 A 只红色珠子,另一条有 B 只蓝色珠子。她想用下列步骤做一条红蓝珠子的串: - 她会从两条珠串上一步一步地取下珠子。 - 第…
红蓝串
小红有两条珠串,一条有 A 只红色珠子,另一条有 B 只蓝色珠子。她想用下列步骤做一条红蓝珠子的串:
- 她会从两条珠串上一步一步地取下珠子。
- 第 i 步时,她会从一条珠串上取下 i 颗珠子,穿到结果串上。
- 她最后要得到一条有 n 颗珠子的串。
小红有可能得到多少种不同的结果呢?
如果小红在至少某一步中选择了不同颜色的串来取珠子,那么两条结果串就被认为是不同的。
时间限制:6000
内存限制:262144
输入
输入在一行中给出 3 个整数:n (0 < n ≤ 2 × 105)、A、B (0≤ A, B ≤ 105),其定义如题面所述。
输出
在一行中输出小红有可能得到多少条有 n 颗珠子的串。因为结果可能是很大的数字,所以你要输出对 1000000007 (109 + 7) 取模后的结果。
样例输入
10 4 7
样例输出
4
提示
小红能得到的 4 种不同的结果如下图所示。

答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int MOD = 1000000007;
int main() {
long long n, A, B;
cin >> n >> A >> B;
long long D = 8 * n + 1;
long long m = sqrt(D);
if (m * m != D || m % 2 == 0) {
cout << 0 << endl;
return 0;
}
long long k = (m - 1) / 2;
long long low = max(n - B, 0LL);
long long high = min(A, n);
if (low > high) {
cout << 0 << endl;
return 0;
}
vector<long long> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= k; ++i) {
for (int s = n; s >= i; --s) {
dp[s] = (dp[s] + dp[s - i]) % MOD;
}
}
long long ans = 0;
for (int s = low; s <= high; ++s) {
ans = (ans + dp[s]) % MOD;
}
cout << ans << endl;
return 0;
}</pre>
这道题暂未补解析。