1

大家，这是参考这个问题：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;
 }
4

1 回答 1

1

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

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

您的代码的其余部分不清楚，但正确。我会做类似的事情：

int A = maxA - minA;

而不是

maxA -= minA;
int A = maxA;

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

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

于 2012-06-22T05:17:16.703 回答