A-解锁专家

NC200607. A-解锁专家

描述

阿炳是一个精通文理的小机灵鬼，它是一个解锁专家，也是一个诗人。一天，阿炳受邀前往黄台甫马哈那坤弃他哇劳狄希阿由他亚马哈底陆浦欧叻辣塔尼布黎隆乌冬帕拉查尼卫马哈洒坦,也就是今天俗称的曼谷，解一个被文字锁锁住的宝箱。
    文字锁是这样描述的，
对于给定的一个n，问存在多少正整数x满足：
1、x>0；
2、x二进制位的位数不超过n，例如5=101(2)，它的二进制位的位数就是3；
3、x的二进制形式，不存在连续的两个二进制位上的数都是1。例如 3=11(2)，则不满足条件，但是5=101(2) 则满足条件。
阿炳思考了5分钟后，望着山下的美景，不禁写起了诗：
                            飞花两岸照船红，
                            波光山色两盈盈。
                            那年私语小窗边，
                            妾心陌上悠扬蝶。
原来阿炳不会解，为了掩饰尴尬，只好作诗缓解一些尴尬的气氛，阿炳作为一个知名解锁专家，当然是要面子的嘛，所以，阿炳请你帮帮他解决这个问题。

输入描述

多测试数据样例，测试样例组数不超过10000；
每组数据一行，一个数n（1 ≤ n ≤ 100）。

输出描述

每组数据输出一个数，满足条件的正整数x的个数取模433494437（即答案需要%433494437）

示例1

输入:

输出:

说明:

当n=1时，只有x=1满足条件。

示例2

输入:

输出:

说明:

当n=3时，有x=1(001), x=2(010), x=4(100), x=5(101)共4种情况。

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

Python3(3.5.2) 解法, 执行用时: 269ms, 内存消耗: 4180K, 提交时间: 2019-12-29 12:16:17

while 1:
    try:
        n=int(input())
    except:
        break
    arr = [0 for _ in range(n+1)]
    arr[1]=1
    for i in range(2,n+1):
        arr[i]=(arr[i-1]+arr[i-2]+1)%433494437
    print(arr[n])

C++(clang++11) 解法, 执行用时: 23ms, 内存消耗: 488K, 提交时间: 2021-04-16 00:34:32

#include<iostream>
using namespace std;
int a[105];
int main(){
	int n;
a[1]=1;
a[2]=2;
for(int i=3;i<=100;i++){
	a[i]=(a[i-1]+a[i-2]+1)%433494437;
}	
while(cin>>n){
	printf("%d\n",a[n]);
}	
}

C(clang 3.9) 解法, 执行用时: 4ms, 内存消耗: 376K, 提交时间: 2019-12-29 13:36:15

#include <stdio.h>
int main()
{
	int a[101];a[1]=1;a[2]=2;
	int i;
	for(i=3;i<101;i++) a[i]=(a[i-1]+a[i-2]+1)%433494437;
		int n;
		while(~scanf("%d",&n))
		printf("%d\n",a[n]);
	
}

C++14(g++5.4) 解法, 执行用时: 9ms, 内存消耗: 380K, 提交时间: 2020-08-28 14:34:06

#include<bits/stdc++.h>
using namespace std;
int n,i=3,f[102]={0,1,2};
main()
{
	for(i=3;i<102;i++)
	    f[i]=(1+f[i-1]+f[i-2])%433494437;
	while(cin>>n)
		cout<<f[n]<<'\n';
}