广告网站模板下载不了,网站建站设计,网站的域名,discuz网站论坛间帖子转移描述 小 D 特别喜欢玩游戏。这一天#xff0c;他在玩一款填数游戏。 这个填数游戏的棋盘是一个n m的矩形表格。玩家需要在表格的每个格子中填入一个数字#xff08;数字 0 或者数字 1#xff09;#xff0c;填数时需要满足一些限制。 下面我们来具体描述这些限制。 为了方… 描述 小 D 特别喜欢玩游戏。这一天他在玩一款填数游戏。 这个填数游戏的棋盘是一个n × m的矩形表格。玩家需要在表格的每个格子中填入一个数字数字 0 或者数字 1填数时需要满足一些限制。 下面我们来具体描述这些限制。 为了方便描述我们先给出一些定义 • 我们用每个格子的行列坐标来表示一个格子即行坐标列坐标。注意行列坐标均从 0 开始编号 • 合法路径 P一条路径是合法的当且仅当 这条路径从矩形表格的左上角的格子(0,0)出发到矩形的右下角格子(n − 1, m − 1)结束 在这条路径中每次只能从当前的格子移动到右边与它相邻的格子或者从当前格子移动到下面与它相邻的格子。 例如在下面这个矩形中只有两条路径是合法的它们分别是?1(0,0) → (0,1) →(1,1)和?2(0,0) → (1,0) → (1,1)。 对于一条合法的路径 P我们可以用一个字符串w§来表示该字符串的长度为n m − 2其中只包含字符“R”或者字符“D”第 i 个字符记录了路径 P 中第 i 步的移动方法“R”表示移动到当前格子右边与它相邻的格子“D”表示移动到当前格子下面与它相邻的格子。例如上图中对于路径?1有w(P1) “RD”而对于另一条路径?2有w(P2) “DR”。 同时将每条合法路径 P 经过的每个格子上填入的数字依次连接后会得到一个长度为n m − 1的 01 字符串记为 s§。例如如果我们在格子(0,0)和(1,0)上填入数字0在格子(0,1)和(1,1)上填入数字 1见上图红色数字。那么对于路径?1我们可以得到s(P1) “011”,对于路径?2有s(P2) “001”。 游戏要求小 D 找到一种填数字 0、1 的方法使得对于两条路径?1P2如果w(P1) w(P2)那么必须s(P1) ≤ s(P2)。我们说字符串 a 比字符串 b 小当且仅当字符串 a 的字典序小于字符串 b 的字典序字典序的定义详见第一题。但是仅仅是找一种方法无法满足小 D 的好奇心小 D 更想知道这个游戏有多少种玩法也就是说有多少种填数字的方法满足游戏的要求 小 D 能力有限希望你帮助他解决这个问题即有多少种填 0、1 的方法能满足题目要求。由于答案可能很大你需要输出答案对10^9 7取模的结果。 输入 输入文件共一行包含两个正整数 n、m由一个空格分隔表示矩形的大小。其中 n 表示矩形表格的行数m 表示矩形表格的列数。 输出 输出共一行包含一个正整数表示有多少种填 0、1 的方法能满足游戏的要求。 注意输出答案对 10^97 取模的结果。 样例输入 2 2 样例输出 12 提示 【样例解释】 【输入样例2】 5 5 【输出样例2】 7136 可以显然看出满足的首要条件是从左下到右上的任意一条对角线是单调不增的 显然看出n2n2n2的时候答案是4∗3m−14*3^{m-1}4∗3m−1 但是3的时候就懵逼了 只能暴力枚举3以内的然后50分滚粗 因为有这样一种情况(1,1),(1,2),(2,2),(3,2),(3,3)(1,1),(1,2),(2,2),(3,2),(3,3)(1,1),(1,2),(2,2),(3,2),(3,3)和(1,1),(2,1),(2,2),(2,3),(3,3)(1,1),(2,1),(2,2),(2,3),(3,3)(1,1),(2,1),(2,2),(2,3),(3,3)这两条路径就不行 正解是轮廓线状压dp 然而我不会 只能搜索打表 规律是一个三维的等比数列 跑了一下午终于跑出来了233…… 上代码我也不知道该怎么讲了 #includebits/stdc.h
using namespace std;
#define ll long long
const ll mod1e97;
int n,m;
inline int read(){char chgetchar();int res0;while(!isdigit(ch))chgetchar();while(isdigit(ch))res(res3)(res1)(ch^48),chgetchar();return res;
}
inline ll ksm(ll a,int n){ll res1;for(;n;n1,aa*a%mod)if(n1)resres*a%mod;return res%mod;
}
int main(){nread(),mread();if(nm)swap(n,m);if(n1){coutksm(2,m)\n;}if(n2){cout4*ksm(3,m-1)%mod\n;}if(n3){cout112*ksm(3,m-3)%mod\n;}if(n4){if(m4)puts(912);else cout2688*ksm(3,m-5)%mod\n;}if(n5){if(m5)puts(7136);else cout21312*ksm(3,m-6)%mod\n;}if(n6){if(m6)puts(56768);else cout170112*ksm(3,m-7)%mod\n;}if(n7){if(m7)puts(453504);else cout1360128*ksm(3,m-8)%mod\n;}if(n8){if(m8)puts(3626752);else cout10879488*ksm(3,m-9)%mod\n;}
}最后 推广一下另外几篇题解 DAY1T1铺设道路并查集 DAY1T2货币系统完全背包/搜索 DAY1T3赛道修建二分答案贪心策略 DAY2T1旅行基环树搜索 DAY2T2填数游戏暴力搜索找规律 DAY2T3保卫王国动态dpSplay 转载于:https://www.cnblogs.com/stargazer-cyk/p/10366392.html
