DP + 접두사 와 - 황소 와 암소 - Acwing 1307

DP + 접두사 와 - 황소 와 암소 - Acwing 1307
존 은 소 N 마 리 를 데 리 고 집회 의 전시 활동 에 참가 하려 고 하 는데, 이 소 들 은 황소 일 수도 있 고 암소 일 수도 있다.
소 들 은 일렬 로 서 야 하지만, 수 소 는 싸움 을 좋아 하 는 것 이다. 황소 가 사 고 를 일 으 키 지 않도록 존 은 임의의 두 마리 의 암소 사이 에 적어도 K 마리 의 암소 가 있어 야 한다 고 결정 했다.
모두 몇 가지 줄 을 서 는 방법 이 있 는 지 계산 해 보 세 요. 모든 수 소 는 같은 것 으로 볼 수 있 고 모든 암소 도 마찬가지 입 니 다. 답 은 5000011 에 대해 서 입 니 다.
입력 형식
한 줄 에 정수 N 과 K 두 개 를 입력 하 십시오.
출력 형식
하나의 정 수 는 줄 을 서 는 방법 수 를 나타 낸다.
데이터 범위
1 ≤ N ≤ 1 0 5 , 0 ≤ K < N 1≤N≤10^5, 0≤K1≤N≤105,0≤K입력 예시:

4 2

출력 예시:

6

예 를 들 어 해석 하 다.
6 가지 방법 은 암컷, 암컷, 암컷, 암컷, 암컷, 암컷, 암컷, 암컷 이다.
분석:
우 리 는 수 소 를 1, 암소 를 0 으로 볼 수 있다. 우 리 는 수 소 를 1, 암소 를 0 으로 볼 수 있다. 우 리 는 수 소 를 1, 암소 를 0 으로 볼 수 있다.
문 제 는 구조 길이 가 n 인 01 꼬치 로 전환 되 어 임의의 두 개의 1 간 의 거리 가 k 보다 크 고 조건 을 만족 시 키 는 01 꼬치 의 방안 총 수 를 구한다.문 제 는 구조 길이 가 n 인 01 꼬치 로 전환 되 어 임의의 두 개의 1 간 의 거리 가 k 보다 크 고 조건 을 만족 시 키 는 01 꼬치 의 방안 총 수 를 구한다.문 제 는 구조 길이 가 n 인 01 꼬치 로 전환 되 어 임의의 두 개의 1 간 의 거리 가 k 보다 크 고 조건 을 만족 시 키 는 01 꼬치 의 방안 총 수 를 구한다.
상태 표시:
f [i]: 마지막 1 을 i 위 에 놓 고 조건 을 만족 시 키 는 방안 의 총수.f [i]: 마지막 1 위 는 i 위 에 놓 고 조건 을 만족 시 키 는 방안 의 총수 입 니 다.f [i]: 마지막 1 위 는 i 위 에 놓 고 조건 을 만족 시 키 는 방안 의 총수 입 니 다.
i 위 는 1 을 놓 으 면 1 부터 i - k - 1 까지 임 의 할 수 있 기 때문에 f [i] = ＞ j = 0 i - k + 1 f [j], 그 중에서 i - k - 1 > = 0.i 위 는 1 을 놓 으 면 1 부터 i - k - 1 까지 마음대로 할 수 있 으 므 로 f [i] = \ sum{j = 0} ^ {i - k + 1} f [j], 그 중 i - k - 1 > = 0.i 위 는 1 을 놓 으 면 1 부터 i - k - 1 까지 임 의 할 수 있 기 때문에 f [i] = ＞ j = 0 i - k + 1 f [j], 그 중에서 i - k - 1 > = 0.
i - k - 1 < 0 이면 f [i] = 1 은 1 개 만 포함 한 다 는 뜻 이다.i - k - 1 < 0, f [i] = 1 은 1 개 만 포함 한 다 는 뜻 이다.i - k - 1 < 0, f [i] = 1 은 1 개 만 포함 한 다 는 뜻 이다.
경계 초기 화: f [0] = 1, f [1] 를 정확하게 계산 할 수 있 습 니 다. i - k - 1 < 0 시, 우 리 는 f [0] 를 누적 하면 됩 니 다.초기 화 경계: f [0] = 1, f [1] 를 정확하게 계산 할 수 있 습 니 다. i - k - 1 < 0 시, 우 리 는 f [0] 를 누적 하면 됩 니 다.초기 화 경계: f [0] = 1, f [1] 를 정확하게 계산 할 수 있 습 니 다. i - k - 1 < 0 시 에 우 리 는 f [0] 를 누적 하면 됩 니 다.
접두사 와 접 두 사 를 자주 구 해 야 하기 때문에 우 리 는 푸 시 하면 서 접두사 와 배열 s [i] = ＞ j = 1 i f [j] 를 계산 할 수 있다.접두사 와 접 두 사 를 자주 구 해 야 하기 때문에 접두사 와 배열 s [i] = \ sum{j=1}^if[j]。 접두사 와 접 두 사 를 자주 구 해 야 하기 때문에 우 리 는 푸 시 하면 서 접두사 와 배열 s [i] = ＞ j = 1i f [j] 를 계산 할 수 있다.
마지막 출력 s [n].마지막 출력 s [n].마지막 출력 s [n].
코드:

#include
#include

using namespace std;

const int N=1e5+10, mod=5000011;

int n,k;
int f[N],s[N];

int main()
{
     
    cin>>n>>k;
    
    f[0]=s[0]=1;
    for(int i=1;i<=n;i++)
    {
     
        f[i]=s[max(i-k-1,0)];
        s[i]=(s[i-1]+f[i])%mod;
    }
    
    cout<<s[n]<<endl;
    
    return 0;
}