鲁班七号来袭

大家好，我是鲁班七号，今天来简简单单写个题解

题目分析

这道题目要求我们计算在n×m的矩形表格中填入0或1的方案数，满足对于任意两条合法路径P₁和P₂，如果w(P₁) > w(P₂)（路径表示的字符串字典序更大），那么必须有s(P₁) ≤ s(P₂)（路径上数字组成的字符串字典序更小或相等）。

解题思路

关键观察

‌1、路径字典序与数字字典序的关系：

题目要求路径字典序大的对应数字字典序必须小或相等。这意味着我们需要找到填数方案，使得路径字典序的增加伴随着数字字典序的减小或不变。

2、小规模情况分析：

从题目给出的样例可以看出：

2×2网格有12种方案
3×3网格有112种方案
5×5网格有7136种方案

‌3、状态转移

根据附件中的状态转移图，我们可以观察到二进制数的转换过程，这与题目中路径和数字序列的关系有相似之处。

解法实现

‌1、基本情况处理‌：

当n=1时，每个格子可以自由选择0或1，方案数为2^m
当n=2时，方案数为4×3^(m-1)
当n=3时，方案数为112×3^(m-3)

‌‌2、一般情况处理‌：

当m=n时，使用公式：(83×8^n + 5×2^(n+7)) / 384 mod P
当m≠n时，使用公式：(83×8^n + 2^(n+8)) × 3^(m-n-1) / 128 mod P

不再多说，

上代码！！！

CPP

#include<bits/stdc++.h>
#define P 1000000007
using namespace std;
int n,m,inv128=570312504,inv384=190104168;
int add(int x,int y)  {return x+y>=P?x+y-P:x+y;}
int dec(int x,int y)  {return x-y< 0?x-y+P:x-y;}
int mul(int x,int y)  {return 1ll*x*y%P;}
int power(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=mul(a,a))  if(b&1)  ans=mul(ans,a);
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	if(n>m)  swap(n,m);
	if(n==1)  printf("%d\n",power(2,m));
	else  if(n==2)  printf("%d\n",mul(4,power(3,m-1)));
	else  if(n==3)  printf("%d\n",mul(112,power(3,m-3)));
	else{
		if(m==n)  printf("%d\n",(83ll*power(8,n)%P+5ll*power(2,n+7)%P)*inv384%P);
		else  printf("%d\n",(83ll*power(8,n)%P+power(2,n+8))*power(3,m-n-1)%P*inv128%P);
	}
	return 0;
}

这道题目说实在的不是很难，推荐大家多做做这种题目。
那么我的题解就到这里啦。谢谢大家的观看。

题解：P5023 [NOIP 2018 提高组] 填数游戏

文章操作