Submission #1863398


Source Code Expand

#include <cstdio>

#define iter(i, n) forw(i, 1, n)
#define forw(i, a, b) for (int i = a; i <= b; ++i)
#define down(i, a, b) for (int i = b; i >= a; --i)

const int mod = 1e9 + 7;

const int NR = 2010;

int pr(int a, int z) {
	int s = 1;
	while (z > 0) {
		if (z % 2 == 1) s = 1ll * s * a % mod;
		a = 1ll * a * a % mod;
		z /= 2;
	}
	return s;
}

int n, K, f[NR][NR], sum[NR][NR], fac[NR], inv[NR];

int binom(int n, int k) {
	return n < k ? 0 : 1ll * fac[n] * inv[k] % mod * inv[n - k] % mod;
}

int main() {
	scanf("%d%d", &n, &K);
	if (n == 1) {
		puts("1");
		return 0;
	}

	fac[0] = inv[0] = 1;
	iter(i, n) {
		fac[i] = 1ll * fac[i - 1] * i % mod;
		inv[i] = pr(fac[i], mod - 2);
	}

	int ans = binom(n - 2, K - 1);

	f[n + 1][0] = 1;
	forw(i, 0, K) sum[n + 1][i] = 1;
	down(i, n - K + 2, n) {
		forw(j, 0, K) {
			/*
				choice:
					-1
					+X
			*/

			f[i][j] = (f[i + 1][j + 1] + sum[i + 1][j]) % mod;
			sum[i][j] = f[i][j];
			if (j) sum[i][j] = (sum[i][j] + sum[i][j - 1]) % mod;

			if (!j) {
				if (i - 3 >= 0 && K - (n - i + 1) - 1 - j >= 0) {
				
					ans = (ans + 1ll * binom(i - 3, K - (n - i + 1) - 1) * f[i][j]) % mod;
			//		printf("0!%d %d => %lld\n", i, j, 1ll * binom(i - 3, K - (n - i + 1) - 1) * f[i][j]);
				}
			} else {

				if (i - 3 >= 0 && K - (n - i + 1) - 1 - j >= 0) {
				
					ans = (ans + 1ll * binom(i - 3, K - (n - i + 1) - 1) * f[i][j]) % mod;
		//			printf("0!%d %d => %lld\n", i, j, 1ll * binom(i - 3, K - (n - i + 1) - 1) * f[i][j]);
				}                                                
			}
		
//			printf("f[%d][%d]=%d\n", i, j, f[i][j]);
		}

	}
	
	if (n == K) printf("%d\n", f[2][0]); 
	else {
		//printf("ans=%d\n", ans);

		iter(i, n - K - 1) ans = ans * 2 % mod;
		printf("%d\n", ans);
	}
	return 0;
}

Submission Info

Submission Time
Task F - Solitaire
User Ketsui
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 1841 Byte
Status AC
Exec Time 36 ms
Memory 31616 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:28:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &K);
                       ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 3
AC × 26
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 1 ms 2176 KB
00_example_02.txt AC 1 ms 2176 KB
00_example_03.txt AC 14 ms 19456 KB
01.txt AC 1 ms 2176 KB
02.txt AC 10 ms 16896 KB
03.txt AC 1 ms 2304 KB
04.txt AC 2 ms 4736 KB
05.txt AC 0 ms 128 KB
06.txt AC 1 ms 2176 KB
07.txt AC 1 ms 2304 KB
08.txt AC 1 ms 2304 KB
09.txt AC 32 ms 29056 KB
10.txt AC 1 ms 2176 KB
11.txt AC 1 ms 2304 KB
12.txt AC 36 ms 30208 KB
13.txt AC 1 ms 2432 KB
14.txt AC 7 ms 13056 KB
15.txt AC 5 ms 11648 KB
16.txt AC 7 ms 13184 KB
17.txt AC 5 ms 11008 KB
18.txt AC 19 ms 23552 KB
19.txt AC 15 ms 19456 KB
20.txt AC 5 ms 11008 KB
21.txt AC 0 ms 128 KB
22.txt AC 31 ms 31616 KB
23.txt AC 1 ms 2176 KB