P1812 骨牌 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2024年3月19日 19:25

骨牌题解：

P1812

回复 0 | 赞 0 | 浏览 462

动态规划-斐波那契数列也可以压缩不用dp数组，关键在于找规律，思路来源http://t.csdnimg.cn/Y81XV #include <iostream> #include <vector> using namespace std; /* n=1 , 1 n=2 , 2 n=3 , 3 n=4 , 5 发现规律：f(n)=f(n-1)+f(n-2) 也可以从排放形状入手带入知道，f(6)=13 */ int main(){ int n; cin >> n; // 读取n值 ...

2023年3月25日 12:55

斐波那契快速幂

P1812

回复 0 | 赞 0 | 浏览 1.8k

#include <iostream> using namespace std; typedef long long ll; typedef pair<ll,ll> pii; const ll MOD=999983; pii db(pii k) { k.first%=MOD; k.second%=MOD; return {(2*k.first*k.second%MOD+MOD-k.first*k.first%MOD)%MOD,(k.second*k.second+k.first*k.first)%MOD}; } pii fib(in...

2021年9月7日 14:27

等同于斐波那契数列

P1812

回复 0 | 赞 0 | 浏览 7.0k

题目看似花俏，2*n乍一看还以为要开二维数组。但其实列举一下可以发现： 2*1 = 1种铺法 2*2 = 2种铺法 2*3 = 3种 2*4 = 5种 2*5 = 8种 2*6 = 13种符合斐波那契数列。。也就是第n块的铺法就是第n-1块铺好的基础上加一块1*2，或者在n-2铺好的基础上加一块2*2 #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<stdio.h> using namespace std; const int maxn...

2021年3月1日 23:39

找规律

P1812

回复 0 | 赞 1 | 浏览 7.6k

#include const int maxn = 10010; int dp[maxn]; int main(){ int n; scanf("%d", &n); dp[1] = 1; dp[2] = 2; for(int i = 3; i <= n; i++){ dp[i] = (dp[i - 1] + dp[i - 2]) % 99998...

题目骨牌

题解数量4

热门题解

1 找规律

2 等同于斐波那契数列

3 斐波那契快速幂

4 骨牌题解：