Submission #19243452


Source Code Expand

Copy
#include <stdio.h>

const int Mod = 1000000007;

int naive(int K, int N)
{
	int i, j, tmp[1001], sum = K;
	for (i = 0; i < K; i++) tmp[i] = 1;
	for (i = K, j = 0; i < N; i++) {
		sum -= tmp[j];
		if (sum < 0) sum += Mod;
		tmp[j] += sum;
		if (tmp[j] >= Mod) tmp[j] -= Mod;
		sum += tmp[j++];
		if (sum >= Mod) sum -= Mod;
		if (j == K) j = 0;
	}
	return tmp[(N-1)%K];
}

int solve(int K, int N)
{
	const int SIZE = 32000000 / K * K;
	int i, j, k;
	long long tmp[1001], block[1001][1001], sum, summ;
	for (j = 2, tmp[0] = 1, tmp[1] = 1; j < K; j++) tmp[j] = tmp[j-1] * 2 % Mod;
	sum = tmp[K-1] * 2 % Mod;
	for (i = K, j = 0; i <= SIZE - K; i++) {
		sum -= tmp[j];
		if (sum < 0) sum += Mod;
		tmp[j] += sum;
		if (tmp[j] >= Mod) tmp[j] -= Mod;
		sum += tmp[j++];
		if (sum >= Mod) sum -= Mod;
		if (j == K) j = 0;
	}
	for (k = K - 1; k >= 0; k--) {
		for (i = 0, summ = sum; i < K; i++) {
			block[k][i] = summ;
			summ -= tmp[j++];
			if (summ < 0) summ += Mod;
			if (j == K) j = 0;
		}
		
		sum -= tmp[j];
		if (sum < 0) sum += Mod;
		tmp[j] += sum;
		if (tmp[j] >= Mod) tmp[j] -= Mod;
		sum += tmp[j++];
		if (sum >= Mod) sum -= Mod;
		if (j == K) j = 0;
	}
	
	long long tmpp[1001];
	for (j = 0, k = K; j < K; j++) tmp[j] = K - j;
	while (N >= k + SIZE) {
		k += SIZE;
		for (i = 0; i < K; i++) tmpp[i] = 0;
		for (i = 0; i < K; i++) {
			for (j = 0; j < K; j++) tmpp[j] += block[i][j] * tmp[i] % Mod;
		}
		for (i = 0; i < K; i++) tmp[i] = tmpp[i] % Mod;
	}
	for (j = 1, k++, sum = tmp[0]; j < K && k < N; j++, k++) {
		tmp[j] += sum;
		if (tmp[j] >= Mod) tmp[j] -= Mod;
		sum += tmp[j];
		if (sum >= Mod) sum -= Mod;
	}
	for (j = 0; k < N; k++) {
		sum -= tmp[j];
		if (sum < 0) sum += Mod;
		tmp[j] += sum;
		if (tmp[j] >= Mod) tmp[j] -= Mod;
		sum += tmp[j++];
		if (sum >= Mod) sum -= Mod;
		if (j == K) j = 0;
	}
	return tmp[(N-1)%K];
}

int main()
{
	int K, N;
	scanf("%d %d", &K, &N);
	if (N > 32000000) printf("%lld\n", solve(K, N));
	else printf("%d\n", naive(K, N));
	fflush(stdout);
	return 0;
}

Submission Info

Submission Time
Task T - フィボナッチ
User ygussany
Language C (GCC 9.2.1)
Score 8
Code Size 2100 Byte
Status AC
Exec Time 446 ms
Memory 9568 KB

Compile Error

./Main.c: In function ‘main’:
./Main.c:86:31: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int’ [-Wformat=]
   86 |  if (N > 32000000) printf("%lld\n", solve(K, N));
      |                            ~~~^     ~~~~~~~~~~~
      |                               |     |
      |                               |     int
      |                               long long int
      |                            %d
./Main.c:85:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
   85 |  scanf("%d %d", &K, &N);
      |  ^~~~~~~~~~~~~~~~~~~~~~

Judge Result

Set Name All
Score / Max Score 8 / 8
Status
AC × 7
Set Name Test Cases
All 00, 01, 02, 03, 04, 90, 91
Case Name Status Exec Time Memory
00 AC 324 ms 9500 KB
01 AC 407 ms 7912 KB
02 AC 446 ms 9568 KB
03 AC 359 ms 4536 KB
04 AC 4 ms 1640 KB
90 AC 1 ms 1680 KB
91 AC 1 ms 1740 KB