春花形态计数算法
花
最新推荐文章于 2022-05-05 09:04:37 发布

David__TT 于 2019-01-22 20:02:59 发布
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
题目描述
某乔为了解花的生长习性,采集了很多春花来研究。
但其中混杂了一些普通的花,为了区别它们,某乔研究出春花的一些特征:春花有S种形态,每天都会展现出某种形态。在N天中,如果有且仅有一次:连续3天都是某种形态,那么它就是一朵春花。
例如:假设每天的形态分别为:AABBBC,那么这就是一朵春花。
但例如:AAABCDDDEEF,AABBBBC,YHNDSB就不是春花。
第一个因为A和D各有1次连续三天是同一种形态。
第二个在[3, 6]天中,形态B存在2次连续三天是相同的。
第三个因为辱骂出题人没有出现连续三天是同一形态。
现在,某乔想知道,给出N, S,一共存在多少种春花可能表现的形态?答案可能很大,对10^9+7取模
输入
一个整数T,表示测试数据组数。
每组测试数据占一行,两个整数,分别表示L和S。
输出
对每组数据,输出一个整数表示答案。
样例输入
复制样例数据
1
3 7
样例输出
7
提示
一共有7种形态,每种形态能构成1个方案。
对于60%的数据,L≤30,S≤26。
对于80%的数据,L≤10000,S≤26。
对于100%的数据,L≤100000,S≤100000。
dp[i][j][k]到第i个,连续j个,k表示是否已经有三个连续的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
#define lowbit(x) x&(-x)
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int t;
int dp[100050][5][2];
ll n,s,ans;
int main()
{
t=read();
while(t--)
{
cin>>n>>s;
dp[1][1][0]=s;
for(int i=2;i<=n;i++)
{
dp[i][1][0]=((dp[i-1][2][0]%mod+dp[i-1][1][0]%mod)%mod*(s-1)%mod)%mod;
dp[i][2][0]=dp[i-1][1][0];
dp[i][3][1]=dp[i-1][2][0];
dp[i][2][1]=dp[i-1][1][1];
dp[i][1][1]=((dp[i-1][1][1]%mod+dp[i-1][2][1]%mod+dp[i-1][3][1]%mod)%mod*(s-1)%mod)%mod;
}
ans=(dp[n][1][1]%mod+dp[n][2][1]%mod+dp[n][3][1]%mod)%mod;
cout<<ans<<endl;
}
return 0;
}
相关知识
基于机器视觉的昆虫种类及计数检测研究
基于机器视觉的害虫种类及计数检测研究
基于深度学习的粘虫板图像害虫识别与计数
基于机器视觉的果园性诱害虫在线识别与计数方法研究
算法很美 笔记 2.递归与算法分析
C++ 算法篇 穷举(枚举)
送春花
具有筛选器支持的唯一值计数
有机薄膜电容器多功能全自动光纤计数包装机电容点数包装机经济发展状况
送春花图片
原文链接: 春花形态计数算法 https://m.huajiangbk.com/newsview1293749.html
| 上一篇: 三种将iCloud照片导出的简单... | 下一篇: 犯了这几个错误,吊兰新叶长不出来... |



