#P9618. Container

    ID: 6238 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高线性 DP计数 DPPascal 递推滚动数组

Container

题目描述

有 nn 个编号为 11 到 nn 的盒子,每个盒子的容量均为 tt,现在有 kk 次操作,对于第 ii 次操作,可以选择在编号为 [Li,Ri][L_i,R_i] 的盒子中放入一个小球,且需保证放完小球后盒子不能溢出。求本质不同的可行操作序列的方案数。两种可行操作序列本质不同当且仅当存在某一次操作二者选择的区间不同。

输入格式

输入仅一行三个整数 n,k,tn, k, t。

输出格式

输出仅一行一个整数表示答案对 10111100111011110011 取模后的结果。

样例

3 2 1
10

以下是 1010 种方案:

  • [1,1],[2,2][1, 1], [2, 2];
  • [1,1],[2,3][1, 1], [2, 3];
  • [1,1],[3,3][1, 1], [3, 3];
  • [1,2],[3,3][1, 2], [3, 3];
  • [2,2],[1,1][2, 2], [1, 1];
  • [2,2],[3,3][2, 2], [3, 3];
  • [2,2],[3,3][2, 2], [3, 3];
  • [3,3],[1,1][3, 3], [1, 1];
  • [3,3],[1,2][3, 3], [1, 2];
  • [3,3],[1,2][3, 3], [1, 2]。
15 6 4
458177764

xn+yn=znx^n+y^n=z^n。

子任务

子任务 分数 特殊性质
11 1414 n,k≤4n,k\le 4
22 2525 t=1t=1
33 99 t=kt=k
44 5252 无特殊限制

对于所有数据,均满足 1≤n,k,t≤401\le n,k,t\le 40,t≤kt\le k。