Qruplaşdırma vəzifəsi#1525

Qruplaşdırma vəzifəsi (Həll təhlili)

Qoy $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n — verilmiş $n$ ədəd olsun. $F_{ik} (i \geq k)$ F_{ik}~(i \ge k) ifadəsi ilə $a_{1}, ..., a_{i}$ a_1, ..., a_i ilk $i$ ədəd arasından seçilmiş mümkün olan bütün $k$ ədədlərin hasilatlarının cəmini təyin edək. Aşağıdakı $F_{ik}$ F_{ik} dəyərləri cədvəlini quraq:

Dörd ədəd üçün əldə edirik:

$F_{4, 1} = a_{1} + a_{2} + a_{3} + a_{4}$ F_{4,1} = a_1 + a_2 + a_3 + a_4;
$F_{4, 2} = a_{1} a_{2} + a_{1} a_{3} + a_{1} a_{4} + a_{2} a_{3} + a_{2} a_{4} + a_{3} a_{4}$ F_{4,2} = a_1a_2 + a_1a_3 + a_1a_4 + a_2a_3 + a_2a_4 + a_3a_4;
$F_{4, 3} = a_{1} a_{2} a_{3} + a_{1} a_{2} a_{4} + a_{1} a_{3} a_{4} + a_{2} a_{3} a_{4}$ F_{4,3} = a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4 + a_2a_3a_4;
$F_{4, 4} = a_{1} a_{2} a_{3} a_{4}$ F_{4,4} = a_1a_2a_3a_4;

Aşağıdakı rekurent bərabərliklər yerinə yetirilir:

F_{i 1} = F_{(i - 1) 1} + a_{i} F_{ii} = F_{(i - 1) (i - 1)} \cdot a_{i}, 1 \leq i \leq n F_{ik} = F_{(i - 1) k} + F_{(i - 1) (k - 1)} \cdot a_{i}, 1 \leq i \leq n, 1 < k < i

F_{i1} = F_{(i-1)1} + a_i\\ F_{ii} = F_{(i-1) (i-1)} \cdot a_i, 1 \le i \le n \\ F_{ik} = F_{(i-1)k} + F_{(i-1) (k-1)} \cdot a_i, 1 \le i \le n, 1 < k < i

Məsələn,

$F_{3, 2} = F_{2, 2} + F_{2,} 1 \cdot a_{3} = a_{1} a_{2} + (a_{1} + a_{2}) \cdot a_{3} = a_{1} a_{2} + a_{1} a_{3} + a_{2} a_{3}$ F_{3,2} = F_{2,2} + F_{2,}1 \cdot a_3 = a_1a_2 + (a_1 + a_2) \cdot a_3 = a_1a_2 + a_1a_3 + a_2a_3;
$F_{4, 3} = F_{3, 3} + F_{3, 2} \cdot a_{4} = a_{1} a_{2} a_{3} + (a_{1} a_{2} + a_{1} a_{3} + a_{2} a_{3}) \cdot a_{4} =$ F_{4,3} = F_{3,3} + F_{3,2} \cdot a_4 = a_1a_2a_3 + (a_1a_2 + a_1a_3 + a_2a_3) \cdot a_4 =
$a_{1} a_{2} a_{3} + a_{1} a_{2} a_{4} + a_{1} a_{3} a_{4} + a_{2} a_{3} a_{4}$
a_1a_2a_3 + a_1a_2a_4 + a_1a_3a_4 + a_2a_3a_4

Hər bir növbəti xəttin dəyərləri əvvəlki xəttin dəyərlərinə əsasən hesablandığından, məlumatları saxlamaq üçün $1000$ ölçüdə bir xətti massiv $d$ kifayətdir. $i$ -ci xəttin dəyərlərini yenidən sayma əməliyyatını sondan başlamaqla yerinə yetirmək lazımdır: öncə $F_{ii}$ F_{ii} hesablanır, sonrakı $F_{i (i - 1)}$ F_{i(i-1)} və sairə $F_{i 1}$ F_{i1}-ə qədər. Bütün hesablamalar $m$ modulu üzrə aparılmalıdır.

Məsələn,

Birinci testi nəzərdən keçirək. İki cədvəl düzəldək: birincisində hesablamalar moduldan olmadan aparılır, ikincisində isə $m = 10$ m = 10 modulu üzrə.

Məsələn,

$F_{4, 2} = F_{3, 2} + F_{3, 1} \cdot 4 = 11 + 6 \cdot 4 = 35$ F_{4,2} = F_{3,2} + F_{3,1} \cdot 4 = 11 + 6 \cdot 4 = 35;
$F_{4, 3} = F_{3, 3} + F_{3, 2} \cdot 4 = 6 + 11 \cdot 4 = 50$ F_{4,3} = F_{3,3} + F_{3,2} \cdot 4 = 6 + 11 \cdot 4 = 50;

Cavab ikinci cədvəlin dördüncü xəttindəki maksimum dəyərdir.

Alqoritmin həyata keçirilməsi

$F_{ik}$ F_{ik} dəyərlərinin yenidən hesablanacağı xətti massiv $d$ elan edək.

long long d[1000];

Ədədlərin sayını $n$ və $m$ dəyərini daxil edirik. Hər bir giriş testi üçün əvvəlcədən $d$ massivini sıfırlayırıq. İlk ədəd $a_{1}$ a_1-i $d [0]$ -a əlavə edirik.

while (scanf("%lld %lld",&n,&m), n + m > 0)
{
  memset(d,0,sizeof(d));
  scanf("%lld",&d[0]);

Sonra $x = a_{i + 1} (1 \leq i < n)$ x = a_{i+1}~(1 \le i < n) dəyərini daxil edirik və yuxarıda verilmiş rekursiya formullarına görə $F_{ik}$ F_{ik} dəyərlərini $k = i, i - 1, ..., 1$ k = i, i - 1, ..., 1 üçün yenidən hesablayırıq. Bütün hesablamalar $m$ modulu üzrə aparılır.

  for (i = 1; i < n; i++)
  {
    scanf("%lld",&x);
    d[i] = (d[i-1] * x) % m; 

    for (j = i - 1; j > 0; j--)
      d[j] = (d[j-1] * x + d[j]) % m;

    d[0] = (d[0] + x) % m;
  }

C++

$d$ massivinin elementləri arasında maksimum dəyəri tapırıq və onu $r es$ dəyişəninə saxlayırıq.

  res = 0;
  for (i = 0; i < n; i++)	   
    if (d[i] > res) res = d[i];

Nəticəni çıxarırıq.

  printf("%lld\n",res);
}