UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#204082#170. 数数snow_trace10031ms10036kbC++111.5kb2024-04-09 11:28:282024-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'