[USACO24JAN] Cowmpetency G

Luogu
IDLGP10138
Time2000ms
Memory256MB
DifficultyP5
动态规划 DPUSACO2024动态规划优化前缀和
Farmer John 正在为他的奶牛们雇用一位新的牛群领队。为此,他面试了 $N$($2\le N\le 10^9$)头奶牛来担任该职位。在每次面试后,他会为候选牛分配一个 $1$ 到 $C$($1\le C\le 10^4$)范围内的整数「牲任力」分数 $c_i$,与她们的领导能力相关。 由于 Farmer John 面试了如此多的奶牛,他已经忘记了所有奶牛的牲任力分数。然而,他确实记得 $Q$ ($1\le Q\le \min(N-1,100)$)对数字 $(a_i,h_i)$,其中奶牛 $h_i$ 是第一头比奶牛 $1$ 到 $a_i$ 拥有**严格**更高牲任力分数的奶牛(所以 $1\le a_i<h_i\le N$)。 Farmer John 现在告诉你这 $Q$ 个数对 $(a_i,h_i)$。请帮助他数一下有多少个牲任力分数序列与此信息一致!输入保证存在至少一个这样的序列。由于这个数字可能非常大,输出该值模 $10^9+7$ 的余数。 ## Input 输入的第一行包含 $N$,$Q$ 和 $C$。 以下 $Q$ 行,每行包含一个数对 $(a_i,h_i)$。输入保证所有 $a_i$ 各不相同。 ## Output 输出与 Farmer John 记忆一致的牲任力分数序列的数量,对 $10^9+7$ 取模。 [samples] ## Note ### 样例解释 1 以下六个序列是仅有的与 Farmer John 记忆一致的序列: $1\ 1\ 2\ 1\ 3\ 1$ $1\ 1\ 2\ 1\ 3\ 2$ $1\ 1\ 2\ 1\ 3\ 3$ $1\ 1\ 2\ 2\ 3\ 1$ $1\ 1\ 2\ 2\ 3\ 2$ $1\ 1\ 2\ 2\ 3\ 3$ ### 样例解释 2 确保输出答案对 $10^9+7$ 取模。 ### 测试点性质 - 测试点 $3-4$:$N\le 10$ 且 $Q,C\le 4$。 - 测试点 $5-7$:$N,C\le 100$。 - 测试点 $8-10$:$N\le 2000$ 且 $C\le 200$。 - 测试点 $11-15$:$N,C\le 5000$。 - 测试点 $16-20$:没有额外限制。
Samples
Input #1
6 2 3
2 3
4 5
Output #1
6
Input #2
10 1 20
1 3
Output #2
399988086
API Response (JSON)
{
  "problem": {
    "name": "[USACO24JAN] Cowmpetency G",
    "description": {
      "content": "Farmer John 正在为他的奶牛们雇用一位新的牛群领队。为此,他面试了 $N$($2\\le N\\le 10^9$)头奶牛来担任该职位。在每次面试后,他会为候选牛分配一个 $1$ 到 $C$($1\\le C\\le 10^4$)范围内的整数「牲任力」分数 $c_i$,与她们的领导能力相关。 由于 Farmer John 面试了如此多的奶牛,他已经忘记了所有奶牛的牲任力分数。然而,他确实记得 $",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10138"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Farmer John 正在为他的奶牛们雇用一位新的牛群领队。为此,他面试了 $N$($2\\le N\\le 10^9$)头奶牛来担任该职位。在每次面试后,他会为候选牛分配一个 $1$ 到 $C$($1\\le C\\le 10^4$)范围内的整数「牲任力」分数 $c_i$,与她们的领导能力相关。\n\n由于 Farmer John 面试了如此多的奶牛,他已经忘记了所有奶牛的牲任力分数。然而,他确实记得 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments