結果

問題 No.3030 Kruskal-Katona
コンテスト
ユーザー Zhiyuan Chen
提出日時 2025-02-21 22:43:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,419 bytes
コンパイル時間 879 ms
コンパイル使用メモリ 69,860 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-02-21 22:43:51
合計ジャッジ時間 2,194 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 4 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

// 计算组合数 C(n, k) 的迭代版本（避免溢出）
ll comb(ll n, int k) {
    if (k > n) return 0;
    if (k == 0 || k == n) return 1;
    k = min(k, (int)(n - k));
    ll res = 1;
    for (int i = 1; i <= k; ++i) {
        res = res * (n - k + i) / i;
    }
    return res;
}

vector<ll> solve(ll N, int i) {
    vector<ll> res;
    ll remaining = N;
    int current_k = i;
    
    while (remaining > 0 && current_k >= 1) {
        // 二分查找最大的n使得C(n, current_k) <= remaining
        ll left = current_k;
        ll right = 2e9; // 上界足够大
        ll best_n = current_k;
        
        while (left <= right) {
            ll mid = (left + right) / 2;
            ll c = comb(mid, current_k);
            
            if (c <= remaining) {
                best_n = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        res.push_back(best_n);
        remaining -= comb(best_n, current_k);
        current_k--;
    }
    
    return res;
}

int main() {
    ll N;
    int i;
    cin >> N >> i;
    
    auto ans = solve(N, i);
    
    for (size_t idx = 0; idx < ans.size(); ++idx) {
        cout << ans[idx];
        if (idx != ans.size() - 1) cout << " ";
    }
    cout << endl;
    
    return 0;
}
0