#P13938. [2024多校联盟省选模拟]经典排列问题

    ID: 13145 传统题 500ms 128MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400动态规划状压DP计数DP模运算图论模拟

[2024多校联盟省选模拟]经典排列问题

题目描述

请注意 LL 的范围!

给定两个正整数 n,Ln,L 和 mm 个有序二元组 (ai,bi) (1≤ai,bi≤n)(a_i,b_i)\ (1\le a_i,b_i\le n),计数满足以下性质的排列 pp 数量:

  • p1=1p_1=1;
  • ∣pi−p(i mod n)+1∣≤L\lvert p_i - p_{(i\bmod n)+1}\rvert \le L;
  • ∀i,j\forall i,j,pi≠aj ∨ p(i mod n)+1≠bjp_i\ne a_j\ \lor\ p_{(i\bmod n)+1}\ne b_j。

由于结果可能很大,输出时对 109+710^9+7 取模。

输入格式

第 1 行三个正整数 n,m,Ln,m,L。
接下来 mm 行每行两个正整数 ai,bia_i,b_i。

输出格式

输出一个正整数,表示合法排列个数对 109+710^9+7 取模的结果。

5 2 3
1 3
5 4
6

数据范围与提示

  • 对于 10% 的数据:n≤10n\le 10;
  • 对于另外 10% 的数据:L≤2L\le 2;
  • 对于另外 30% 的数据:m=0m=0;
  • 对于 100% 的数据:1≤n≤1061\le n\le 10^6,0≤m≤1050\le m\le 10^5,0≤L≤30\le L\le 3。