SPBINARY - Xâu Nhị Phân
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 605, BASE = 1000000000, MAX_DIGIT = 25;
struct BigInteger {
int d[MAX_DIGIT], nDigit;
void operator = (const int &x) {
nDigit = 0; memset(d, 0, sizeof d);
for(int t = x; t != 0; t /= BASE) d[nDigit++] = t % BASE;
}
void operator += (const BigInteger &a) {
int rem = 0; nDigit = max(nDigit, a.nDigit);
for(int i = 0; i < nDigit; ++i) {
int p = d[i] + a.d[i] + rem;
if(p >= BASE) d[i] = p - BASE, rem = 1;
else d[i] = p, rem = 0;
}
if(rem) d[nDigit++] = rem;
}
void print() {
printf("%d", d[nDigit-1]);
for(int i = nDigit-2; i >= 0; --i) printf("%09d", d[i]);
printf("\n");
}
} f[N][N][2];
int main() {
int n, k; scanf("%d%d", &n, &k);
f[1][1][0] = 1; f[1][1][1] = 1;
for(int len = 1; len < n; ++len)
for(int cont = 1; cont <= k; ++cont)
for(int digit = 0; digit < 2; ++digit) {
if(cont < k) f[len+1][cont+1][digit] += f[len][cont][digit];
f[len+1][1][!digit] += f[len][cont][digit];
}
BigInteger res; res = 0;
for(int cont = 1; cont <= k; ++cont)
for(int digit = 0; digit < 2; ++digit)
res += f[n][cont][digit];
res.print();
return 0;
}