Submission #15299098


Source Code Expand

Copy
#include<iostream>
using namespace std;
long long int mod = 924844033;
long long int dp[4003][2002][2];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int num, kai;
	cin >> num >> kai;
	dp[0][0][0] = 1;
	int pt = 0;
	for (int i = 0; i < kai * 2; i++){
		int t = 0;
		int nx, ny;
		if (i < kai)nx = i, ny = i + kai;
		else nx = i, ny = i - kai;
		while(true){
			if (nx >= num || ny >= num){
				break;
			}
			t++;
			if (nx < ny){
				nx += kai * 2;
			}else{
				ny += kai * 2;
			}
		}
		for (int j = 0; j < t; j++){
			for (int k = 0; k <= num; k++){
				dp[pt + 1][k][0] += dp[pt][k][0] + dp[pt][k][1];
				dp[pt + 1][k + 1][1] += dp[pt][k][0];
				dp[pt + 1][k][0] %= mod;
				dp[pt + 1][k + 1][1] %= mod;
			}
			pt++;
		}
		for (int k = 0; k <= num; k++){
			dp[pt][k][0] += dp[pt][k][1];
			dp[pt][k][0] %= mod;
			dp[pt][k][1] = 0;
		}
	}
	long long int ans = 0;
	long long int now = 1;
	for (int i = num; i >= 0; i--){
		if (i % 2 == 0){
			ans += dp[pt][i][0] * now;
		}else{
			ans += mod - dp[pt][i][0] * now % mod;
		}
		ans %= mod;
		now *= (num - i + 1);
		now %= mod;
	}
	cout << ans;
}

Submission Info

Submission Time
Task D - ~K Perm Counting
User INvisIbl3
Language C++ (GCC 9.2.1)
Score 900
Code Size 1196 Byte
Status AC
Exec Time 229 ms
Memory 128580 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 5
AC × 28
Set Name Test Cases
Sample example0, example1, example2, example3, example4
All example0, example1, example2, example3, example4, handmade0, handmade1, handmade2, handmade3, handmade4, handmade5, handmade6, maxrand0, maxrand1, maxrand2, maxrand3, maxrand4, rand0, rand1, rand2, rand3, rand4, small0, small1, small2, supersmall0, supersmall1, supersmall2
Case Name Status Exec Time Memory
example0 AC 8 ms 3544 KB
example1 AC 3 ms 3624 KB
example2 AC 4 ms 3608 KB
example3 AC 2 ms 3524 KB
example4 AC 23 ms 11576 KB
handmade0 AC 4 ms 3656 KB
handmade1 AC 225 ms 128580 KB
handmade2 AC 76 ms 3716 KB
handmade3 AC 211 ms 121220 KB
handmade4 AC 69 ms 3532 KB
handmade5 AC 229 ms 125516 KB
handmade6 AC 224 ms 125608 KB
maxrand0 AC 100 ms 28004 KB
maxrand1 AC 155 ms 71124 KB
maxrand2 AC 166 ms 76788 KB
maxrand3 AC 214 ms 121312 KB
maxrand4 AC 74 ms 7260 KB
rand0 AC 192 ms 97608 KB
rand1 AC 26 ms 10588 KB
rand2 AC 16 ms 4660 KB
rand3 AC 3 ms 3948 KB
rand4 AC 87 ms 27424 KB
small0 AC 12 ms 6976 KB
small1 AC 6 ms 4960 KB
small2 AC 8 ms 4212 KB
supersmall0 AC 2 ms 3608 KB
supersmall1 AC 2 ms 3536 KB
supersmall2 AC 2 ms 3620 KB