QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#766470 | #4794. Salaj | 5toubun_no_hanayome | WA | 61ms | 4036kb | C++14 | 2.4kb | 2024-11-20 17:26:20 | 2024-11-20 17:26:21 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a);i <= (b);++i)
#define per(i, a, b) for(int i = (a);i >= (b);--i)
#define lc (k << 1)
#define rc (k << 1 | 1)
#define lowbit(x) ((x) & -(x))
#define odd(x) ((x) & 1)
#define even(x) (!odd(x))
#define fir first
#define sec second
#define pb push_back
#define il inline
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define i128 __int128
#define f128 __float128
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << (x) << "\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T> using vc = vector<T>;
template<class Tx, class Ty>
il void chkmx(Tx& x, const Ty y) {x = max<common_type_t<Tx, Ty>>(x, y);}
template<class Tx, class Ty>
il void chkmn(Tx& x, const Ty y) {x = min<common_type_t<Tx, Ty>>(x, y);}
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3fll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
bool ms;
const int N = 55;
int f[N * 2][N], pre[N * 2][N];
void solve() {
int n, m, p;
cin >> n >> m >> p;
auto toadd = [&](int& x, int y) -> void {
(x += y) >= p && (x -= p);
};
memset(f, 0, sizeof(f));
f[0][n] = 1;
rep(i, 0, m - 1) {
rep(j, 0, min(i, (n - 1) * 2)) {
memcpy(pre[j + 2], f[j] + 1, sizeof(f[j][0]) * n);
per(k, n, 1) {
if(i + 1 <= (n - k + 1) * (n - k) + (k - 1) * (k - 2) / 2 + (k - 1) * (n - k + 1))
break;
f[j][k] = 0;
}
}
int ans = 0;
rep(j, 0, min(i + 1, (n - 1) * 2)) {
rep(k, 1, n) {
if(j <= i + 1) {
if(__builtin_expect(j > 0, 1))
toadd(pre[j][k], pre[j - 1][k + 1]);
toadd(f[j][k], pre[j][k]);
}
toadd(ans, f[j][k]);
}
}
cout << ans << " \n"[i == m - 1];
}
}
bool mt;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cerr << fabs(&ms - &mt) / 1024 / 1024 << "\n";
int t;
cin >> t;
while(t--)
solve();
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3984kb
input:
2 5 10 666013 6 9 10
output:
1 2 4 9 21 50 110 209 351 546 1 2 4 9 1 1 6 0 7
result:
ok 19 numbers
Test #2:
score: -100
Wrong Answer
time: 61ms
memory: 4036kb
input:
10 31 248 8654701 13 11 331266209 33 517 52876477 26 580 675225807 48 2029 311070528 26 31 327981899 39 25 644128037 29 776 464963196 43 799 451592950 25 184 564388620
output:
1 2 4 9 21 51 127 323 835 2188 5798 15511 41835 113634 310572 853467 2356779 6536382 889882 7578514 4072343 2646977 4649285 7797829 7894657 8630011 5369867 7539674 4332126 8201689 8589675 2709364 4018535 3531401 5490003 4890382 334630 1280966 7295275 4971992 1680824 7744560 2450701 2716471 1097918 5...
result:
wrong answer 784th numbers differ - expected: '323', found: '325'