Məşq (Platin)
Fermer Con inəklər üçün yeni bir səhər idmanı rejimi icad edib!
Conun n inəyi sıraya düzülüb və hər biri soldan sağa i nömrəsi ilə etiketlənib (1 ≤ i ≤ n). O, inəklərə, başlanğıcda olduğu kimi eyni sıraya qayıdana qədər, aşağıdakı addımı təkrarlamağı tapşırır.
Uzunluğu n olan A permutasiyası verilir və inəklər öz sıralarını dəyişirlər ki, dəyişiklikdən əvvəl soldan i-ci inək dəyişiklikdən sonra soldan A[i]-ci olur.
Məsələn, əgər A = (1, 2, 3, 4, 5) olarsa, inəklər bir addım atır. Əgər A = (2, 3, 1, 5, 4) olarsa, inəklər altı addım atacaq. Hər bir addımdan sonra soldan sağa inəklərin sırası belə olacaq:
0 addım: (1, 2, 3, 4, 5)
1 addım: (3, 1, 2, 5, 4)
2 addım: (2, 3, 1, 4, 5)
3 addım: (1, 2, 3, 5, 4)
4 addım: (3, 1, 2, 4, 5)
5 addım: (2, 3, 1, 5, 4)
6 addım: (1, 2, 3, 4, 5)
Bütün uzunluğu n! olan mümkün permutasiyalar üçün A-nın tələb etdiyi addımların sayının hasilini hesablayın.
Bu rəqəm çox böyük ola biləcəyi üçün cavabı m modulunda verin.
C++ istifadəçiləri üçün KACTL-dən aşağıdakı kod faydalı ola bilər. Barrett reduksiyası kimi tanınan bu üsul, b > 1 sabit olan və kompilyasiya zamanı məlum olmayan a % b-ni adi üsuldan bir neçə dəfə daha sürətli hesablamağa imkan verir (təəssüf ki, Java üçün belə bir optimizasiya məlum deyil).
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
ull b, m;
FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
ull reduce(ull a) {
ull q = (ull)((L(m) * a) >> 64);
ull r = a - q * b; // can be proven that 0 <= r < 2*b
return r >= b ? r - b : r;
}
};
FastMod F(2);
int main() {
int M = 1000000007; F = FastMod(M);
ull x = 10ULL*M+3;
cout << x << " " << F.reduce(x) << "\n"; // 10000000073 3
}Giriş məlumatları
Bir sətirdə n (1 ≤ n ≤ 7500) və m (10^8 ≤ m ≤ 10^9 + 7, m sadə) ədədləri verilir.
Çıxış məlumatları
Bir ədəd çıxarın.
Nümunə
Hər bir i üçün (1 ≤ i ≤ n), aşağıdakı massivdəki i-ci element inəkləri i addım atmağa məcbur edən permutasiyaların sayıdır: [1, 25, 20, 30, 24, 20]. Cavab 1^1 * 2^25 * 3^20 * 4^30 * 5^24 * 6^20 = 369329541 (mod 10^9 + 7).