B4401 题解
gitxiaozheng
·
·
题解
大家好啊，由于我喜欢组合数学，这里给出一个组合数学+动态规划的做法，该方法精细实现后可以拿到目前最优解。
解法分析
题目求“乘积值”为 11 的倍数的路径的总数，由于 11 是个质数，所以一条“乘积值”为 11 的倍数的路径所经过数中必含有 11 这个数，或者含有能被 11 整除的数。
考虑将问题拆分成以下步骤：
- 先求从网格左上角走到右下角的路径总数。
- 然后求出从网格左上角走到右下角“乘积值”不为 11 的倍数的路径总数。
- 相减就可以得出结果。
Step 1
路径总数可以通过组合数学去算。容易得到总路径数为 C^{h+w-2}_{h-1}。
::::info[你觉得这不容易得到？点击查看推导。]
从起点 (1,1) 到终点 (h,w)，每次只能向右或向下移动，总步数为 h+w-2，其中你需要向右移动 h-1 次，向下移动 w-1 次，每条路径的不同之处在于这些移动的顺序排列，这样一分析应该就很明显了。
::::
Step 2
这一步是一个经典的动态规划，有些类似于 P1002。
-
定义 dp_{i,j} 为从起点到点 (i,j) “乘积值”不为 11 的倍数的路径数，a_{i,j} 为点 (i,j) 所代表的数字。
-
如果点 (i,j) 代表的数字是 11 的倍数，那么 dp_{i,j} 就直接为 0 了，因为过不去。否则 dp_{i,j} 就是从上方来的路径数加上从左边来的路径数，注意在边界处的点，即 (1,j) 和 (i,1)，要么只能从上方来，要么从左边来，综上可以得到：
dp_{i,j}=\begin{cases}
1 & i=j=1\\
dp_{i,j-1} & i=1,j>1 \\
dp_{i-1,j} &j=1,i>1 \\
0 & 11\mid a_{i,j} \\
dp_{i,j-1}+dp_{i-1,j} & \text{otherwise}
\end{cases}
那么这一步的答案即为 dp_{h,w}。
想必都不难思考出来，但是如果你直接像下面这样开了二维数组就会直接内存爆炸。
//dp为全局数组
const int maxn=1e7+10;
int dp[maxn][maxn];
因为万恶的数据范围：1\le h,w \le 10^7。
所以我们需要优化，注意到 1\le h \times w \le 10^7，针对这一重要性质有多种处理方式，这里我使用了笨办法——滚动数组，将 dp 数组干掉一维变成 dp_i，令 id=i \times w+j，转移方程就变成了这样：
dp_{id}=\begin{cases}
1 & i=j=1\\
dp_{id-w} & i=1,j>1 \\
dp_{id-1} &j=1,i>1 \\
0 & 11\mid a_{i,j} \\
dp_{id-w}+dp_{id-1} & \text{otherwise}
\end{cases}
跳的可能有点快，事实上把 id 代入进去一下就明白了。
现在这一步的答案为 dp_{h\times w+w}。
Step 3
想必大家都会。
上面两步得到的答案做差取模即可。
代码实现
::::warning[实现时注意事项]{open}
-
根据上述转移方程可以发现，转移过程中不需要用到 a_{i,j} 具体的值，所以我们可以开一个 bool 型一维数组，直接记录整个网格中哪些数能被 11 整除。
-
转移方程用的是 1-indexed，但是由于作者太菜了，代码只用了 0-indexed，这一点请阅读代码的读者注意。
-
当起点或者终点所代表的数字是 11 的倍数时，可以直接输出网格左上角到右下角的路径总数，因为无论如何路径“乘积值”都能被 11 整除，尽管这一点没注意到也应该能 AC，但这会使你的程序快很多。
-
由于算组合数要预处理阶乘的原因而导致代码不能通过赛时内存限制？不要紧！由于你只需要计算 1 次组合数，因此你可以把预处理阶乘的数组直接砍掉，算组合数时再算阶乘。
-
注意取模的问题！Step 3 由于涉及到作差，答案要加上模数后再取模！
-
本题输入量很大，建议用较快的读入方式。
::::
::::info[附注：0-index 时的转移方程]
（方便读者理解。）
$$
dp_{id}=\begin{cases}
1 & i=j=0\\
dp_{id-w} & i=0,j>0 \\
dp_{id-1} &j=0,i>0 \\
0 & 11\mid a_{i,j} \\
dp_{id-w}+dp_{id-1} & \text{otherwise}
\end{cases}
$$
现在 Step 2 的答案为 $dp_{(h-1)\times w+w-1}$。
::::
::::success[参考代码1]
代码附注释，轻微卡常，仅供参考。
这是[提交记录（与上文提到的最优解提交记录不一样）](https://www.luogu.com.cn/record/233770033)，内存超过了赛时限制。
```cpp line-numbers
//edit by devc++
//by gitxiaozheng/dakada
#include<bits/stdc++.h>
using namespace std;
#define L long long
#define iotype L //zigai
#define space putchar(' ')
#define enter putchar('\n')
inline iotype qcin();
void qcout(iotype);
string qcins();
void qcouts(string);
const int mod=1e9+7,maxn=1e7+9;
L jc[maxn+1];
int dp[maxn];
bitset<maxn> map1;
inline L qpow(L a,L b)
{
L ans=1;
L base=a%mod;
while(b>0)
{
if(b&1){
ans=(L)ans*base%mod;
}
base=(L)base*base%mod;
b>>=1;
}
return ans%mod;
}
L C(int n,int k){
if(k<0||k>n){
return 0;
}
return ((jc[n]*qpow(jc[k],mod-2)%mod)*qpow(jc[n-k],mod-2))%mod;
}
void Jc(int n){
jc[0]=jc[1]=1;
for(int j=1;j<=n;++j)
jc[j]=jc[j-1]*j%mod;
}
int main(){
//Your code is here...
int h=qcin(),w=qcin();
Jc(max(h+w,h));
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
//记录每个数字是否能被 11 整除
map1[i*w+j]=!(qcin()%11);
}
}
L tot=C(h+w-2,h-1);
//(h,w) 转化成滚动数组的下标为 h*w+w，再转换成0-indexed 即为 (h-1)*w+w-1。
if(map1[0]||map1[(h-1)*w+w-1]){
qcout(tot);
return 0;
}
dp[0]=1;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
int id=i*w+j;
if(map1[id]){
dp[id]=0;
continue;
}
//拆开来处理效率更高
if(i>0){
dp[id]=dp[id-w]%mod;
}
if(j>0){
dp[id]=(dp[id]+dp[id-1])%mod;
}
}
}
qcout((tot-dp[(h-1)*w+w-1]+mod)%mod);
return 0;
}
inline iotype qcin(){
iotype k=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-'){
f=-1;
}
c=getchar();
}
while(c>='0'&&c<='9'){
k=k*10+c-'0';
c=getchar();
}
return k*f;
}
void qcout(iotype x){
if(x<0){
putchar('-');
x=-x;
}
if(x<10){
putchar(x+'0');
}else {
qcout(x/10);
putchar(x%10+'0');
}
}
string qcins(){
string s="";
char c=getchar();
while(c==' '||c=='\n'||c=='\r'){
c=getchar();
}
while(c!=' '&&c!='\n'&&c!='\r'){
s+=c;
c=getchar();
}
return s;
}
void qcouts(string s){
for(int i=0;i<s.size();i++){
putchar(s[i]);
}
}
//over!
```
::::
::::error[参考代码2（不建议阅读）]
这篇代码内存满足赛时内存限制，但是码风更加猎奇，如果不是为了了解如何卡内存，则不建议阅读，仅供参考。
这是[提交记录（与上文提到的最优解提交记录一样）](https://www.luogu.com.cn/record/233903345)，内存在赛时限制之内。
```cpp
//edit by devc++
//by gitxiaozheng/dakada
#include<bits/stdc++.h>
using namespace std;
#define L long long
#define getchar getchar_unlocked
#define iotype L //zigai
#define space putchar(' ')
#define enter putchar('\n')
inline iotype qcin();
void qcout(iotype);
string qcins();
void qcouts(string);
const int mod=1e9+7,maxn=1e7+9;
int dp[maxn],h,w;
L V1=1,V2=1,V3=1;
bitset<maxn> map1;
inline L qpow(L a,L b)
{
L ans=1;
L base=a%mod;
while(b>0)
{
if(b&1){
ans=(L)ans*base%mod;
}
base=(L)base*base%mod;
b>>=1;
}
return ans%mod;
}
L TOT(){
return ((V1*qpow(V2,mod-2)%mod)*qpow(V3,mod-2))%mod;
}
void Jc(L n){
L a=1ll,b=1ll;
for(L j=1;j<=n;j++){
b=(a*j)%mod;
a=b;
if(j==h+w-2){
V1=b;
}
if(j==h-1){
V2=b;
}
if(j==w-1){
V3=b;
}
// jc[j]=jc[j-1]*j%mod;
}
}
int main(){
//Your code is here...
h=qcin(),w=qcin();
Jc(h+w-2);
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
map1[i*w+j]=!(qcin()%11);
}
}
L tot=TOT();
if(map1[0]||map1[(h-1)*w+w-1]){
qcout(tot);
return 0;
}
dp[0]=1;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
int id=i*w+j;
if(map1[id]){
dp[id]=0;
continue;
}
if(i>0){
dp[id]=dp[id-w]%mod;
}
if(j>0){
dp[id]=(dp[id]+dp[id-1])%mod;
}
}
}
qcout((tot-dp[(h-1)*w+w-1]+mod)%mod);
return 0;
}
inline iotype qcin(){
iotype k=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-'){
f=-1;
}
c=getchar();
}
while(c>='0'&&c<='9'){
k=k*10+c-'0';
c=getchar();
}
return k*f;
}
void qcout(iotype x){
if(x<0){
putchar('-');
x=-x;
}
if(x<10){
putchar(x+'0');
}else {
qcout(x/10);
putchar(x%10+'0');
}
}
string qcins(){
string s="";
char c=getchar();
while(c==' '||c=='\n'||c=='\r'){
c=getchar();
}
while(c!=' '&&c!='\n'&&c!='\r'){
s+=c;
c=getchar();
}
return s;
}
void qcouts(string s){
for(int i=0;i<s.size();i++){
putchar(s[i]);
}
}
//over
```
::::