a+b+c<=n的解决方案数量

Question

各位，这是关于这个问题的：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;
 }

Answer 1

您可能应该通过一些简单的案例来看看哪里出了问题。

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

你剩下的一些代码不清楚，但是正确的。我会这样做：

int A = maxA - minA;

而不是

maxA -= minA;
int A = maxA;

此外，还有潜在的溢出错误，这取决于数字的大小-将所有三个数字相乘，然后除以6，在您到达mod之前可能会溢出。你应该能够做的是找出这三个中的哪一个可以被3整除，然后计算出哪一个/哪一个可以被2整除，然后再除以一个因子。将两个结果相乘，对其进行mod，然后将最终结果相乘，对其进行mod。

哦，还有修改你的最终答案，我想这就是问题所要求的。