UVA10328 Coin Toss

考虑把答案拆成至多有(n)张朝上减去至少有(k-1)张朝上。
显然第一部分的答案就是(2^n)，考虑(DP)第二部分。设(dp[i][0/1])表示第(i)张是反面/正面的情况数。然后有：

[dp[i][0]=dp[i-1][0]+dp[i-1][1] ]

[dp[i][1]=dp[i-1][0]+dp[i-1][1]-dp[i-k-1][0] ]

然后处理下边界，比如(i=k+1)之类的。 然后这题的问题就转化为高精度了。显然我是不会的。所以就用$ int128 $水了。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

#define R register
#define LL __int128
const int inf = 0x3f3f3f3f;
const int MAXN = 100+10;

int n,k;
LL dp[MAXN][2];

inline void print(LL x) {
	if( x > 9 ) print(x / 10);
	putchar('0' + x % 10);
}

int main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	while(cin>>n>>k) {
		k--;
		memset(dp,0,sizeof(dp));
		dp[1][0] = 1; dp[1][1] = k ? 1 : 0;
		for(R int i = 2; i <= n ; i++ ) {
			dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
			if( i <= k ) dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
			if( i == k + 1 ) dp[i][1] = dp[i - 1][0] + dp[i - 1][1] - 1;
			if( i > k + 1) dp[i][1] = dp[i - 1][0] + dp[i - 1][1] - dp[i - k - 1][0];
		}
		LL ans1 = 1;
		for(R int i = 1; i <= n ; i++ ) ans1 = ans1 * 2;
		print(ans1 - dp[n][0] - dp[n][1]); putchar('
');
	}
	return 0;	
}