求至少k个连续硬币为正面的情况数 是有限制的递推DP
我枯了 mian了半天把里面的关系理清楚 然后我高精又双叒写挂了QAQ
把高精+的c.a[i]+=p.a[i]+q.a[i]; 打成 c.a[i]=p.a[i]+q.a[i];
我就系个瓜娃几
把至少转为至多 将至少k个连续的H可以转换为→至多n~k个连续→至多n个连续的情况数-至多(k-1)个连续的情况数
dp[i][0/1]表示第i张牌为正/反至多有x个连续H的所有情况
i<=x : dp[i][0]=dp[i-1][0]+dp[i-1][1]
i==x+1 : dp[i][0]=dp[i-1][0]+dp[i-1][1]-1 因为第x+1的位置为H时 它前x个的情况就不要能为全为H的情况 故-1
i>x+1 : dp[i][0]=dp[i-1][0]+dp[i-1][1]-dp[i-x-1][1] 当i-1~i-x的位置全为H时 i的位置不能为H i-x-1一定为T
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define rg register 4 const int N=100+55; 5 const int base=10000,power=4; 6 int n,k; 7 8 template<class t>void rd(t &x) 9 { 10 x=0;int w=0;char ch=0; 11 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 12 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 13 x=w?-x:x; 14 } 15 16 struct num{ 17 int a[1000]; 18 num(){memset(a,0,sizeof(a));} 19 num(int x) 20 { 21 memset(a,0,sizeof(a)); 22 int t=0; 23 while(x) a[++t]=x%base,x/=base; 24 a[0]=t; 25 } 26 void print() 27 { 28 printf("%d",a[a[0]]); 29 for(rg int i=a[0]-1;i>=1;--i) printf("%0*d",power,a[i]); 30 } 31 }sum,ans,e; 32 33 num operator +(const num &p,const num &q) 34 { 35 num c; 36 c.a[0]=max(p.a[0],q.a[0]); 37 for(rg int i=1;i<=c.a[0];++i) 38 { 39 c.a[i]+=p.a[i]+q.a[i]; 40 c.a[i+1]+=c.a[i]/base,c.a[i]%=base; 41 } 42 if(c.a[c.a[0]+1]) ++c.a[0]; 43 return c; 44 } 45 46 num operator -(const num &p,const num &q) 47 { 48 num c=p; 49 for(int i=1;i<=c.a[0];++i) 50 { 51 c.a[i]-=q.a[i]; 52 if(c.a[i]<0) c.a[i]+=base,--c.a[i+1]; 53 } 54 while(c.a[0]>0&&!c.a[c.a[0]]) --c.a[0]; 55 return c; 56 } 57 58 num work(int x) 59 { 60 num f[N][2]; 61 f[0][0]=e; 62 for(rg int i=1;i<=n;++i) 63 { 64 sum=f[i-1][0]+f[i-1][1]; 65 f[i][1]=sum; 66 if(i<=x) f[i][0]=sum; 67 else if(i==x+1) f[i][0]=sum-e; 68 else if(i>x+1) f[i][0]=sum-f[i-x-1][1]; 69 } 70 return f[n][0]+f[n][1]; 71 } 72 73 int main() 74 { 75 // freopen("testdata.in-3.txt","r",stdin); 76 e=num(1); 77 while(scanf("%d%d",&n,&k)==2) 78 { 79 ans=work(n)-work(k-1); 80 ans.print(); 81 printf(" "); 82 } 83 return 0; 84 }
