首页 > 代码库 > SPOJ-ANTP [组合数学]
SPOJ-ANTP [组合数学]
tags:[组合][预处理]
题解：
关于方程A+C+B=X的正整数解组数。
我们用插板法可知，解的组数=在(X-1)个元素中选择两个元素的方案数
故答案为：C(x-1,2)+C(x,2)+C(x+1,2)+...+C(y-1,2)。
因为有多组样例，所以预处理好前缀和即可。
code:
#include <iostream>
using namespace std;
typedef long long LL;
const int NICO = 1000000 + 10;
const int MOD = 1000000007;
int T, x, y;
LL res = 0;
LL ans[NICO];
int main()
{
cin >> T;
for(int i=1;i<NICO;i++)
{
ans[i] = ans[i-1] + (LL)i * (i-1) / 2;
ans[i] %= MOD;
}
while(T--)
{
cin >> x >> y;
x = max(0, x-1);
y = max(0, y-1);
res = (ans[y]-ans[max(x-1,0)]+MOD)%MOD;
cout << res << endl;
}
}
SPOJ-ANTP [组合数学]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。