Codeforcesで似たようなの見たからなぁ…。
https://code.google.com/codejam/contest/4314486/dashboard#s=p1&a=0
問題
1~BのB個の頂点からなる有向グラフを考える。
1からBに至る経路が計M通りになるものを構築せよ。
ただし同じ2頂点間に複数の辺を張ってはならない。
解法
1≦i≦j≦B-1となる頂点対(i,j)の間にi→jという辺を張ろう。
すると頂点1から頂点iに至る経路は2^(i-2)通りできる。(i=1の時は1通り)
あとは各頂点からBに辺を張り、計M個の経路ができるようにしたい。
貪欲に頂点iを(B-1)から順に走査し、2^(i-2)≦Mならi→Bに辺を張りM -= 2^(i-2)で更新すればよい。
Mが大きすぎる場合、全頂点からBに辺を張っても計M通りに満たないので、その場合IMPOSSIBLEとなる。
int B; ll M; int mat[60][60]; void solve(int _loop) { int f,i,j,k,l,x,y; cin>>B>>M; ZERO(mat); for(x=0;x<B-1;x++) for(y=x+1;y<B-1;y++) mat[x][y]=1; for(y=B-2;y>=0;y--) { ll v=(y==0)?1:(1LL<<y-1); if(M>=v) mat[y][B-1]=1, M-=v; } if(M==0) { _P("Case #%d: POSSIBLE\n",_loop); FOR(y,B) { FOR(x,B) _P("%d",mat[y][x]); _P("\n"); } } else { _P("Case #%d: IMPOSSIBLE\n",_loop); } }
まとめ
これは既出っぽいな…。