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

どこが間違っているのかを確認するために、おそらくいくつかの単純なケースに取り組む必要があります。

明らかな問題が 1 つあります。f の式は (N+3) 3 を選択します。(N+2) 2 を選択します (合計 N 個の場合は、2 つのセパレーターを追加し、それら 2 つの位置を選択します)。

コードの残りの部分は不明確ですが、正しいです。私は次のようなことをします：

int A = maxA - minA;

それよりも

maxA -= minA;
int A = maxA;

また、数値の大きさによっては、オーバーフロー エラーが発生する可能性があります。3 つの数値すべてを掛けてから 6 で割ると、mod に到達する前にオーバーフローする可能性があります。あなたができるべきことは、3つのうちどれが3で割り切れるかを割り出し、それを割り、次にどれが2で割り切れるかを割り出し、1つの因数を割り出すことです. 2 つの結果を乗算して mod し、最終結果を乗算して mod します。

ああ、あなたの最終的な答えも変更してください。問題が求めているものだと思います。

于 2012-06-22T05:17:16.703 に答える