NKTOSS - Tung đồng xu
Tác giả: khuc_tuan
Ngôn ngữ: Java
import java.util.*;
import java.math.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
BigInteger[] F = new BigInteger[n+1];
F[0] = BigInteger.ONE;
BigInteger total = BigInteger.ONE;
for(int i=1;i<=n;++i) {
F[i] = total;
if(i<k) F[i] = F[i].add(BigInteger.ONE);
total = total.add( F[i]);
if(i>=k) total = total.subtract(F[i-k]);
}
BigInteger res = BigInteger.ONE;
for(int i=0;i<n;++i) res = res.multiply(BigInteger.valueOf(2));
System.out.println(res.subtract(F[n]));
}
}