-1

以下の問題で行き詰まっています。私の解決策は制限時間を超えています。誰かがそれを改善する方法を教えてもらえますか?

異なる数 (X1、X2、X3) の順序付けられたトリプルの数を数えるだけです。ここで、Xi は 1 から Ni までの任意の正の整数 (i = 1、2、3) です。数値 N1、N2、N3 は 10^18 まで可能です。このため、答えは非常に大きくなる可能性があります。したがって、モジュロ 10^9 + 7 で出力する必要があります。

入力

入力の最初の行には、テスト ケースの数を示す整数 T が含まれます。T テスト ケースの説明は次のとおりです。各テスト ケースの唯一の行には、スペースで区切られた 3 つの整数 N1、N2、N3 が含まれています。

出力

テスト ケースごとに、10^9 + 7 を法とする必要なトリプルの数を含む 1 行を出力します。

制約

1≦T≦1000

1 ≤ Ni ≤ 10^18

Example

Input:

5

3 3 3
2 4 2
1 2 3
25 12 2012
1 1 2013

Output:
6
4
1
578880
0

これが私の解決策です：

#include <iostream>

using namespace std;

int main()
{
int t;
scanf("%d",&t);
for(int i=0; i<t; i++)
{
    long long unsigned a,b,c,sum=0,s1,s2,s3;
    scanf("%llu %llu %llu", &a,&b,&c);
    for(s1=1; s1<=a; s1++)
    {
        for(s2=1; s2<=b; s2++)
        {
            if(s1==s2) continue;
            for(s3=1; s3<=c; s3++)
            {
                if(s1==s3 || s2==s3) continue;
                sum=(sum+1)%1000000007;
            }
        }
    }
    printf("%llu\n",sum);
}
return 0;
}
4

1 に答える 1

1

順序付けられたトリプルの数を簡単に計算できることがわかったので、ここで解決策を示します。

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
const long long unsigned the_prime= 1000000007;
int t;
scanf("%d",&t);
for(int i=0; i<t; i++)
{
    long long unsigned m[3],res=0;
    scanf("%llu %llu %llu", &m[0],&m[1],&m[2]);
    sort(m,m+3);
    res=((((m[0]%the_prime)*((m[1]-1)%the_prime))%the_prime)*((m[2]-2)%the_prime))%the_prime;
    printf("%llu\n",res);
}
return 0;
 }
于 2013-03-17T20:20:36.203 に答える