题解 P5023 【填数游戏】
ouuan
2018-11-16 19:28:57
> 注:本文中以有序数对 $(x,y)$ 指代 $n=x,m=y$ 时的答案。
我在考场上没有推出 $(n,n)=(n-1,n-1)\times8-5\times2^n$,然而由于我写的暴力比较快?我在考场上把 $(8,8)$ 以内的答案全算出来了。
## 暴力
首先是两个结论:
### $1.$ 每一斜行左下是连着的 $1$,右上是连着的 $0$ ,或全 $1$ 、全 $0$
若不是的话就会存在一个格子右边是 $1$ 下面是 $0$ ,不符合要求。
### $2.$ 满足条件的等价条件是:每个格子右边的格子先往下再往右的路径小于等于下面的格子先往右再往下的路径。
![](https://i.loli.net/2018/11/16/5beea329f0125.png)
如上图,黄色路径 $\le$ 蓝色路径
因为蓝色路径是往下走后最小的路径,黄色路径是往右走后最大的路径。
然后就可以写出暴力了:
```cpp
#include <iostream>
#include <cstdio>
using namespace std;
const int N=100;
bool check(int x,int y);
void dfs(int sum);
int n,m,a[N][N],ans;
int main()
{
cin>>n>>m;
dfs(2);
cout<<ans;
return 0;
}
void dfs(int sum)
{
int i,j;
if (sum>n+m)
{
for (i=1;i<n;++i)
{
for (j=1;j<m;++j)
{
if (!check(i,j))
{
return;
}
}
}
++ans;
return;
}
dfs(sum+1);
for (i=n;i>=1;--i) //将左下填成1
{
if (sum-i>=1&&sum-i<=m)
{
a[i][sum-i]=1;
dfs(sum+1);
}
}
for (i=n;i>=1;--i) //回溯时复原
{
if (sum-i>=1&&sum-i<=m)
{
a[i][sum-i]=0;
}
}
}
bool check(int x,int y)
{
int rx=x,ry=y+1,dx=x+1,dy=y;
while (rx+ry<=n+m)
{
if (a[rx][ry]!=a[dx][dy])
{
return a[rx][ry]<a[dx][dy];
}
if (rx<n)
{
++rx;
}
else
{
++ry;
}
if (dy<m)
{
++dy;
}
else
{
++dx;
}
}
return true;
}
```
## 规律
虽然 $n,m$ 较大时这个暴力还是要跑很久,但我们可以先跑出 $(3,10)$ 之内的所有解,可以很快跑出来,并发现 $(1,m)=2^m$(因为任意填都合法),$(n,m)=(n,m-1)\times3\quad(n\ge2,m>n+1)$,而且$(n,m)=(m,n)$ 。
只计算 $(n,n)$ 和 $(n,n+1)$,可以在 $10min$ ~ $30min$ 左右跑出 $(8,8)$ 内的所有解。如果一进考场就开始跑这题的暴力而且机子不是太慢应该可以跑出 $(8,9)$ ,然而我考场上没有跑出来...事实上不算出 $(8,9)$ 在洛谷的数据已经可以得到 $90$ 分了。
再仔细看一眼打出来的表,发现 $(n,n+1)=(n,n)\times3-3\times2^n\quad(n\ge4)$,然后就可以算出 $(8,9)$ 了。
## 代码
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const long long Ans[9][2]={{0,0},{0,0},{12,36},{112,336},{912,2688},{7136,21312},{56768,170112},{453504,1360128},{3626752,10879488}}; //(n,n)和(n,n+1)
const long long M=1000000007;
long long n,m,ans=1;
int main()
{
int i;
cin>>n>>m;
if (n>m)
{
swap(n,m);
}
if (n==1)
{
for (i=30;i>=0;--i)
{
ans=ans*ans%M;
if (m&(1<<i))
{
ans=ans*2%M;
}
}
cout<<ans;
}
else
{
if (m==n)
{
cout<<Ans[n][0];
return 0;
}
else if (m==n+1)
{
cout<<Ans[n][1];
}
else
{
for (i=30;i>=0;--i)
{
ans=ans*ans%M;
if ((m-n-1)&(1<<i))
{
ans=ans*3%M;
}
}
cout<<ans*Ans[n][1]%M;
}
}
return 0;
}
```