Masala #0096

Xotira 32 mb Vaqt 1000 ms Qiyinchiligi 85 %
14

  

Permutatsiya

Adizda [1,…,N] sonlar ketma-ketligi mavjud. U bu sonlarning barcha permutatsiyasini leksikografik o’sish tartibida qog’ozga yozib oldi va ularni ketma-ketligi bo’yicha raqamlab chiqdi. Masalan N=3 uchun jami 6 ta permutatsiya bor va ular quyidagilar:

Adiz bu permutatsiyalar orasidan ixtiyoriy birini tanlab oldi va uni yodida saqladi. Bir necha kundan so’ng u o’zi tanlagan permutatsiyani qog’ozga yozmoqchi bo’lganida bildiki tanlagan permutatsiyasidagi ba’zi qiymatlar yodidan ko’tarilgan, qog’ozga yozish jarayonida u yodidan ko’tarilgan qiymatlar o’rniga 0 qiymatini yozdi. Shundan so’ng uni quyidagicha savol qiziqtirib qoldi, u tanlagan permutatsiya qog’ozdagi qaysi qatorlar bo’lishi mumkin.


Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, N(1 ≤ N ≤ 3*105) permutatsiyadagi elementlar soni. Keyingi qatorda N ta butun son, Adizning yodida saqlagan permutatsiyasi.


Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida bitta butun son, Adiz yodida saqlagan permutatsiya mos kelishi mumkin bo’lgan qog’ozdagi qatorlarning qiymatlari yig’indisini 109+7 ga bo’lgandagi qiymatini chop eting.


Misollar
# input.txt output.txt
1
4
0 2 3 0
23
2
4
4 3 2 1
24
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin

Robocontest.uz Copyrighted © 2020 by Robocontest Team

Generated in 108ms