#1169893 (C++17) No.3585 Make Ends Meet (Easy)

• 問題: No.3585 Make Ends Meet (Easy)
• ユーザー: marc2825
• 提出日時: 2026-07-01 01:29:39
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,432 bytes
• コンパイル時間: 1,594 ms
• コンパイル使用メモリ: 234,232 KB
• 実行使用メモリ: 49,920 KB
• 最終ジャッジ日時: 2026-07-10 21:02:47
• 合計ジャッジ時間: 6,318 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 21 TLE * 1 -- * 26

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static const int MOD = 998244353;
vector<vector<bool>> keep;
int N, M, K;

void print_no() {
    cout << "No\n";
}

void print_yes() {
    cout << "Yes\n";

    for (int u = 1; u <= N; ++u) {
        for (int v = u + 1; v <= N; ++v) {
            if (!keep[u][v]) {
                cout << u << ' ' << v << '\n';
            }
        }
    }
}

ll modpow(ll a, ll e) {
    ll r = 1;
    while (e > 0) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

struct Comb {
    vector<int> fact, ifact;

    void init(int n) {
        fact.assign(n + 1, 1);
        ifact.assign(n + 1, 1);
        for (int i = 1; i <= n; i++) fact[i] = (ll)fact[i - 1] * i % MOD;
        ifact[n] = (int)modpow(fact[n], MOD - 2);
        for (int i = n; i >= 1; i--) ifact[i - 1] = (ll)ifact[i] * i % MOD;
    }

    int C(int n, int r) const {
        if (r < 0 || r > n) return 0;
        return (ll)fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
    }
};

static inline void trim(vector<int> &a) {
    while (!a.empty() && a.back() == 0) a.pop_back();
}

vector<int> mul_qs_minus_1(const vector<int> &p, int s, int E) {
    if (p.empty()) return {};
    int need = min(E + 1, (int)p.size() + s);
    vector<int> res(need, 0);

    // p(q) * q^s
    if (s <= E) {
        int lim = min((int)p.size(), E + 1 - s);
        for (int i = 0; i < lim; i++) res[i + s] = p[i];
    }

    // - p(q)
    int lim = min((int)p.size(), need);
    for (int i = 0; i < lim; i++) {
        res[i] -= p[i];
        if (res[i] < 0) res[i] += MOD;
    }

    trim(res);
    return res;
}

void add_shift_scaled(vector<int> &dst, const vector<int> &src, int shift, int scale, int E) {
    if (src.empty() || scale == 0 || shift > E) return;
    int need = min(E + 1, shift + (int)src.size());
    if ((int)dst.size() < need) dst.resize(need, 0);

    int len = need - shift;
    for (int i = 0; i < len; i++) {
        if (src[i] == 0) continue;
        dst[i + shift] = (dst[i + shift] + (ll)src[i] * scale) % MOD;
    }
}


int main() {

    cin >> N >> M >> K;

    int E = N * (N - 1) / 2;
    int R = E - M;
    int S = N - 2;

    Comb comb;
    comb.init(E);

    // dp[r][s] is a polynomial in q.
    // r: number of ordinary vertices not reached yet
    // s: size of current BFS frontier
    vector<vector<vector<int>>> dp(S + 1, vector<vector<int>>(S + 2));
    dp[S][1] = vector<int>{1};

    // Build layers 1,2,...,K-1 without reaching vertex N.
    for (int step = 0; step < K - 1; step++) {
        vector<vector<vector<int>>> ndp(S + 1, vector<vector<int>>(S + 2));

        for (int r = 0; r <= S; r++) {
            for (int s = 0; s <= S + 1; s++) {
                if (dp[r][s].empty()) continue;

                vector<int> cur = dp[r][s]; // cur * (q^s - 1)^t
                for (int t = 0; t <= r; t++) {
                    int shift = t * (t - 1) / 2; // free edges inside the next frontier
                    int ways = comb.C(r, t);
                    add_shift_scaled(ndp[r - t][t], cur, shift, ways, E);

                    if (t != r) cur = mul_qs_minus_1(cur, s, E);
                }
            }
        }
        dp.swap(ndp);
    }

    // H(q): generating polynomial for dist(1,N)=K in q=1+x.
    vector<int> H(E + 1, 0);

    // N must have at least one edge to the current frontier: (q^s - 1).
    // All edges among the remaining r vertices, between them and N, and between them and the current frontier are free.
    for (int r = 0; r <= S; r++) {
        for (int s = 0; s <= S + 1; s++) {
            const vector<int> &p = dp[r][s];
            if (p.empty()) continue;

            int base = s * r + r + r * (r - 1) / 2;

            for (int i = 0; i < (int)p.size(); i++) {
                int val = p[i];
                if (val == 0) continue;

                if (i + base + s <= E) {
                    H[i + base + s] += val;
                    if (H[i + base + s] >= MOD) H[i + base + s] -= MOD;
                }
                if (i + base <= E) {
                    H[i + base] -= val;
                    if (H[i + base] < 0) H[i + base] += MOD;
                }
            }
        }
    }

    // We need [x^R] H(1+x). If H(q)=sum_c h_c q^c, then
    // [x^R] H(1+x) = sum_c h_c * C(c,R).
    ll ans = 0;
    for (int c = R; c <= E; c++) {
        if (H[c] == 0) continue;
        ans += (ll)H[c] * comb.C(c, R) % MOD;
        ans %= MOD;
    }

	if (ans == 0) print_no();
	else {
		int T = N * (N - 1) / 2;
    	int E = T - M; // number of edges to keep

    	keep.assign(N + 1, vector<bool>(N + 1, false));

    	if (K == 1) {
        // The distance is 1 iff the direct edge (1, N) remains.

        keep[1][N] = true;
        E--;

        for (int u = 1; u <= N && E > 0; ++u) {
            for (int v = u + 1; v <= N && E > 0; ++v) {
                if (u == 1 && v == N) continue;

                keep[u][v] = true;
                E--;
	            }
	        }
	
	        print_yes();
	        return 0;
	    }

	    // K >= 2.
	    // Use the path 1 - 2 - ... - K - N as the mandatory shortest path.
	    int U = N - K - 1; // number of vertices not on the path
	
	    int min_keep = K;
	    int max_keep = K + 3 * U + U * (U - 1) / 2;
	
	    // Keep the mandatory path edges.
	    for (int i = 1; i < K; ++i) {
	        keep[i][i + 1] = true;
	        E--;
	    }
	    keep[K][N] = true;
	    E--;
	
	    vector<pair<int, int>> free_edges;
	
	    // Extra vertices are K+1, K+2, ..., N-1.
	    // Each of them can be connected to three consecutive path vertices.
	    for (int x = K + 1; x <= N - 1; ++x) {
	        free_edges.push_back({1, x});
	        free_edges.push_back({2, x});
	
	        if (K == 2) {
	            // Path vertices are 1, 2, N.
	            free_edges.push_back({x, N});
	        } else {
	            // Path vertices include 1, 2, 3.
	            free_edges.push_back({3, x});
	        }
	    }
	
	    // Extra vertices can be connected freely among themselves.
	    for (int x = K + 1; x <= N - 1; ++x) {
	        for (int y = x + 1; y <= N - 1; ++y) {
	            free_edges.push_back({x, y});
	        }
	    }
	
	    // Add arbitrary free edges until exactly E additional edges are kept.
	    for (auto [u, v] : free_edges) {
	        if (E == 0) break;
	
	        keep[u][v] = true;
	        E--;
	    }
			
			print_yes();
			
	}
}