UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#159231#239. countbitsstdcheee3059ms1276kbC++685b2022-09-28 14:52:382022-09-28 14:52:40

answer

#include <iostream>

using namespace std;

int n, m, k;
const int mod = 998244353; 
int f[20][2020];
int dfs(int dep, int le) {
    if (f[dep][le]) return f[dep][le];
    // cout << dep << " " << le << endl;
    if (le < 0) return 0;
    if (dep == k + 1) {
        if (le != 0) return 0;
        return 1;
    }
    if (le == 0) return 0;
    int res = 0;
    for (int i = 1; i <= le; i++) {
        if (i % m == 0) continue;
        res += dfs(dep + 1, le - i);
        res %= mod;
    }
    return f[dep][le] = res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    cout << dfs(1, n) << endl;
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 9ms
memory: 1276kb

input:

1000 1000 3


output:

498501

result:

ok single line: '498501'

Test #2:

score: 10
Accepted
time: 11ms
memory: 1268kb

input:

2000 2000 2


output:

1999

result:

ok single line: '1999'

Test #3:

score: 10
Accepted
time: 39ms
memory: 1276kb

input:

1999 1005 3


output:

1992024

result:

ok single line: '1992024'

Test #4:

score: 0
Runtime Error

input:

523098578902387543 1990 3


output:


result:


Test #5:

score: 0
Runtime Error

input:

985435493875384653 1987 3

output:


result:


Test #6:

score: 0
Runtime Error

input:

854378965978354365 4898 20


output:


result:


Test #7:

score: 0
Runtime Error

input:

869347685748976465 5000 20


output:


result:


Test #8:

score: 0
Runtime Error

input:

985493567483653416 4999 2000


output:


result:


Test #9:

score: 0
Runtime Error

input:

1000000000000000000 4987 1992


output:


result:


Test #10:

score: 0
Runtime Error

input:

666666666623333333 4998 1999


output:


result: