列表

详情

NC220777. Domino铺设

描述

我们称在一个 的点阵中画出 n 条不相交的线的方式，为一种 矩形的 “Domino铺设”，例如

，一个图案称为 “Domino铺设” 的条件是：各线均不相交、每条线要么竖直要么水平、每条线连接两个格点；
如果我们将两个这样的图案叠加起来，就得到一组回路，这是由于每点都与两条线相连，例如，如果上面的线与这样的线：

，组合起来，结果就是：
而且，将，
和
组合起来也会得到同一组回路。但是，如果在第一个图案中交替用向上、向下、向上、向下、…的红色箭头，在第二个图案中交替用向下、向上、向下、向上、…的蓝色箭头，为那些竖直的线指定方向，我们就会得到从叠加的图案中构造出定向回路的唯一一种方案，例如：

通过这样的设定，构造这种定向回路图案的方案数是确定的。换句话说，如果两个回路相同，当且仅当构成两个回路的铺设完全相同。
给定正整数 n ，求出在 的点阵中构造定向回路图案的方案数，由于结果可能特别大，所以输出答案对 1000000007 取模后的结果。

输入描述

输入仅一行，一个正整数 n （） 。

输出描述

输出一个数，表示方案数，结果对 1000000007  取模。

示例1

输入: 

2

输出: 

4

说明:

n=2，即 2\times 2 的点阵中构造定向回路的方案数显然只有 4 种：

示例2

输入: 

3

输出: 

9

说明:

n=3，即 2\times 3 的点阵中构造定向回路的方案数显然只有 9 种：

示例3

输入: 

15

输出: 

974169

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 12ms, 内存消耗: 1144K, 提交时间: 2021-04-10 15:37:29 

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int mo=1e9+7;
int n,f[N];
int main()
{
	scanf("%d",&n);
	f[0]=1;
	f[1]=1;
	for (int i=2;i<=n;i++)
	{
		f[i]=(f[i-1]+f[i-2])%mo;
	}
	printf("%d",1LL*f[n]*f[n]%mo);
	return 0;
}

Python3 解法, 执行用时: 82ms, 内存消耗: 4628K, 提交时间: 2022-10-25 09:33:48 

a,b=1,1
n=int(input())
mod=1000000007 
for i in range(n):
    a,b=b%mod,(a+b)%mod
print((a**2)%mod)

上一题

© 2025 nowcoder.com