QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#50708#4807. Melborp LacissalcalittlestoryTL 1109ms3720kbC++2.9kb2022-09-28 19:26:232022-09-28 19:26:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-28 19:26:23]
  • 评测
  • 测评结果:TL
  • 用时:1109ms
  • 内存:3720kb
  • [2022-09-28 19:26:23]
  • 提交

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;
}

詳細信息

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

output:


result: