题解：洛谷 P5023 [NOIP 2018 提高组] 填数游戏-洪萨配资

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P5023 [NOIP 2018 提高组] 填数游戏 - 洛谷

【题目描述】

小 D 特别喜欢玩游戏。这一天，他在玩一款填数游戏。

这个填数游戏的棋盘是一个n × m n \times mn×m的矩形表格。玩家需要在表格的每个格子中填入一个数字（数字0 00或者数字1 11），填数时需要满足一些限制。

下面我们来具体描述这些限制。

为了方便描述，我们先给出一些定义：

我们用每个格子的行列坐标来表示一个格子，即（行坐标，列坐标）。注意：行列坐标均从0 00开始编号。
合法路径P PP：一条路径是合法的当且仅当：
1. 这条路径从矩形表格的左上角的格子( 0 , 0 ) (0,0)(0,0)出发，到矩形的右下角格子( n − 1 , m − 1 ) (n - 1,m - 1)(n−1,m−1)结束；
2. 在这条路径中，每次只能从当前的格子移动到右边与它相邻的格子，或者从当前格子移动到下面与它相邻的格子。
例如：在下面这个矩形中，只有两条路径是合法的，它们分别是P 1 P_1P1：( 0 , 0 ) → ( 0 , 1 ) → ( 1 , 1 ) (0,0)\to (0,1)\to (1,1)(0,0)→(0,1)→(1,1)和P 2 P_2P2：( 0 , 0 ) → ( 1 , 0 ) → ( 1 , 1 ) (0,0) \to (1,0) \to (1,1)(0,0)→(1,0)→(1,1)。

对于一条合法的路径P PP，我们可以用一个字符串w ( P ) w(P)w(P)来表示，该字符串的长度为n + m − 2 n + m - 2n+m−2，其中只包含字符R \texttt RR或者字符D \texttt DD，第i ii个字符记录了路径P PP中第i ii步的移动方法。R \texttt RR表示移动到当前格子右边与它相邻的格子，D \texttt DD表示移动到当前格子下面与它相邻的格子。例如，上图中对于路径P 1 P_1P1，有w ( P 1 ) = RD w(P_1) = \texttt {RD}w(P1)=RD；而对于另一条路径P 2 P_2P2，有w ( P 2 ) = DR w(P_2) = \texttt {DR}w(P2)=DR。

同时，将每条合法路径P PP经过的每个格子上填入的数字依次连接后，会得到一个长度为n + m − 1 n + m - 1n+m−1的01 0101字符串，记为s ( P ) s(P)s(P)。例如，如果我们在格子( 0 , 0 ) (0,0)(0,0)和( 1 , 0 ) (1,0)(1,0)上填入数字0 00，在格子( 0 , 1 ) (0,1)(0,1)和( 1 , 1 ) (1,1)(1,1)上填入数字1 11（见上图红色数字），那么对于路径P 1 P_1P1，我们可以得到s ( P 1 ) = 011 s(P_1) = 011s(P1)=011，对于路径P 2 P_2P2，有s ( P 2 ) = 001 s(P_2) = 001s(P2)=001。

游戏要求小 D 找到一种填数字0 00、1 11的方法，使得对于两条路径P 1 P_1P1，P 2 P_2P2，如果w ( P 1 ) > w ( P 2 ) w(P_1) > w(P_2)w(P1)>w(P2)，那么必须s ( P 1 ) ≤ s ( P 2 ) s(P_1) ≤ s(P_2)s(P1)≤s(P2)。我们说字符串a aa比字符串b bb小，当且仅当字符串a aa的字典序小于字符串b bb的字典序，字典序的定义详见第一题。但是仅仅是找一种方法无法满足小 D 的好奇心，小 D 更想知道这个游戏有多少种玩法，也就是说，有多少种填数字的方法满足游戏的要求？

小 D 能力有限，希望你帮助他解决这个问题，即有多少种填0 00、1 11的方法能满足题目要求。由于答案可能很大，你需要输出答案对10 9 + 7 10^9 + 7109+7取模的结果。

【输入】

输入文件共一行，包含两个正整数n , m n,mn,m，由一个空格分隔，表示矩形的大小。其中n nn表示矩形表格的行数，m mm表示矩形表格的列数。

【输出】

输出共一行，包含一个正整数，表示有多少种填0 00、1 11的方法能满足游戏的要求。注意：输出答案对10 9 + 7 10^9+7109+7取模的结果。

【输入样例】

2 2

【输出样例】

【算法标签】

#省选# #递推#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=8,M=1000005,mod=1e9+7;intn,m,ans;// n: 行数, m: 列数, ans: 最终答案// 打表结果：f[n][m] 表示 n 行 m 列时的方案数intf[N+1][N+1]={{0,0,0,0,0,0,0,0,0},{0,2,4,8,16,32,64,128,256},// n=1 时：2^m{0,4,12,36,108,324,972,2916,8748},// n=2 时：4 × 3^(m-1){0,8,36,112,336,1008,3024,9072,27216},{0,16,108,336,912,2688,8064,24192,72576},{0,32,324,1008,2688,7136,21312,63936,191808},{0,64,972,3024,8064,21312,56768,170112,510336},{0,128,2916,9072,24192,63936,170112,453504,1360128},{0,256,8748,27216,72576,191808,510336,1360128,3626752}};// 快速幂计算 a^b mod modintqmi(inta,intb){intmul=1;// 结果初始化为1while(b)// 当指数b不为0{if(b&1)// 如果当前位为1{mul=mul*a%mod;// 累乘}a=a*a%mod;// 底数平方b/=2;// 指数右移一位}returnmul;// 返回结果}signedmain(){intn,m;// 重新定义n,m，隐藏外部变量cin>>n>>m;// 输入行数和列数if(n>m)// 保证n ≤ m，方便处理{swap(n,m);}// 情况1：n=1，答案为2^mif(n==1){cout<<qmi(2,m)<<endl;}// 情况2：m ≤ 9，直接查表elseif(m<=9){cout<<f[n][m]<<endl;}// 情况3：m > 9，使用规律递推else{if(n!=8)// n不是8时，从表中取f[n][n+1]作为基准{ans=f[n][n+1];}else// n=8的特殊情况{ans=10879488;}// 递推：每增加一列，方案数乘以3for(inti=1;i<=m-n-1;i++){ans=ans*3%mod;}cout<<ans<<endl;}return0;// 程序正常结束}