foj2204 Problem 2204 7 dp

Problem 2204 7 Accept: 50 Submit: 142 Time Limit: 2000 mSec Memory Limit: 65536 KB Problem Description n 레이블이 있는 공이 원을 이룹니다.공마다 두 가지 색깔이 있는데 검은색이나 흰색 염색을 선택할 수 있다.연속 백구 7개나 연속 흑구 7개가 나오지 않도록 하는 방안이 얼마나 있느냐고 물었다.
Input의 첫 번째 행에는 여러 개의 데이터가 있습니다.첫 번째 행 T는 그룹 수를 나타냅니다.(T <= 20)
각 조는 n을 포함하여 구의 개수를 나타낸다.(1 <= n <= 100000)
Output 각 그룹은 먼저 "Case #x:"(여기서 x는 현재 그룹 수) 행을 내보내고 그 다음에 프로젝트 수를 내보냅니다.프로젝트 수mod 2015.
Sample Input 2 7 1 Sample Output Case #1: 126 Case #2: 2 Source FOJ 시상식-2015년 10월
Submit Back Status Discuss는 루프를 선으로 만들고 선의 상황만 고려합니다.dp, dp[i][j][jf][k][kf]로 jfkf는 0으로 흰색을 나타내고 1로 검은색을 나타낸다.전체 식은 i개의 공이 있고 앞의 6개의 공 중 jf가 j개가 있고 kf가 k개가 있으면 7개가 부족할 때 뒤로 한 개의 공을 넣으면 검은색을 넣을 수도 있고 흰 공을 넣을 수도 있는데 두 가지 방법이 있다.컨디션 전이란 마지막 공과 다른 색깔의 공을 넣거나 같은 색깔의 공을 넣으면 7개 연속만 넣지 않으면 된다.다시 고리의 문제를 고려하면 앞뒤가 같은 색이면 앞뒤 6개와 뒤쪽 6개, 합쳐서 같은 색이 7을 넘지 않으면 된다.전체 시간의 복잡도는 o(n*7*7*2*2)이므로 아마ac도 될 것이다.

#define N 205
#define M 100005
#define maxn 205
#define MOD 1000000000000000007
int n,T;
short dp[100005][7][2][7][2];
int p[20],all;
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    fill(dp,0);
    dp[1][1][0][1][0] = 1;
    dp[1][1][1][1][1] = 1;
    For(i,1,100000){
        For(j,1,7)
            For(jf,0,2){
                for(int k = 1;k < 7;k++){
                    For(kf,0,2){
                        if(i <= 5){
                            if(j == i && k == i && jf == kf){
                                dp[i+1][j+1][jf][k+1][kf] = (dp[i+1][j+1][jf][k+1][kf] + dp[i][j][jf][k][kf]) % mod;
                                dp[i+1][j][jf][1][kf ^ 1] = (dp[i+1][j][jf][1][kf ^ 1] + dp[i][j][jf][k][kf]) % mod;
                            }
                            else {
                                dp[i+1][j][jf][k+1][kf] = (dp[i+1][j][jf][k+1][kf] + dp[i][j][jf][k][kf]) % mod;
                                dp[i+1][j][jf][1][kf ^ 1] = (dp[i+1][j][jf][1][kf ^ 1] + dp[i][j][jf][k][kf]) % mod;
                            }
                        }
                        else {
                            if(j < 7 && k + 1 < 7)
                                dp[i+1][j][jf][k+1][kf] = (dp[i+1][j][jf][k+1][kf] + dp[i][j][jf][k][kf]) % mod;
                            if(j < 7)
                                dp[i+1][j][jf][1][kf ^ 1] = (dp[i+1][j][jf][1][kf ^ 1] + dp[i][j][jf][k][kf]) % mod;
                        }
                    }
                }
            }
    }
     while(S(T)!=EOF)
    {
        int i = 0,ans;
        while(T--){
            S(n);
            ans = 0;
            For(j,1,7){
                For(jf,0,2){
                    For(k,1,7){
                        For(kf,0,2){
                            if(jf == kf){
                                if(min(j + k,n)< 7)
                                    ans = (ans + dp[n][j][jf][k][kf]) % mod;
                            }
                            else
                                ans = (ans + dp[n][j][jf][k][kf]) % mod;
                        }
                    }
                }
            }
            printf("Case #%d: %d
",++i,ans);
        }
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}