YZOJ P4611 区间加多项式(YJC 的数组/多项式?)

YZOJ P4611 区间加多项式(YJC 的数组/多项式?)

时间限制:4444MS      内存限制:1048576KB

难度:\(7.2\)

  • 题目描述

由于本题之前被*了,所以现在数据就是随便造的,可能会因为太水又被艹     //给出题人留点面子吧qwq

YJC 在 AK 了一场校内之后,对其中的一题(P2036 「A Simple Data Structure Problem II 」)产生了兴趣。

于是他出了一题加强版(P4316 「ASDSP VII —— YJC树」),然而,他还是觉得这个加强版太简单啦!!!

所以,这次,他不仅把 \(K \leq 5\) 往后面加了三个零变成了 \(K \leq 5000\) ,还对询问做了一点修改!

喜欢差分的 YJC 有一个长度为 \(N\) 的数组 \(c\),初始值都为 \(0\),下标编号为 \(1, 2, \cdots, N\) 。

现在 YJC 忙着 AK CSP-S2019,没空验证数据的正确性,所以只能把这个重任交给了你 —— ******,希望你能写一个程序帮他实现以下的几个操作:

\(opt=1\),给定 \(L, R\),输出 \(\sum\limits_{i=L}^R c_i\) 的值对 \(998244353\) 取模后的结果;

\(opt=0\),给定 \(L, R\) 以及 \(K\) 次多项式 \(f(x)=\sum\limits_{k=0}^K a_kx^k\),对 \(c_L, c_{L+1}, \cdots, c_R\) 分别加上 \(f(1), f(2), \cdots, f(R-L+1)\) 的值。

  • 输入格式

第一行两个正整数 \(N, Q\) ,分别表示区间范围 \([1, N]\) 及询问数 \(Q\) 。

接下来,每行(除了每个 \(opt=0\) 操作的下一行)的第一个数 \(opt\) 表示操作类型。

若 \(opt=0\),则接下来有两个正整数 \(L, R\) 表示操作的区间 \([L, R]\)。紧接着下一行的第一个整数 \(K\) 表示多项式的最高次数为 \(K\) ,接下来 \(K+1\) 个整数 \(a_0, a_1, \cdots, a_K\) 分别表示多项式 \(f(x)= \displaystyle\sum\limits_{k=0}^K a_kx^k\) 的系数;

若 \(opt=1\),则接下来有两个正整数 \(L, R\) 表示询问的区间 \([L, R]\)。

因为 YJC 忙着 AK CSP-S2019(之前说过了),所以他一不小心把数据给加密了。

记 …

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\) 后的余数。

  • 样例输入


Read the rest

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 P3782 [校内训练20180619]组合数问题

YZOJ P3782 [校内训练20180619]组合数问题

时间限制:1000MS 内存限制:524288KB

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

  • 题目描述

  • 输入格式

第一行一个正整数 \(n\) 表示数对个数。

接下来 \(n\) 行,第 \(i\) 行两个正整数 \(a_i, b_i\),表示一个数对 \((a_i, b_i)\) 。

  • 输出格式

一行一个整数,表示所求式子的值。

  • 样例输入

  • 样例输出

  • 样例说明

  • 数据规模与约定

保证 \(2 \leq n \leq 200,000\) , \(1 \leq b_i \leq a_i \leq 2000\) 。

 

 

 …