yukicoder #690 : E869120 and Constructing Array 4

N=32とする。1<=v<w<=31としてを満たすすべての辺(v, w)の辺を貼ると1から2<=x<=31までの経路の和は2^x-2通りである。これは経路数をf(x)と表すと f(x) = f(1) + f(2) +...+ f(x-2) + f(x-1) = (f(1)+f(2)+...+f(x-2)) + f(x-1) = f(x-1) + f(x-1) = 2f(x-1)であるため。よってKを2進数として各桁をみてk(>=0)ビット目が立っていたら頂点k+2から頂点Nに辺を張ればよい。

int K, N = 32;
cin >> K;
vector<pii> E;
for (int w = 2; w <= N - 1; w++)
    for (int v = 1; v < w; ++v)
        E.emplace_back(v, w);
rep(a, 30)if (K >> a & 1)E.emplace_back(a + 2, N);
cout << N << ' ' << sz(E) << endl;
each(e, E)cout << e.first << ' ' << e.second << endl;