c++ - a + b + c <= n的解数

大家，这是关于这个问题的参考:http://www.spoj.pl/problems/DCEPC702 /。(请参阅此处以获取示例输入)。我将问题陈述翻译成这样，以找到na + nb + nc <= newN形式的方程的解数
newN = N - (mina + minb + minc)，
0<=na<=maxa - mina, 0<=nb<=maxb-minb, 0<=nc<=maxc-minc。

然后，我尝试使用包含-排除来查找解决方案的数量。我是这个原则的新手，因此不确定我是否做对了。反正我的答案是不正确的。有人可以告诉我这种方法的错误之处吗？这是我的代码。

提前致谢。

#include<iostream>
#include<cstdio>
using namespace std;
#define MOD 1000000007

#define ulli  long long int

ulli f(int a)
{
if(a<0) return 0;
else
{
    ulli n = (ulli)a;
    return ((((n+3)*(n+2)*(n+1))/6))%MOD;
}
}


 int N;

 int minA, maxA;
 int minB, maxB;
 int minC, maxC;

  int main()
 {
   int T;

scanf("%d",&T);

while(T--)
{
    scanf("%d",&N);

    scanf("%d %d",&minA , &maxA);
    scanf("%d %d",&minB , &maxB);
    scanf("%d %d",&minC , &maxC);

    maxA -= minA;
    maxB -= minB;
    maxC -= minC;

    int A = maxA;
    int B = maxB;
    int C = maxC;

    N -= (minA + minB + minC);


    ulli res = f(N) -f(N-A-1)-f(N-B-1)-f(N-C-1)+f(N-A-B-2)+f(N-C-B-2)+f(N-A-C-2)-f(N-A-B-C-3);

    cout<<res%MOD<<endl;
}


return 0;
 }

最佳答案

您可能应该通过一些简单的案例来弄清楚问题出在哪里。

一个明显的问题:f的公式为(N + 3)选择3；应该是(N + 2)选择2。(如果总共有N个，则添加2个分隔符，然后选择这两个分隔符的位置。)

您的其余代码中的一些尚不清楚，但是正确的。我会做类似的事情:

int A = maxA - minA;

而不是

maxA -= minA;
int A = maxA;

此外，根据数字的大小，可能存在溢出错误-将所有三个数字相乘然后除以6可能会在您进入mod之前溢出。您应该能够做的是找出三个中的哪一个可被3整除，然后将其除以2，然后找出一个因子。将结果中的两个相乘，对其进行修改，然后将最终结果相乘并对其进行修改。

哦，也修改了您的最终答案，我想这就是问题的根源。