题解：P13196 [GCJ 2016 #1C] Slides!

wsy_I · 2026-04-26 15:03:30 · 题解

建议做本题之前先尝试求解方案数的题目食物链。

话说在校内出题组某位同学想出来了一道差不多的题，还多一个差分，然后那位同学给它评黄了……

题意：构造一个 b 个节点的有向图，使其 1\to b 的路径数为 m。

对于这种构造，注意到可以不限边数，所以说，下面的这种方案得到的路径数肯定是最多的：


为什么呢？再加任意一条边，这个图上就会有环，即 \infin 条可行路径，显然不对。然后假如删掉边的话容易发现只会减少路径数量。

那么容易发现此时 1\to 5 的路径数为 8。容易证明：对于 n 个点，按照以上方法构造的完全图，从 1\to n 的路径数为 2^{n-2}。

于是，得到结论：当 m>2^{b-2} 的时候，一定不存在构造。当 m\leq 2^{b-2} 的时候，我们考虑如何构造。

一个很精妙的观察：在这个图中，包含的子图 \{1, 2, 3, 4\}，\{1, 2, 3\}，\{1, 2\}，\{1\} 都是一个单向完全图。

进一步可以得知：从这个图中，1\to x 的路径数就是 2^{x-2}。于是，就可以开始构造了。

考虑将 m 二进制拆分。对于 m 的第 i 位，假如为 1，则有一条 i+1\to m 的边。这样就可以构造出 m 条路径啦，因为 DAG 上到一个节点的路径数量等于到其前驱数量之和。

当然，假如 m=2^{b-2}，需要特判一下，因为这里不是最后一个点自己向自己连边，而是其余所有点向最后一个点连边。于是可以写出以下代码：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 50 + 5;
int T, m, b, mp[N][N];

signed main() {
  ios :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  cin >> T;
  for(int i = 1; i <= T; i ++ ) {
    cout << "Case #" << i << ": ";
    memset(mp, 0, sizeof mp); 
    cin >> b >> m;
    if(m > (1LL << (b - 2))) cout << "IMPOSSIBLE\n";
    else {
        cout << "POSSIBLE\n";
        for(int i = 1; i < b; i ++ )
            for(int j = i + 1; j < b; j ++ )
                mp[i][j] = 1;
        if(m == (1LL << (b - 2))) {
            for(int i = 1; i < b; i ++ ) mp[i][b] = 1;
            for(int i = 1; i <= b; i ++ ) {
                for(int j = 1; j <= b; j ++ ) cout << mp[i][j];
                cout << endl;
                }
            } else {
                for(int i = 2; m > 0; m >>= 1, i ++ )
                if(m & 1) mp[i][b] = 1;
            for(int i = 1; i <= b; i ++ ) {
                for(int j = 1; j <= b; j ++ ) cout << mp[i][j];
                cout << endl;
                }
            }
        }
    }
  return 0;
}