czy123

| a_1  |  a_2|... |   a_n-1|a_n|
| ------------ | ------------ | ------------ | ------------ |
|   b_1| b_2|...  |   b_n-1|b_n|
a[n]：n列2行的格子从a_1开始，刷完全部格子的总方案。
b[n]: n列2行的格子从a_1开始，刷完全部格子且最后刷完的格子是b_1的总方案。

刷油漆从a_1出发，最后到b_1结束，很明显只能从a_2到b_2结束或从b_2到a_2（对角出发）结束，则n列格子a_1到b_1总方案数b[n]等于从a_2到b_2的总方案数*2 ；
然后对a[n] 分解 递推
```cpp
#include<iostream>
using namespace std;
#define N 1000000007 
/*
a[n]为n列格子从角落的一个格子开始刷的总可能数
b[n]为n列格子从角落的一个格子开始刷，最终回到起始格子的正下方的总数
b[n]=b[n-1]*2
四个角： 
a[n] = 2*a[n-1] + b[n] + 4 * a[n-2] 分3个方向
1.水平右走 2*a[n-2]+b[n]/2（b[n-1]） 
2.垂直下走 2*a[n-1]
3.斜向走 2*a[n-2]+b[n]/2 
sum+=4*a[n]
中间点:中间第i列上方点 总共n列 
水平右走到正下方点*剩余从角落走的种数：b[n-i+1]*2*a[i-1] 
水平左走到正下方点*剩余从角落走的种数：b[i]*2*a[n-i] 
中间第i列种数sum+=2*(b[n-i+1]*2*a[i-1]+b[i]*2*a[n-i] ) 
*/
int main()
{
    int n,i;
    long long a[1001],b[1001]; 
    long long  sum=0;
    cin>>n;
    b[1] = 1;
    for(i = 2; i <= n; i++){
        b[i] = (b[i-1] * 2) % N;
    }
    a[1] = 1;
    a[2] = 6;
    for(i = 3; i <= n; i++){
        a[i]=(2*a[i-1]+b[i]+4*a[i-2])%N;
    }
    sum+=4*a[n]; //四个角为起点的情况
    for(i = 2; i <= n-1; i++){//中间为起点
		sum+=2*(b[n-i+1]*2*a[i-1]+b[i]*2*a[n-i]);
		sum%=N; 
    }
   	cout<<sum;
}
```
```

0.0分

6 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

西单

完全是考验数学推理能力。。。、

2021-04-10 11:11:38

czy123

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

C语言训练-委派任务* （C语言代码）..................竟然是第一个

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

蓝桥杯2013年第四届真题-格子刷油漆-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

矩形面积交（Java代码）

printf基础练习2 （C语言代码）

九宫重排（C++代码）

printf基础练习2 （有点不明白）

WU-格式化数据输出（C语言代码）

WU-陶陶摘苹果2 （C++代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

czy123

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

C语言训练-委派任务* （C语言代码）..................竟然是第一个

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

蓝桥杯2013年第四届真题-格子刷油漆-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

矩形面积交 （Java代码）

printf基础练习2 （C语言代码）

九宫重排 （C++代码）

printf基础练习2 （有点不明白）

WU-格式化数据输出 （C语言代码）

WU-陶陶摘苹果2 （C++代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

　　评论区

矩形面积交（Java代码）

九宫重排（C++代码）

WU-格式化数据输出（C语言代码）