QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#36038#2573. Two Permutationsconqueror_of_zky#WA 3ms7696kbC++874b2022-06-23 14:39:332022-06-23 14:39:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-23 14:39:33]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:7696kb
  • [2022-06-23 14:39:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 105, K = 10005, mod = 1e9 + 7;
int n, k, f[N][N][K];
inline int mul(int a, int b) {return 1ll * a * b % mod;}
inline int add(int a, int b) {return (a += b) >= mod ? a - mod : a;}
inline void upd(int &a, int b) {a = add(a, b);}
int main() {
	//freopen("in.txt", "r", stdin);
	cin >> n >> k;
	k -= n * (n + 1) / 2;
	if(k < 0) {
		cout << 0 << '\n';
		return 0;
	}
	f[n][0][0] = 1;
	for(int i = n; i >= 1; i --) {
		for(int j = 0; j <= n - i; j ++) {
			for(int l = 0; l < n * n; l ++) if(f[i][j][l]) {
				upd(f[i - 1][j][l], mul(j + 1, f[i][j][l]));
				upd(f[i - 1][j + 1][l + i], f[i][j][l]);
				if(j && l >= i) upd(f[i - 1][j - 1][l - i], mul(f[i][j][l], j));
			}
		}
	}
	int ans = f[0][0][k];
	for(int i = 1; i <= n; i ++) ans = mul(ans, i);
	cout << ans << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 7532kb

input:

2 4

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 7680kb

input:

3 7

output:

12

result:

ok 1 number(s): "12"

Test #3:

score: 0
Accepted
time: 2ms
memory: 7572kb

input:

4 10

output:

24

result:

ok 1 number(s): "24"

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 7696kb

input:

4 14

output:

48

result:

wrong answer 1st numbers differ - expected: '96', found: '48'