Codeforces Gym 100015B Ball Painting 找规律
Ball Painting
题目连接:
http://codeforces.com/gym/100015/attachments
Description
There are 2N white balls on a table in two rows, making a nice 2-by-N rectangle. Jon has a big paint bucket
full of black paint. (Don’t ask why.) He wants to paint all the balls black, but he would like to have some
math fun while doing it. (Again, don’t ask why.) First, he computed the number of di!erent ways to paint
all the balls black. In no time, he figured out that the answer is (2N)! and thought it was too easy. So, he
introduced some rules to make the problem more interesting.
• The first ball that Jon paints can be any one of the 2N balls.
• After that, each subsequent ball he paints must be adjacent to some black ball (that was already
painted). Two balls are assumed to be adjacent if they are next to each other horizontally, vertically,
or diagonally.
Jon was quite satisfied with the rules, so he started counting the number of ways to paint all the balls
according to them. Can you write a program to find the answer faster than Jon?
Input
The input consists of multiple test cases. Each test case consists of a single line containing an integer N,
where 1 ! N ! 1,000. The input terminates with a line with N = 0. For example:
1
2
3
0
Output
For each test case, print out a single line that contains the number of possible ways that Jon can paint all
the 2N balls according to his rules. The number can become very big, so print out the number modulo
1,000,000,007. For example, the correct output for the sample input above would be:
2
24
480
Sample Input
1
2
3
0
Sample Output
2
24
480
Hint
题意
给你2*n的矩阵,都是白色
1.一开始你随便选一个染成黑色
2.接下来你可以选择一个和黑色相邻的白色,染成黑色
问你有多少种染法
题解:
我是OEIS的,蛤蛤
正常做可以DP
代码
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
//(4-8*n)*a(n)+a(n+1) =0.
long long a[1200];
void pre()
{
a[1]=1;
a[2]=2;
for(int i=3;i<=1100;i++)
a[i]=(a[i-1]*(8LL*(i-1LL)-4LL))%mod;
}
long long n;
int main()
{
pre();
while(cin>>n)
{
if(n==0)break;
cout<<a[n+1]<<endl;
}
}
最新文章
- C 语言学习的第 04 课:编译器常见错误和警告(1)
- 彻底弄明白之数据结构中的排序七大算法-java实现
- HDU 1711 Number Sequence (KMP)
- (24)odoo中模型标识汇总
- 支持多人协作的在线免费作图工具:ProcessOn
- android中 回调方法,怎么转变为阻塞执行的方法
- 用DateTime.ToString(string format)输出不同格式的日期
- CruiseControl.NET : svnrevisionlabeller
- system2之:4-LVM逻辑卷管理
- Linux软件安装,RPM与YUM
- 飘逸的python - 赛程表算法
- (中等) POJ 3225 Help with Intervals , 线段树+集合。
- C# 高性能 TCP 服务的多种实现方式
- [Shiro] tutorial 1 :SecurityManager and Subject
- hive函数--编码解码
- Maven之pom.xml配置文件详解
- datatable 转list ,list转datatable
- 执行PowerShell脚本的时候出现";在此系 统上禁止运行脚本";错误
- css加载字体跨域问题
- nginx支持android、ios、微信扫一扫