QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#751475#9740. Aho-Corasick 自动机lonelywolf#WA 0ms3556kbC++201.3kb2024-11-15 18:56:192024-11-15 18:56:19

Judging History

你现在查看的是最新测评结果

  • [2024-11-15 18:56:19]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3556kb
  • [2024-11-15 18:56:19]
  • 提交

answer

#include <bits/stdc++.h>  
using namespace std;  

#define int long long  

const int mod = 998244353;
void add(int &a, int b) {
	a += b;
	if (a >= mod) {
		a -= mod;
	}
}

signed main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  

	int n, m, d;
	cin >> n >> m >> d;

	vector C(n * m + 1, vector<int>(n + 1));
	for (int i = 0; i <= n * m; i++) {
		C[i][0] = 1;
	}
	for (int i = 1; i <= n * m; i++) {
		for (int j = 1; j <= min(i, n); j++) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
		}
	}

	vector<int> cnt(d + 1);
	cnt[0] = 1;
	for (int i = 1; i <= d; i++) {
		if (cnt[i - 1] > n) {
			cnt[i] = 1e18;
		} else {
			cnt[i] = cnt[i - 1] * m;
		}
	}

	if (n == 1) {
		cout << 1 << "\n";
		return 0;
	}

	int ans = 0;
	vector dp(n + 1, vector<int>(n + 1));
	dp[1][1] = 1;
	for (int l = 1; l <= d; l++) {
		vector ndp(n + 1, vector<int>(n + 1));
		for (int i = l + 1; i <= n; i++) {
			for (int j = 1; j <= min(i, cnt[l]); j++) {
				for (int k = 1; k <= min({i - j, cnt[l - 1], (j + m - 1) / m}); k++) {
					add(ndp[i][j], dp[i - j][k] * C[k * m][j] % mod);
				}
			}
		}
		dp = ndp;
		for (int i = 1; i <= n; i++) {
			add(ans, dp[n][i]);
		}
		cout << "\n";
	}
	cout << ans << "\n";

    return 0;
}  
  

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3556kb

input:

3 2 2

output:



5

result:

ok answer is '5'

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3500kb

input:

4 2 2

output:



2

result:

wrong answer expected '6', found '2'