#P3215. [Zjoi2013]话旧

    ID: 2399 传统题 1000ms 512MiB 尝试: 309 已通过: 91 难度: 8 上传者: 标签>CF2500提高+/省选-线性 DP计数 DP普通生成函数生成函数求系数快速幂滚动数组

[Zjoi2013]话旧

题目描述

小林跟着银河队选手去了一趟宇宙比赛,耳濡目染,变得学术起来。回来后,他发现世界大变样了。比丘兽究级进化,成了凤凰兽;金先生因为发了一篇 paper,一跃成为教授,也成为了银河队选拔委员会成员。

一日,小林与金教授聊天。金教授回忆起过去的岁月,那些年他学过的电路原理。他曾经对一种三角波很感兴趣,并且进行了一些探究。小林感到很好奇,于是金教授就将课题形式化地说了一遍。

有一定义在 [0,n][0,n] 的连续函数 f(x)f(x),其中 nn 是整数,满足 f(0)=f(n)=0f(0)=f(n)=0,它的所有极值点在整数处取到,且 f(x)f(x) 的极小值均是 00。对于任意的 00 到 n−1n−1 间的整数 ii,f(x)f(x) 在 (i,i+1)(i, i+1) 上是斜率为 11 或 −1−1 的一次函数。

金先生研究的是,若他知道其中 kk 个整点的函数值,那么:

  1. 有多少个函数满足条件?
  2. 满足条件的函数中,f(x)f(x) 的最大值,最大能是多少?

小林思考了一下,便想出了很好的算法。那么作为经过多年训练的你呢?

输入格式

第一行包含两个用空格隔开的整数 n,kn,k。

接下来 kk 行,每行两个整数,表示 xix_i 和 f(xi)f(x_i)。

输出格式

一行两个整数,分别对应两个问题的答案。考虑到第一问答案可能很大,你只要输出它除以 19 940 41719\ 940\ 417 的余数。

2 0
1 1
6 9
4 2
4 2
2 0
4 2
6 0
5 1
2 0
0 0
0 0
1 2

数据规模与约定

  • 对于 10%10\% 的数据,n≤10n \leq 10。
  • 对于 20%20\% 的数据,n≤50n \leq 50。
  • 对于 30%30\% 的数据,n≤100n \leq 100,k≤100k \leq 100。
  • 对于 50%50\% 的数据,n≤103n \leq 10^3,k≤103k \leq 10^3。
  • 对于 70%70\% 的数据,n≤105n \leq 10^5。
  • 另有 10%10\% 的数据,k=0k=0。
  • 对于 100%100\% 的数据,0≤n≤1090 \leq n \leq 10^9,0≤k≤1060 \leq k \leq 10^6。