[COTS 2024] 奇偶矩阵 Tablica

Luogu
IDLGP10681
Time1000ms
Memory1024MB
DifficultyP6
动态规划 DP递推2024O2优化生成函数线性递推COTS(克罗地亚)
考虑只包含 $0$ 和 $1$ 的 $N\times M$ 矩阵 $A$。 我们称满足以下条件的矩阵是好的: - $\forall 1\le i\le N$,$\displaystyle \sum_{j=1}^M A_{i,j}\in \{1,2\}$; - $\forall 1\le j\le M$,$\displaystyle \sum_{i=1}^N A_{i,j}\in \{1,2\}$。 求出 $N$ 行 $M$ 列的好的矩阵的数量,对 $(10^9+7)$ 取模。 ## Input 输入共一行两个正整数,即 $N,M$。 ## Output 输出一行一个整数,表示答案对 $(10^9+7)$ 取模后的结果。 [samples] ## Background 译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D1T2。$\texttt{1s,1G}。$ ## Note #### 样例解释 样例 $1$ 解释如图所示。 ![](https://cdn.luogu.com.cn/upload/image_hosting/xufx7ad6.png) #### 数据范围 对于 $100\%$ 的数据,$1\le N,M\le 3\, 000$。 | 子任务编号 | 分值 | 约束 | |:-----:|:------:|:-------:| | $1$ | $10$ | $N, M \leq 6$ | | $2$ | $18$ | $N, M \leq 50$ | | $3$ | $31$ | $N, M \leq 200$ | | $4$ | $41$ | 无额外约束 |
Samples
Input #1
2 2
Output #1
7
Input #2
3 3
Output #2
102
Input #3
15 20
Output #3
415131258
API Response (JSON)
{
  "problem": {
    "name": "[COTS 2024] 奇偶矩阵 Tablica",
    "description": {
      "content": "考虑只包含 $0$ 和 $1$ 的 $N\\times M$ 矩阵 $A$。 我们称满足以下条件的矩阵是好的: - $\\forall 1\\le i\\le N$,$\\displaystyle \\sum_{j=1}^M A_{i,j}\\in \\{1,2\\}$; - $\\forall 1\\le j\\le M$,$\\displaystyle \\sum_{i=1}^N A_{i,j}\\in \\{1,2\\}",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10681"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "考虑只包含 $0$ 和 $1$ 的 $N\\times M$ 矩阵 $A$。\n\n我们称满足以下条件的矩阵是好的:\n\n- $\\forall 1\\le i\\le N$,$\\displaystyle \\sum_{j=1}^M A_{i,j}\\in \\{1,2\\}$;\n- $\\forall 1\\le j\\le M$,$\\displaystyle \\sum_{i=1}^N A_{i,j}\\in \\{1,2\\}...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments