到+ B + C <= N

Question

大家解决方案的数量，这是在参考，这一问题：http://www.spoj.pl/problems/DCEPC702 /.(Kindly看到有一个样本输入）。我翻译的问题陈述这个寻找解决方案的数量，这种形式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）选择3;它应该是（N + 2）选择2.（如果总共有N个，则添加2个分隔符，并选择这两个分隔符的位置。）

其余一些代码不清楚，但是正确。我会做这样的事情：

int A = maxA - minA; 

而不是

maxA -= minA; 
int A = maxA; 

另外，还有一些潜在的溢出错误，这取决于数字有多大 - 这三个数字，然后由6分乘以你之前可能溢出去mod。你应该能够做的就是找出其中三个由3整除，并划分了这一点，然后再来哪个（些）是2 /整除，并划分出的一个因素。乘以两个结果，对其进行修改，然后乘以最终结果并对其进行修改。

哦，国防部最终的答案也一样，我觉得这个问题问什么。