QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#50708 | #4807. Melborp Lacissalc | alittlestory | TL | 1109ms | 3720kb | C++ | 2.9kb | 2022-09-28 19:26:23 | 2022-09-28 19:26:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long long ll;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a, ll b, ll mod) {ll res=1;a%=mod;
assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;
a=a*a%mod;};return res;}
ll gcd(ll a, ll b) {return b?gcd(b, a%b):a;}
template<class T>
void chkmin(T&x,T y){x=min(x,y);}
template<class T>
void chkmax(T&x,T y){x=max(x,y);}
template<class T>
void add(T&x,T y){x+=y;if(x>=mod)x-=mod;}
template<class T>
void sub(T&x,T y){x-=y;if(x<0)x+=mod;}
// head
const int N = 110;
int n, k, t, cnt;
int a[N];
ll f[N], ans, invf[N];
ll c(int n, int m) {
//cout << n << ' ' << m << '\n';
if (n < m) return 0;
return f[n] * invf[m] % mod * invf[n - m] % mod;
}
void dfs(int x, int cur, int last, int res) {
//cout << cur << '\n';
if ((x - cur) * last < res) return;
if (cur == x) {
int tot = cnt * (cnt + 1) / 2;
for (int i = 0; i < x; i++)
tot += a[i] * (a[i] - 1) / 2;
if (tot == t) {
/*cout << cnt << ' ';
for (int i = 0; i < x; i++) cout << a[i] << ' ';
cout << '\n';*/
ll p = f[x];
VI b;
if (cnt) b.pb(cnt);
for (int i = 0; i < x; i++)
if (a[i]) b.pb(a[i]);
for (int i = 0, j; i < x; i = j + 1) {
j = i;
while (j + 1 < x && a[j + 1] == a[j]) ++j;
p = p * powmod(f[j - i + 1], mod - 2, mod) % mod;
}
//cout << p << '\n';
int r = n;
for (int i : b) {
p = c(r, i) * p % mod;
r -= i;
}
//cout << p << '\n';
add(ans, p);
}
return ;
}
for (int i = min(res, last); i >= 0; i--) {
a[cur] = i;
dfs(x, cur + 1, i, res - i);
}
}
void solve() {
// to solve a single test case
f[0] = 1;
cin >> n >> k >> t;
for (int i = 1; i <= 64; i++) {
f[i] = f[i - 1] * i % mod;
invf[i] = powmod(f[i], mod - 2, mod);
}
invf[0] = 1;
for (cnt = 0; cnt <= n; cnt++) {
if (cnt * (cnt + 1) / 2 > t) break;
//cout << cnt << '\n';
dfs(k - 1, 0, k - 1, n - cnt);
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tt;
//cin >> tt;
tt = 1;
while (tt--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3512kb
input:
2 5 1
output:
12
result:
ok 1 number(s): "12"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
7 10 15
output:
2016
result:
ok 1 number(s): "2016"
Test #3:
score: 0
Accepted
time: 307ms
memory: 3692kb
input:
46 50 171
output:
645560469
result:
ok 1 number(s): "645560469"
Test #4:
score: 0
Accepted
time: 1109ms
memory: 3568kb
input:
64 64 0
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: -100
Time Limit Exceeded
input:
64 64 1