题意:抛出n次硬币（有顺序），求至少k个以上的连续正面的情况的种数。
思路：转换成求抛n个硬币，至多k-1个连续的情况种数，用所有可能出现的情况种数减去至多k-1个的情况，就得到答案了。此题涉及大数加减。
分析：
（1）假设n=k，那么只有一种情况。
（2）假设n=k+1，那么有3种情况，包含k个的两种，k+1个的一种。
（3）假设k=1，那么只有无正面这一种的情况不能被考虑，其他都能算，那么就是（1<<n）-1种。（n个硬币有2^n种结果）
（4）其他情况考虑递推。先把问题的规模降低，最小就是1了，再逐渐增大，每次规模增加1，直到n为止。用dp[n+1]这么大的数组就够了，而dp[n]表示从第1个硬币到第n个硬币中最多出现k-1个连续正面的情况种数。到这步，可以直接将拿到的k自减一，假设结果为t。那么问题转成求抛第i个硬币时，它和它前面不能超过t个正面。
（5）基于上面第4步的分析。可以看出，在抛第t个之前（包括第t个），最多就出现t个正面，不可能超过抛的次数的。那么dp[0~k]可以一次性初始化为1<<i，也就是有这么多抛法其结果都不会超过t个正面啦。
（6）考虑在抛第k+1个的情况，顶多也就一种不合法，也就是全面都是正面，那么种数就是(1<<k+1)-1。
（7）考虑在抛大于第k+2的情况，不妨设为dp[k+2]=dp[k+1]*2，但是这里面包含了大于t个的情况，只可能出现这样的情况：第k+2个刚好抛到正面，如果其前面与其连续的刚好有t个正面，那么就会造成连续t+1个正面，非法！但是不可能出现多于t+2个连续的可能，如果多于t+2，那么假设当前为正面，其前面必须有t+1个连续，而dp[k+1]中不会记录有非法的情况，所以不考虑。那么出现与第k+2个刚好连起来是t+1个连续的情况会有多少种?(k+2)-t-1这个位置肯定是反面的，不然就会造成连续t+2个了，那么在k+2-t-2及其之前所有不超过t个连续的情况种数就是出现“与k相连t+1个正面”的情况种数，减去这个数量即可。
总之，对于i大于k+2的，dp[i]=dp[i-1]*2-dp[i-t-2]。推到dp[n]时，所有可能都出来了。用所有可能数减去此数：答案= (1<<n)-dp[n]。
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int n, k;
long long a[];
vector<string> ans;
vector<string> pre; bool comp(string num1,string num2)
{
int leng=num1.length(),i;
for(i=;i<leng;i++){if(num1[i]!='')break;}
num1=num1.substr(i,leng);
if(num1.length()==)num1=""; leng=num2.length();
for(i=;i<leng;i++){if(num2[i]!='')break;}
num2=num2.substr(i,leng);
if(num2.length()==)num2=""; if(num1.length()>num2.length())return true;
else if(num1.length()==num2.length())
{
if(num1>=num2)return true;
else return false;
}
else return false;
}
string _minus(string num1,string num2)
{
string result;
if(comp(num2,num1)){string ss=num1;num1=num2;num2=ss;}
reverse(num1.begin(),num1.end());
reverse(num2.begin(),num2.end()); result=""; int i;
for(i=;i<int(num1.length())&&i<int(num2.length());i++)
{
char c=num1[i]-num2[i]+;
result=result+c;
}
if(i<int(num1.length()))
for(;i<int(num1.length());i++)
result=result+num1[i]; int jiewei=;
for(i=;i<int(result.length());i++)
{
int zhi=result[i]-+jiewei;
if(zhi<) {zhi=zhi+;jiewei=-;}
else jiewei=;
result[i]=(char)(zhi+);
} for(i=result.length()-;i>=;i--)
if(result[i]!='')
break; result=result.substr(,i+);
reverse(result.begin(),result.end());
if(result.length()==)result="";
return result;
}
string sum(string s1,string s2)
{
if(s1.length()<s2.length())
{
string temp=s1;
s1=s2;
s2=temp;
}
int i,j;
for(i=s1.length()-,j=s2.length()-;i>=;i--,j--)
{
s1[i]=char(s1[i]+(j>=?s2[j]-'':)); //注意细节
if(s1[i]-''>=)
{
s1[i]=char((s1[i]-'')%+'');
if(i) s1[i-]++;
else s1=''+s1;
}
}
return s1;
} void cal64()
{
ans[]="";
for(int i=; i<=k; i++)
ans[i]=pre[i];
string tmp= sum(ans[k], ans[k]);
ans[k+]=_minus(tmp,""); for(int i=k+; i<=n; i++)
{
tmp=sum( ans[i-], ans[i-] );
ans[i]=_minus(tmp,ans[i-k-]);
}
cout<<_minus(pre[n], ans[n])<<endl; } void cal63()
{
a[]=;
for(int i=; i<=k; i++) //小于k的情况，直接2^k
a[i]=a[i-]+a[i-]; a[k+]=a[k]+a[k]-;
for(int i=k+; i<=n; i++)
a[i] = a[i-]-a[i-k-]+a[i-]; cout<<((long long)<<n)-a[n]<<endl;
}
void init()
{
string tmp;
ans.resize(,tmp);
pre.resize(,tmp);
pre[]="";
for(int i=; i<; i++)
pre[i]=sum(pre[i-], pre[i-]);
}
int main()
{
//freopen("input.txt","r",stdin);
init();
while(cin>>n>>k)
{ if(n==k)
{
cout<<""<<endl;
continue;
}
if(n==k+)
{
cout<<""<<endl;
continue;
}
if(k==)
{
cout<<_minus(pre[n],"")<<endl;
continue;
}
k--;
if(n<) //这里对抛62次以下的情况用longlong直接干掉。
cal63();
else //大于62就用大数来算
cal64(); }
return ;
}
AC代码