Submission #65126271

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#define MOD_BY 1000000000
int add(int a, int b) {
  return a + b - MOD_BY * (a + b >= MOD_BY);
}
int sub(int a, int b) {
  return b == 0 ? a : add(a, MOD_BY - b);
}
int A[1123456];
int main(void) {
  int N, K;
  int i;
  if (scanf("%d%d", &N, &K) != 2) return 1;
  for (i = 0; i < K; i++) A[i] = 1;
  A[K] = K;
  for (i = K + 1; i <= N; i++) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

#define MOD_BY 1000000000

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

int sub(int a, int b) {
	return b == 0 ? a : add(a, MOD_BY - b);
}

int A[1123456];

int main(void) {
	int N, K;
	int i;
	if (scanf("%d%d", &N, &K) != 2) return 1;
	for (i = 0; i < K; i++) A[i] = 1;
	A[K] = K;
	for (i = K + 1; i <= N; i++) {
		A[i] = sub(add(A[i - 1], A[i - 1]), A[i - K - 1]);
	}
	printf("%d\n", A[N]);
	return 0;
}

Submission Info

Judge Result