[HDU 5459] Jesus Is Here [전달] [실현]

제목 링크: [HDU 5459] Jesus Is Here [전달] [실현]
제목 분석: 주어진 n 번 째 문자열 중 모든 c 사이 의 거 리 는 얼마 입 니까?( s[i]=s[i−2]+s[i−1] )
문제 풀이 방향: 우 리 는 f [i] 를 답 으로 설정 합 니 다. 그러면 정의: f [i] = f [i - 2] + f [i - 1] + (두 줄 의 거 리 를 뛰 어 넘 는 합) 두 줄 의 거 리 를 뛰 어 넘 는 것 과 어떻게 구 합 니까?sum [i] 배열 대 표를 설정 합 니 다. s [i] 에서 c 까지 의 거 리 를 합 친 다음 cnct [i] 배열 을 설정 합 니 다. s [i] 에서 c 의 개 수 를 대표 합 니 다.이 정의 가 있 으 면 두 줄 을 뛰 어 넘 는 거리 와 = cnct [i - 1] 건 8727 건, sum [i - 2] + cnt [i - 2] 건 8727 건 (cnct [i - 1] 건 8727 건, 렌 [i - 1] 건 - sum [i - 1] 건 중 렌 [i] 은 s [i] 의 길 이 를 대표 한다.마지막 으로 모델 링 에 주의 하면 답 을 얻 을 수 있다.
개인 적 인 느낌: 두 줄 의 거 리 를 뛰 어 넘 고 어떻게 구 해 야 할 지 모 르 겠 습 니 다. 인터넷 의 배열 정 의 를 보고 나 서 야 생각 이 생 겼 습 니 다.구체 적 인 코드 는 다음 과 같다.
#include<cstdio>
#define ll long long

const int MOD = 530600414;
const int MAXN = 201320;

ll f[MAXN], cnt[MAXN], len[MAXN], sum[MAXN];

void init()
{
    f[1] = f[2] = f[3] = 0;
    len[1] = 1, len[2] = 2, len[3] = 3;
    cnt[1] = 1, cnt[2] = 0, cnt[3] = 1;
    sum[1] = sum[2] = 0, sum[3] = 3;

    for (int i = 4; i <= 201314; ++i)
    {
        len[i] = (len[i - 2] + len[i - 1]) % MOD;
        cnt[i] = (cnt[i - 2] + cnt[i - 1]) % MOD;
        sum[i] = (sum[i - 2] + cnt[i - 2] * len[i - 1] + sum[i - 1]) % MOD;
        f[i] = (f[i - 2] + f[i - 1]
                + (cnt[i - 1] * sum[i - 2]) % MOD
                + (cnt[i - 2] * ((cnt[i - 1] * len[i - 1]) % MOD + MOD - sum[i - 1])) % MOD) % MOD;
    }
}

int main()
{
    int t, n;
    init();
    for (int kase = scanf("%d", &t); kase <= t; ++kase)
    {
        scanf("%d", &n);
        printf("Case #%d: %lld
"
, kase, f[n]); } return 0; }

좋은 웹페이지 즐겨찾기