0

N 個の整数の配列があり、配列の左 (L) と右セグメント (R) を指定して T 回セグメント乗算を実行し、指定された係数 (M) を法として答えを返す必要があるインターネットからの問題があります。 .

制約

N、T<=100000

1<=L<=R<=N

M<=10^9

および整数 <=100

元-

入力

5(N) 2 5 8 9 4 4(T) 1 2 3 2 3 4 1 1 1 1 5 100000

出力

1 0 0 2880

だから私はこの問題を解決しましたが、少し遅いので、プログラムを最適化するためのヒントが必要です。

#include "stdio.h"

int main(void)
{
        int t;
        scanf("%d",&t);

        int Array[t+1];


    for (int i = 1; i <=t; i++)
    {
        scanf("%d",&Array[i]);
    }

    int N;
    scanf("%d",&N);


    for (int i = 0; i <N ; i++)
    {

        long long a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        long long Product = 1;
        if (c==1)
        {
            Product = 0;

        }
        else
        {

            for (int j = a; j <=b ; j++)
            {

                Product *= Array[j];

                if (Product>=10000000000000000)
                {
                    Product%=c;
                }
            }

        }

        Product%=c;


        printf("%lld\n",Product );

    }

    return 0;
}
4

1 に答える 1

2

ヒント

100 未満の素数 p ごとに配列 A_p[i] を計算できます。これは、p が配列の i^ 番目のエントリを分割する回数を示します。

次に、j を含む i までの A_p[i] の累積合計である二次配列 B_p[j] を計算できます。(これは、再帰 B_p[i]=B_p[i-1]+A_p[i] によって O(n) で実行できます。)

この二次配列を使用すると、任意の範囲の各素数の合計パワーを計算できます。たとえば、素数 5 が配列エントリ 10 から 100 に出現した回数を知りたい場合は、B_5[100]-B_5[10-1] を計算できます。

したがって、各クエリに対して、各素数を対応するべき乗にし、結果をモジュロ M で乗算することにより、最終的な答えを計算できます。この計算を効率的にする、2 乗によるべき乗と呼ばれる手法があることに注意してください。

0 が可能な整数である場合、計算で考慮される素数のリストに 0 を追加します。

関心のために

累積合計を使用するこのアプローチは、多くの状況で非常に役立つことに注意してください。たとえば、顔認識の Viola-Jones 法では、2 次元フィルターを効率的に計算できるようにするために、この手法のバージョンを 2 次元で使用しています。

于 2013-08-07T21:27:14.237 に答える