#P9743. LJJ 的生日礼物

    ID: 6368 传统题 3000ms 512MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-计数 DP对称性分析转移矩阵矩阵快速幂离散化添加哨兵模逆元

LJJ 的生日礼物

题目描述

一条长度为 LL 的纸带由 LL 个方格组成,从左到右编号为 0,1,…,L−10,1,\ldots,L-1。用编号为 1,2,…,K1,2,\ldots,K 的颜色给每格涂一种颜色,要求相距 11 或 22 的两个方格颜色不同。此外有 NN 个预先指定的颜色要求,第 ii 个要求是方格 pip_i 必须涂成颜色 cic_i。

求符合所有要求的涂色方案数,对 109+710^9+7 取模。方格按固定方向比较,只要某一位置颜色不同,就视为不同方案。

输入格式

第一行一个整数 TT,表示测试组数。

对于每组数据,第一行三个整数 N,K,LN,K,L。

接下来 NN 行,每行两个整数 pi,cip_i,c_i。位置按严格递增的顺序给出。

输出格式

输出 TT 行。第 xx 组数据的输出格式为 Case #x: y,其中 yy 是该组答案,xx 从 11 开始。

样例

3
0 3 4
1 4 4
1 1
2 5 5
1 1
3 2
Case #1: 6
Case #2: 12
Case #3: 27

数据范围

对于全部数据,1≤T<1001\le T<100,0≤N≤10000\le N\le1000,K≤109K\le10^9,max⁡(1,N)≤L≤109\max(1,N)\le L\le10^9,1≤ci≤K1\le c_i\le K,0≤p1<⋯<pN<L0\le p_1<\cdots<p_N<L。至多 1010 组数据满足 N>100N>100。

  • 原题测试点 1–3 满足 L≤50L\le50,K≤109K\le10^9。
  • 原题测试点 4–6 满足 N≤1000N\le1000,K≤1000K\le1000。

原 PDF 题面