#P18832. [COCI 2026/2027 #2] Jackpot

[COCI 2026/2027 #2] Jackpot

题目描述

键盘上有 nn 种字符。每按一次回车,恰有一种字符被写入,或者什么也不写:写入字符 ii 的概率是 ai/bia_i/b_i,剩余概率对应不写字符。各次按键独立。

如果每种字符 ii 都已出现至少 kik_i 次,就达成目标。求从空字符串出发,首次达成目标所需的按键次数的期望。

输入格式

第一行一个整数 nn。第二、三、四行分别给出 k1,…,knk_1,\ldots,k_n、a1,…,ana_1,\ldots,a_n、b1,…,bnb_1,\ldots,b_n。

输出格式

若无法达成目标,输出 nikada。否则设期望为既约分数 P/QP/Q,输出 PQ−1 mod (109+7)P Q^{-1}\bmod (10^9+7)。

数据范围与评分

  • 1≤n≤1000001\le n\le 100000,ki≥0k_i\ge 0,1≤∑iki≤221\le \sum_i k_i\le 22。
  • 0≤ai≤bi≤1090\le a_i\le b_i\le 10^9,bi≥1b_i\ge 1,∑iai/bi≤1\sum_i a_i/b_i\le 1。
  • 若目标可达,任选一个非空的、仅含 ki>0k_i>0 的字符集合,其概率之和化为既约分数后,分子不被 109+710^9+7 整除。
  • 时间限制 5 秒,内存限制 8 MiB。
子任务 分值 额外限制
1 9 n=1n=1
2 26 ∑iki≤2\sum_i k_i\le 2
3 39 ∑iki≤16\sum_i k_i\le 16
4 31 每个 ki≤1k_i\le 1
5 无

输入输出样例

样例 1

输入

1

1

1

6

输出

6

样例 2

输入

2

1 1

1 1

2 2

输出

3

样例 3

输入

1

1

0

6

输出

nikada