首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#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>
这道题暂未补解析。