#P14483. [2025年广东省队集训]图上的游戏

    ID: 13700 传统题 4000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3000博弈论动态规划组合数学生成函数计数DP

[2025年广东省队集训]图上的游戏

问题描述

我喜欢你,E_Space,所以这是一道博弈题。

小 A\textbf{A} 与小B\textbf{B} 喜欢图上的游戏,现在有一个 nn 个点的有向图 GG,最初图上没有边。在接下来 mm 个时刻,每个时刻会发生下列事件:

  • 随机选取 u,v∈[1,n]u,v\in[1,n],在图 GG 上连接一条从 u→vu\rightarrow v 的有向边。

小 A\textbf{A} 和小 B\textbf{B} 喜欢黑白两种颜色,最初第 ii 个点有颜色 ci∈{0,1,2}c_i\in \{0,1,2\},如果 ci=0c_i=0 就是黑色,ci=1c_i=1 就是白色,ci=2c_i=2 表示该点颜色未确定。

小 A\textbf{A} 和小 B\textbf{B} 会在 mm 个时刻后的图 GG 上做游戏,小 A\textbf{A} 与小 B\textbf{B} 会轮流选择图 GG 上一个还未染色的点进行染色,其中小 A\textbf{A} 先手。小 A\textbf{A} 和小 B\textbf{B} 认为黑白相间的边才是美丽的,但是边存在方向。小 A\textbf{A} 获得的分数是满足 u→vu\rightarrow v 且 cu=0,cv=1c_u=0,c_v=1 的边的条数,小 B\textbf{B} 获得的分数是满足 u→vu\rightarrow v 且 cu=1,cv=0c_u=1,c_v=0 的边的条数,令 Z\textbf{Z} 为小 A\textbf{A} 的分数减去小 B\textbf{B} 的分数,小 A\textbf{A} 想要使 Z\textbf{Z} 尽量大,而小 B\textbf{B} 想要使 Z\textbf{Z} 尽量小,若双方都足够聪明,最终 Z\textbf{Z} 的值会是多少?

小 A\textbf{A} 和小 B\textbf{B} 想要知道,对于所有可能的 n2mn^{2m} 种情况,最终 Z\textbf{Z} 的和对 109+710^9+7 取模后的值为多少。\udot{注意,这里认为两种情况不同,当前仅当存在某个时刻加入的有向边不同,同时,图 GG 中可能存在重边和自环}。

但是观战者小 C\textbf{C} 认为这太简单了,小 C\textbf{C} 想要知道,对于所有 1≤N≤n,1≤M≤m1\le N\le n,1\le M\le m,若只关注图 GG 的前 NN 个点(即忽略后 n−Nn-N 个点,图 GG 上只有 NN 个点)且 m=Mm=M 时上述问题对应的答案。

输入格式

第一行两个整数 n,mn,m,分别表示图 GG 的点数以及时刻数。

接下来一行包含 nn 个整数,第 ii 个整数表示 cic_i。

输出格式

共 nn 行,每行包含 mm 个整数,第 ii 行第 jj 个整数表示当 N=i,M=jN=i,M=j 时对应的答案。

输入格式

3 2
0 1 2

输出格式

0 0
0 0
2 28

数据范围

对于 100%100\% 的数据,1≤n,m≤501\leq n,m\le 50,ci∈{0,1,2}c_i\in \{0,1,2\}。

测试点编号 nn mm 特殊限制
11 ≤50\leq 50 ≤50\leq 50 AA
2∼32\sim 3 =1=1 无
4∼64\sim 6 =2=2
7∼97\sim 9 ≤5\leq 5
10∼1110\sim 11 ≤8\leq 8
12∼1312\sim 13 ≤15\leq 15
14∼1714\sim 17 ≤25\leq 25
18∼2118\sim 21 ≤50\leq 50 BB
22∼2322\sim 23 ≤35\leq 35 无
24∼2524\sim 25 ≤50\leq 50

特殊性质 A: ∀i∈[1,n]\forall i \in [1,n],ci∈{0,1}c_i\in \{0,1\}。

特殊性质 B: 保证 ci=2c_i=2 的个数不超过 11。