HDU 1865 1sting 斐波那契数列 + 大数加法
发布时间:2020-12-14 01:28:57 所属栏目:大数据 来源:网络整理
导读:题目: http://acm.hdu.edu.cn/showproblem.php?pid=1865 题意: 给定一个长度不超过200的只有1的字符串,可以把相邻的两个1合并为2,问合并后有多少种不同的字符串 思路: 很容易发现答案是斐波那契数列,只不过200项会溢出,所以要用大数 #include iostrea
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1865 题意:给定一个长度不超过200的只有1的字符串,可以把相邻的两个1合并为2,问合并后有多少种不同的字符串 思路:很容易发现答案是斐波那契数列,只不过200项会溢出,所以要用大数 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 210;
char arr[N][N];
void add(char *s,char *s1,char *s2)
{
int len1 = strlen(s1),len2 = strlen(s2);
reverse(s1,s1 + len1);
reverse(s2,s2 + len2);
int t = 0;
for(int i = 0; i < len1 || i < len2; i++)
{
t += i < len1 ? s1[i]-'0' : 0;
t += i < len2 ? s2[i]-'0' : 0;
s[i] = t % 10 + '0';
t /= 10;
}
if(t) s[max(len1,len2)] = t + '0';
int len = strlen(s);
reverse(s,s + len);
reverse(s1,s2 + len2);
}
void table()
{
memset(arr,0,sizeof arr);
arr[1][0] = '1',arr[2][0] = '2';
for(int i = 3; i <= 200; i++)
add(arr[i],arr[i-2],arr[i-1]);
// for(int i = 1; i <= 200; i++)
// printf("%sn",arr[i]);
}
int main()
{
int t;
table();
scanf("%d",&t);
while(t--)
{
char str[N];
scanf("%s",str);
int len = strlen(str);
printf("%sn",arr[len]);
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |