分类： 矩阵快速幂

YZOJ P4587 斐波那契数列

YZOJ P4587 斐波那契数列

时间限制：1234MS      内存限制：43210KB

难度：\(6.5\)       （既然是自己搬的题还是正常一点吧w）

  • 题目描述

定义模意义下的递推数列 \(\displaystyle f_n=\left\{ {\begin{array}{*{20}{c}} 1&{,n \le 2}\\ {{f_{n – 1}} + {f_{n – 2}}}&{,n > 2} \end{array}} \right.\)，其中模数为 \(1000000009\) 。

给定整数 \(c\)（\(0 \leq c < 1000000009\)），求出它最早出现在数列的哪个位置，并输出下标。

若 \(c\) 永远不会出现在此数列的任一位置，则输出 \(-1\) 。

  • 输入格式

多组数据。

第一行一个正整数 \(T\) （\(0 < T \leq 100\)） 表示 \(T\) 组数据。

接下来 \(T\) 行每行一个数表示每组数据的 \(c\) 。

  • 输出格式

对于每组数据，输出一行一个数表示答案。

  • 样例输入

  • 样例输出

 

 

 

Source： BZOJ 5104…

YZOJ P3527 [FJOI2018D1T3]城市路径问题

YZOJ P3527 [FJOI2018D1T3]城市路径问题

时间限制：1000MS      内存限制：131072KB

难度：\(6.5\)

  • 题目描述

给出一张 \(n\) 个点的有向图 \(G(V, E)\) 。对于任意两个点 \(u, v\) （\(u\) 可以等于 \(v\) ），\(u\) 向 \(v\) 的连边数为：\(\sum\limits_{i=1}^k {out[u, i] \times in[v, i]}\) 。

给定 \(k\) 和数组 \(out, in\) ，现在有 \(m\) 个询问，每次询问给出三个参数 \(u, v, d\)，你需要回答从节点 \(u\) 出发，经过不超过 \(d\) 条边到达节点 \(v\) 的路径有多少种。

答案对 \(10^9+7\) 取模。

  • 输入格式

第一行两个整数 \(n, k\) 。

接下来 \(n\) 行，第 \(i\) 行有 \(2k\) 个整数，前 \(k\) 个整数描述 \(out[i][]\)，后 \(k\) 个数描述 \(in[i][]\) 。

接下来一行一个整数 \(m\) 。

接下来 \(m\) 行，每行三个整数 \(u, v, d\)，描述一组询问。

  • 输出格式

对于每个询问，输出一个方案数。由于答案可能太大，输出其除以 \(10^9+7\) 后的余数。…

YZOJ P3033 背包

YZOJ P3033 背包

时间限制：1000MS      内存限制：131072KB

出题人：chj2001             难度：\(5.4\)

  • 题目描述

存在 \(n\) 种物品，其中第 \(i\) 种物品的价值为 \(a_i\) ，最多可以用 \(b_i\) 件，求从这些物品中选取若干件（不能为 \(0\) 件），得到的总价值为 \(9\) 的倍数的方案。

需要分别计算每种物品中，每件之间有区别的方案数和没有区别的方案数。

（即每种物品按照 \(1,2,3, \cdots ,b_i\) 编号的方案数和不编号的方案数。）

  • 输入格式

第一行输入一个数 \(n\) 。

接下来 \(n\) 行，每行两个数 \(a_i, b_i\) 。

  • 输出格式

输出共两行，每行各包括一个数，分别表示对于每种物品视为不同的时的方案数和视为相同的时的方案数。有的时候方案数可能很大，你需要将它对 \(10^9+7\) 取模。

方案数均不考虑顺序，如 \(2, 3, 4\) 和 \(4, 3, 2\) 是同一种方案。

如果无法做到则输出 \(0\) 。

  • 样例输入

  • 样例输出

  • 样例说明

不考虑同种物品之间的区别，一共有 \(2\) 种不同的方案凑出 \(9\) 的倍数，即 \(3, 2, 2, 2\) 和 \(3, 3, 3\) 。

考虑同种和果子的区别时，一共有 \(C_3^1 \times C_3^3 = 3\) 种不同的方案凑出 \(3, 2, 2, 2\)，\(C_3^3=1\) 种方案凑出 \(3, 3, 3\)，因此总共有 \(4\) 种方案。

  • 数据规模与约定

对于 \(40\%\) 的数据，\(n \le 1000 , a_i \le 100 , b_i \le 100\) 。

对于 \(100\%\) 的数据，\(1 \le n \le 10^5 , 1 \le a_i \le 90000 , 1 \le b_i \le …

YZOJ P3629 [校内训练20180406]表达式

YZOJ P3629 [校内训练20180406]表达式

时间限制：1000MS      内存限制：131072KB

出题人：zzx         难度：\(6.5\)

  • 题目描述

本题中，我们需要计算一些“Bomb表达式”的结果。比如， “1-2+3” 的结果为 2 。和普通表达式不同的是，Bomb表达式中可能包含一些 “#” 号，会展开一些普通表达式。比如 “(1-2+3)#(3)” 表示 “1-2+3 ”出现了 3 次，将会被展开为 “1-2+31-2+31-2+3”，其结果为 60 。

为了方便理解，下面给出了Bomb表达式（bomb expression）和普通表达式（normal expression）的BNF表示。…