ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#204082 | #170. 数数 | snow_trace | 100 | 31ms | 10036kb | C++11 | 1.5kb | 2024-04-09 11:28:28 | 2024-04-09 11:28:30 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int dp[55][55][2505];int n,m;
signed main(){
cin >> n >> m;
dp[0][0][0] = 1;
for(int i = 1;i<=n;i++){
for(int j = 0;j<i;j++){
for(int k =0;k<=2500;k++){
if(dp[i-1][j][k]){
//i 的位置 正好放进去 i
dp[i][j+1][k+i] =(dp[i][j+1][k+i]+dp[i-1][j][k])%mod;
//i 的位置里面放的比 i 大,而且 i 放在了前面
dp[i][j+1][k+i] = (dp[i][j+1][k+i]+dp[i-1][j][k]*(i-1-j))%mod;
//i 的位置里面放的比 i 小,而且 i 放在了前面
dp[i][j+2][k+2*i] =(dp[i][j+2][k+2*i]+dp[i-1][j][k]*(i-1-j)*(i-1-j))%mod;
//i 的位置里面放的比 i 大,而且 i 放在后面
dp[i][j][k] = (dp[i][j][k]+dp[i-1][j][k])%mod;
//i 的位置里面放的比 i 小,而且 i 放在后面
dp[i][j+1][k+i] = (dp[i][j+1][k+i]+dp[i-1][j][k]*(i-1-j))%mod;
}
}
}
}int ans = 0;for(int i = m;i<=2500;i++)ans = (ans+dp[n][n][i])%mod;
for(int i = 1;i<=n;i++)ans = ans*i%mod;cout << ans << endl;
return 0;
}/*
很牛的一个题。
首先我们可以发现相对顺序没有关系
令 bi = i 然后答案要乘上 n!
dp_i_j_k 表示前 i 个数在前 i 个位置里有 j 个,最大值 <=i 的最大值的和是 k
思考
为什么这么设?
我们需要从 i 的大小关系推到 i+1 的大小关系,同时又会影响到 i+1 的位置
所以我们必须让前面不影响后面,出现了这样一个神秘的状态。
orzozrrozrzozorzro
3 8
*/
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1328kb
input:
6 25
output:
468000
result:
ok single line: '468000'
Test #2:
score: 10
Accepted
time: 0ms
memory: 1448kb
input:
9 55
output:
94864779
result:
ok single line: '94864779'
Test #3:
score: 10
Accepted
time: 0ms
memory: 1500kb
input:
10 70
output:
451961658
result:
ok single line: '451961658'
Test #4:
score: 10
Accepted
time: 0ms
memory: 2164kb
input:
19 188
output:
199080822
result:
ok single line: '199080822'
Test #5:
score: 10
Accepted
time: 0ms
memory: 2268kb
input:
20 233
output:
354115829
result:
ok single line: '354115829'
Test #6:
score: 10
Accepted
time: 0ms
memory: 2072kb
input:
18 200
output:
360483048
result:
ok single line: '360483048'
Test #7:
score: 10
Accepted
time: 8ms
memory: 8260kb
input:
46 1200
output:
744054009
result:
ok single line: '744054009'
Test #8:
score: 10
Accepted
time: 5ms
memory: 9124kb
input:
48 1333
output:
506724228
result:
ok single line: '506724228'
Test #9:
score: 10
Accepted
time: 8ms
memory: 10032kb
input:
50 1275
output:
263941435
result:
ok single line: '263941435'
Test #10:
score: 10
Accepted
time: 10ms
memory: 10036kb
input:
50 1800
output:
763816424
result:
ok single line: '763816424'