输入一行,包含一个整数n。
输出一个整数,表示返回的答案,由于字符串的数量巨大,可能会溢出,请输出对取模后的答案。
1
1
只有“1”满足
2
2
只有“10”和“11”满足
3
3
只有“101”,“110”,“111”满足
时间复杂度。额外空间复杂度。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { final static int MOD = 1 << 29; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); long n = Long.parseLong(br.readLine()); if(n == 1){ System.out.println(1); }else if(n == 2){ System.out.println(2); }else{ long[][] res = new long[][]{{1, 0}, {0, 1}}; long[][] base = new long[][]{{1, 1}, {1, 0}}; long p = n - 1; while(p > 0){ if((p & 1) != 0) res = multiMat(res, base); base = multiMat(base, base); p >>= 1; } System.out.println((res[0][0] + res[1][0]) % MOD); } } private static long[][] multiMat(long[][] A, long[][] B) { return new long[][]{{((A[0][0] * B[0][0] % MOD) + (A[0][1] * B[1][0] % MOD)) % MOD, ((A[0][0] * B[0][1] % MOD) + (A[0][1] * B[1][1] % MOD)) % MOD}, {((A[1][0] * B[0][0] % MOD) + (A[1][1] * B[1][0] % MOD)) % MOD, ((A[1][0] * B[0][1] % MOD) + (A[1][1] * B[1][1] % MOD)) % MOD}}; } }稍微再从正面解释一下为什么可以用斐波那契的套路,我们记函数F(i)可以返回长度为i的二进制字符串中满足题意的数量,调用函数F的条件是第一个字符必须为1(满足题意的二进制字符串的首字符一定是1,因为如果是0,则这个0的左边就没有1给它靠着了)。以i=8为例调用F(8),如果第二个字符是1,那从第二个字符开始可以调用F(7),如果第二个字符是0,那第三个字符肯定是1,否则第三个0左边就没有1给它靠着了,于是可以调用F(6),得到F(8)=F(7)+F(6)。
#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; }
设f(i)表示长度为i的【0左边必有1的二进制字符串的数量】:
import java.util.Scanner; public class Main { public static final int MOD = 1 << 29; public static void main(String[] args) { int n = new Scanner(System.in).nextInt(); System.out.println(getCount(n)); } public static int getCount(int n) { if (n <= 2) { return n; } int a = 1, b = 2; // f(1) = 1, f(2) = 2 for (int i = 3; i <= n; i++) { int tmp = (a + b) % MOD; a = b; b = tmp; } return b; } }
import java.util.*; public class Main{ public static final int mod = (int) Math.pow(2, 29); public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println(getMaxNum(n)); } /*假设p(i)表示0~i-1位置上的字符已经确定,这一段符合要求且第 i-1位上是'1',接下来i~n-1位置上进行穷举看有多少个字符串符合条件。 p(n-1)表示n-2位为1且之前已经定好了,最后一位只有两种可能,1或0 p(n)表示全部定好了所以只有一种可能了 对于普遍位置p(i),若i位置选了1,则=p(i+1); 若i位置选了0,则i+1位置必须选1,否则若选了0左边就没有一个1了,则=p(i+2) */ public static int getMaxNum(int n) { if (n < 1) return 0; if (n == 1) return 1; if (n == 2) return 2; int p1 = 1; int p2 = 2; int p = 3; for(int i = 3; i <= n; i++) { p = (p1+p2) % mod; p1 = p2; p2 = p; } return p; } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int mod = (int) Math.pow(2, 29); int a = 0, b = 1; for(int i=0; i<n; i++){ int c = (a + b) % mod; a = b; b = c; } System.out.println(b % mod); } }
#include<iostream> using namespace std; int main() { int n; cin>>n; long long dp1=1;//末尾为1满足条件数量 long long dp2=0;//末尾为0满足条件数量 for(int i=1;i<n;i++) { long long temp=dp1; dp1=(dp1+dp2)%(1<<29); dp2=temp; } cout<<(dp1+dp2)%(1<<29)<<endl; }