#P10443. [2021年联测]上进心

    ID: 9560 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>数论图论拓扑排序CF2600生成函数多项式数学模拟DAG-DP

[2021年联测]上进心

上进心

题目描述

有 kk 个工作小组,第 xx 天第 ii 组的工作量为 cx,ic_{x,i},每天按如下规则同时更新:

cx+1,i=t∑j=1icx,j.c_{x+1,i}=t\sum_{j=1}^{i}c_{x,j}.

每个月有 mm 天,每过 mm 天的月底,在当天的日常更新之后,各组额外加上 bib_i,并记录各组工作量对 p=109+7p=10^9+7 取模的值。

公司成立于一个月底,初始记录为 a1,…,aka_1,\ldots,a_k,这一天不额外加 bib_i。以后每个月底都按上述规则增加额外工作量。

给定某次月底记录 d1,…,dkd_1,\ldots,d_k,求它最早可能是成立后多少个月的记录,允许为 00。若 101010^{10} 个月以内不存在符合全部分量的记录,输出 −1-1。

保证若 a1=d1a_1=d_1,则第一个月月底第一组的工作量与 d1d_1 模 pp 不同。

输入格式

第一行三个整数 k,m,tk,m,t。

第二行 kk 个整数 a1,…,aka_1,\ldots,a_k。

第三行 kk 个整数 b1,…,bkb_1,\ldots,b_k。

第四行 kk 个整数 d1,…,dkd_1,\ldots,d_k。

输出格式

输出一个整数,表示最少月数;不存在不超过 10^10 的答案时输出 −1。

样例 1 输入

3 3 2
1 2 3
3 2 1
5851 73562 513993

样例 1 输出

4

样例说明

初始工作量为 (1,2,3)(1,2,3)。

第一个月:

$$(2,6,12)\to(4,16,40)\to(8+3,40+2,120+1)=(11,42,121).$$

第二个月:

$$(22,106,348)\to(44,256,952)\to(88+3,600+2,2504+1)=(91,602,2505).$$

第三个月月底为 (731,7002,38857)(731,7002,38857),第四个月月底为 (5851,73562,513993)(5851,73562,513993),所以答案为 44。

数据范围

全部数据满足 1≤k≤201\le k\le20,1≤m≤1081\le m\le10^8,2≤t≤1092\le t\le10^9,1≤ai,bi,di≤1091\le a_i,b_i,d_i\le10^9。

原 PDF 将 ai,bi,dia_i,b_i,d_i 的下界也写为 22,但样例含 a1=1a_1=1、b3=1b_3=1,此处允许样例中的 11。

子任务 分值 附加限制
1 15 m=1m=1,性质 A
2 m≤104m\le10^4,性质 A
3 性质 A
4 20 k=1k=1
5 35 无

性质 A:若有答案,保证最少月数不超过 10510^5。

附加样例 2、3 分别满足子任务 2、5 的限制。