输入一行,包含一个整数n。
输出一个整数,表示返回的答案,由于字符串的数量巨大,可能会溢出,请输出对取模后的答案。
1
1
只有“1”满足
2
2
只有“10”和“11”满足
3
3
只有“101”,“110”,“111”满足
时间复杂度。额外空间复杂度。
#include <stdio.h> #define MOD 0x20000000 int main(void) { int n; scanf("%d", &n); if (n == 1) { printf("%d\n", 1); return 0; } int next1 = 2, next2 = 1, tmp; n -= 2; while (n-- > 0) { tmp = (next1 + next2) % MOD; next2 = next1; next1 = tmp; } printf("%d\n", next1); return 0; }