(1) rockZ의 블로그에서
　　

 

UVa 10328 - Coin Toss(점진)

제목: 동전 한 개를 주고 n번을 던지며 최소 k개의 정면이 위로 올라가는 상황이 몇 가지가 있는지 물어본다.
 
원제에서 최소 k개의 H가 연속되는 상황이 나타나면 손을 대기 어렵다고 물었다.우리는 문제를 한번 바꾸어 볼 수 있다.
dp[i][j]를 설정하면 i개의 동전을 던지면 여러 j개의 H가 연속되는 상황을 나타낸다.
실제로 원제의 출현은 최소 k개의 H를 연속으로 나타낸다. 즉, 연속 k개의 H, k+1개의 H가 나타난다.n개의 H를 합치면 dp[n][n]-dp[n][k-1]와 같다. 즉, 연속에서 여러 n개의 H까지의 상황(사실 이것은 모든 투척 상황의 종수)에서 연속에서 여러 개의 H까지의 상황을 빼면 얻은 모든 상황은 적어도 k개의 연속적인 H가 있어야 한다.
이제 문제는 dp[i][j]를 어떻게 구하는가로 바뀌었다.
i<=j를 고려할 때 dp[i][j]=dp[i-1][j]*2, 즉 이전 단계에서 얻은 던지기 서열 뒤에 정과 반 두 가지 상황이 증가한다. 만약에 연속적인 H 개수가 j개보다 많으면 이런 상황은 불법이지만 이때 이런 상황이 발생하지 않을 것이 분명하다.
i>j일 때 dp[i][j]=dp[i-1][j]*2를 계속 사용하면 안 됩니다.만약에 i-j에서 i-1까지 모두 H가 된다면 이때 i-j에서 i-1까지 모두 H를 추가하면 연속적인 H가 j개보다 많은 불법 상태가 발생하기 때문에 우리는 i-j에서 i-1까지 모두 H인 상황을 줄여야 한다.그럼 이런 경우는 몇 가지일까요?우리는 이 상태가 어떻게 전이되었는지 고려한다.제 i-j-1의 위치가 무엇인지 생각해 보세요.분명히 F일 거예요.H면 불법상태가 될 수도 있어.그럼 i-j-1 이전 자리는요?H와 F를 막론하고 연속적인 H 개수가 j보다 많은 불법 상태가 나타나지 않으면 된다. 이것이 바로 dp[i-j-2][j]이다.
그러면 dp[i][j]=dp[i-1][j]*2-dp[i-j-2][j].
그래도 부족해.우리의 이전 추론은 모두 i-j-1의 위치가 반드시 존재하는 전제에서 (i>j는 i-j-1의 위치가 반드시 존재한다는 것을 보장할 수 없다). 그러면 i-j-1의 위치가 존재하지 않으면 i-j-2의 위치도 존재하지 않고 상술한 방정식도 성립되지 않는다.그러나 이런 상황은 매우 보고 싶다. 이때 반드시 i==j+1이다. 첫 번째 위치부터 첫 번째 위치까지 모두 H이다. 이런 상황만 있기 때문에 방정식은 dp[i][j]=dp[i-1][j]*2-1로 변한다.
요약:
dp[i][j]는 i개의 동전을 던지면 여러 j개의 H가 연속되는 상황을 나타낸다.
dp[0][j]=1
i<=j:dp[i][j]=dp[i-1][j]*2
i>j :i==j+1:dp[i][j]=dp[i-1][j]*2-1
      else: dp[i][j]=dp[i-1][j]*2-dp[i-j-2][j]
ans=dp[n][n]-dp[n][k-1]
큰 숫자가 필요하다.
 
 
(2) accagin으로 이동하는 블로그:http://blog.csdn.net/cc_again/article/details/24841249
제목 링크:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5170
 
Attack on Titans Time Limit: 2 Seconds      Memory Limit: 65536 KB
 
Over centuries ago, mankind faced a new enemy, the Titans. The difference of power between mankind and their newfound enemy was overwhelming. Soon, mankind was driven to the brink of extinction. Luckily, the surviving humans managed to build three walls: Wall Maria, Wall Rose and Wall Sina. Owing to the protection of the walls, they lived in peace for more than one hundred years.
But not for long, a colossal Titan appeared out of nowhere. Instantly, the walls were shattered, along with the illusory peace of everyday life. Wall Maria was abandoned and human activity was pushed back to Wall Rose. Then mankind began to realize, hiding behind the walls equaled to death and they should manage an attack on the Titans.
So, Captain Levi, the strongest ever human being, was ordered to set up a special operation squad of N people, numbered from 1 to N. Each number should be assigned to a soldier. There are three corps that the soldiers come from: the Garrison, the Recon Corp and the Military Police. While members of the Garrison are stationed at the walls and defend the cities, the Recon Corps put their lives on the line and fight the Titans in their own territory. And Military Police serve the King by controlling the crowds and protecting order. In order to make the team more powerful, Levi will take advantage of the differences between the corps and some conditions must be met.
The Garrisons are good at team work, so Levi wants there to be at least M Garrison members assigned with continuous numbers. On the other hand, members of the Recon Corp are all elite forces of mankind. There should be no more than K Recon Corp members assigned with continuous numbers, which is redundant. Assume there is unlimited amount of members in each corp, Levi wants to know how many ways there are to arrange the special operation squad.

Input

There are multiple test cases. For each case, there is a line containing 3 integers N (0 < N < 1000000), M (0 < M < 10000) and K (0 < K < 10000), separated by spaces.

Output

One line for each case, you should output the number of ways mod 1000000007.

Sample Input

3 2 2

Sample Output

5

Hint

Denote the Garrison, the Recon Corp and the Military Police as G, R and P. Reasonable arrangements are: GGG, GGR, GGP, RGG, PGG.
 
제목:
n명의 병사에게 줄을 서고 각 병사에게 3종의 G, R, P를 선택할 수 있다. 적어도 m개의 연속 G병사가 있고 최대 k개의 연속 R병사의 배열 종수가 있어야 한다.
문제 해결 방법:
dp 점차적 추진.
먼저 문제를 다중 연속의 상황으로 전환한다. 최대 k개의 연속 R, 최대 n개의 연속 G 상황[빼기]에서 최대 k개의 연속 R, 최대 (m-1)개의 연속 G 상황.
기껏해야 상황을 비교적 잘 고려하고, 적어도 상황은 비교적 복잡하며, 시합할 때 줄곧 최소한의 범위 안에 처박혀 있으니, 점차로 미룰 줄은 생각지도 못했다.
//dp[i][0]는 i번째가 G임을 나타내며, 많으면 u개의 연속 G가 있고, 많으면 v개의 연속 R의 개수가 있다//여기 u와 v가 고정되어 있음을 나타낸다.
//dp[i][1]은 i번째가 R임을 나타냅니다.
//d[i][2]는 i번째 i가 P임을 나타냅니다.
i가 P인 경우 연속적인 R과 G에 영향을 미치지 않을 것을 잘 고려하면 dp[i][2]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
i가 G인 경우
만약에 i<=u를 아무리 놓아도 u개의 연속적인 G라는 제한 조건을 초과하지 않기 때문에 dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
만약에 i=u+1일 때 앞의 u개가 모두 G를 넣은 상황을 배제하려면 dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-1;
만약에 i>u+1일 때 i-1에서 i-u까지 G를 넣은 상황을 배제하려면 dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-dp[i-1][2]-dp[i-u-1][1]-dp[i-u-1][2];
                             
 
i가 R인 경우
만약에 i<=v일 때 아무리 놓아도 u개의 연속적인 G라는 제한 조건을 초과하지 않기 때문에 dp[i][1]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
만약에 i=v+1일 때 전 v개가 모두 G를 넣은 상황을 배제하려면 dp[i][1]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-1;
만약에 i>v+1일 때 i-1에서 i-v까지 G를 넣은 상황을 배제하려면 dp[i][1]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-dp[i-1][0]-dp[i-v-1][0]-dp[i-v-1][2];

//#include<CSpreadSheet.h>  
  
#include<iostream>  
#include<cmath>  
#include<cstdio>  
#include<sstream>  
#include<cstdlib>  
#include<string>  
#include<string.h>  
#include<cstring>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<set>  
#include<stack>  
#include<list>  
#include<queue>  
#include<ctime>  
#include<bitset>  
#include<cmath>  
#define eps 1e-6  
#define INF 0x3f3f3f3f  
#define PI acos(-1.0)  
#define ll __int64  
#define LL long long  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
#define M 1000000007  
//#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
#define Maxn 1100000  
  
LL dp[Maxn][5]; //dp[i][0]   i  G，   u   G，   v   R     
                //dp[i][1]   i  R，....  
                //dp[i][2]   i  P，....  
LL n,m,k,u,v;  
  
LL Cal()  
{  
    dp[0][0]=1; //      
    dp[0][1]=0;  
    dp[0][2]=0;  
  
    for(int i=1;i<=n;i++)  
    {  
       LL sum=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%M;  
       dp[i][2]=sum;  
  
       if(i<=u)  
            dp[i][0]=sum;  
       else if(i==u+1)  
            dp[i][0]=(sum-1)%M;  
       else  
            dp[i][0]=(sum-dp[i-u-1][1]-dp[i-u-1][2])%M;  
  
       if(i<=v)  
            dp[i][1]=sum;  
       else if(i==v+1)  
            dp[i][1]=(sum-1)%M;  
       else  
            dp[i][1]=(sum-dp[i-v-1][0]-dp[i-v-1][2])%M;  
  
       //printf("u:%lld v:%lld i:%d %lld %lld %lld
",u,v,i,dp[i][0],dp[i][1],dp[i][2]);  
       //system("pause");  
  
    }  
    return (dp[n][0]+dp[n][1]+dp[n][2])%M;  
}  
  
  
int main()  
{  
   //freopen("in.txt","r",stdin);  
   //freopen("out.txt","w",stdout);  
   while(~scanf("%lld%lld%lld",&n,&m,&k))  
   {  
       LL ans;  
       u=n,v=k;  
       ans=Cal();  
  
       //printf(":%lld
",ans);  
       //system("pause");  
  
       u=m-1,v=k;  
       //printf(":%lld
",Cal());  
       //system("pause");  
       ans=((ans-Cal())%M+M)%M;  
       printf("%lld
",ans);  
  
  
   }  
   return 0;  
}