[COCI 2022/2023 #4] Bojanje

Luogu

IDLGP9174

Time1000ms

Memory512MB

DifficultyP5

动态规划 DP2022矩阵加速状态合并COCI（克罗地亚）状压 DP

Oliver 是一只不仅能找出 bug 并且喜欢画画的小黄鸭。他最新的画有 $n$ 个部分，每部分用一种不同的颜色涂色。在此之后他得到了很多批评，因为他的画太可预测了。他决定用 $t$ 次迭代修改他的画。在每次迭代中他将做以下操作： Oliver 会均匀随机选择一个下标 $i\ (1\le i\le n)$，然后记住画中第 $i$ 部分的颜色。 Oliver 会再均匀随机选择一个下标 $j\ (1\le j\le n)$。他会把画中第 $j$ 部分涂成和第 $i$ 部分一样的颜色。如果第 $j$ 部分的颜色和第 $i$ 部分相同，那么不会有任何改变。注意 $i$ 可以等于 $j$。现在，Oliver 害怕他的画会变得十分单调或者无聊。他认为一幅画是好的，如果画上至少有 $k$ 种不同的颜色。请帮他计算最后这幅画是好的这个事件的概率。 ## Input 第一行包含三个整数 $n,t,k\ (2\le k\le n\le 10,1\le t\le 10^{18})$，意义如题目描述。 ## Output 输出一行一个数，表示答案对 $10^9+7$ 取模后的值。形式化地，令 $m=10^9+7$。可以知道答案可以用不可约分数 $\frac{p}{q}$ 表示，其中 $p$ 和 $q$ 是整数，$q\not\equiv 0 \pmod m$。输出 $p\cdot q^{-1}\bmod m$。换句话说，输出满足 $0\le x<m$ 且 $x\cdot q\equiv p\pmod m$ 的整数 $x$。 [samples] ## Note 样例 $1$ 解释：画上有两种颜色，所以一次迭代后画和未操作之前相同的概率是 $\frac{1}{2}$。样例 $2$ 解释：在两次迭代后，不同的颜色数不可能从 $10$ 变为小于 $5$，所以在任何情况下这幅画都会有至少 $5$ 种不同的颜色。 | 子任务编号 | 附加限制 | 分值 | |:-:|:-:|:-:| | $0$ | 是样例 | $0$ | | $1$ | $k=n$ | $28$ | | $2$ | $t\le 1000$ | $36$ | | $3$ | 无附加限制 | $36$ |

Samples

Input #1

2 1 2

Output #1

500000004

Input #2

10 2 5

Output #2

Input #3

3 141592653589793 2

Output #3

468261332

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2022/2023 #4] Bojanje",
    "description": {
      "content": "Oliver 是一只不仅能找出 bug 并且喜欢画画的小黄鸭。他最新的画有 $n$ 个部分，每部分用一种不同的颜色涂色。在此之后他得到了很多批评，因为他的画太可预测了。他决定用 $t$ 次迭代修改他的画。在每次迭代中他将做以下操作： Oliver 会均匀随机选择一个下标 $i\\ (1\\le i\\le n)$，然后记住画中第 $i$ 部分的颜色。 Oliver 会再均匀随机选择一个下标 $j\\ (",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9174"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Oliver 是一只不仅能找出 bug 并且喜欢画画的小黄鸭。他最新的画有 $n$ 个部分，每部分用一种不同的颜色涂色。在此之后他得到了很多批评，因为他的画太可预测了。他决定用 $t$ 次迭代修改他的画。在每次迭代中他将做以下操作：\n\nOliver 会均匀随机选择一个下标 $i\\ (1\\le i\\le n)$，然后记住画中第 $i$ 部分的颜色。\nOliver 会再均匀随机选择一个下标 $j\\ (...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments