P11436 题解

· · 题解

神秘 adhoc。

首先你考虑一下最大多少，然后你会发现每个非 1 点至少选择一条入边，那么最大值就是 3^{32}\times 4，刚好略大于 k 的那个限制。由此猜测，不会有 -1，他就是让我们构造的。

然后你会发现你搓个 DAG 答案必然是每个点入边数量之积，所以你不能搓 DAG。

这引导我们去搓一个环。对于一个单独的环（2\sim n 组成的环），外向生成树数量是每个点入边之积减去环上两两之间边的积。

但是这样还是不够，我们只能弄出 3^{32}\times 4-\prod x_i，其中 x_1,x_2,\dots,x_{32}\leq 3，x_{33}\leq 4。

考虑搓一个环，然后加一条 2\to 4 的边的后果。此时方案数是总数减去出现 2,3,4,\dots,n 这个环的方案数再减去 2,4,5,\dots,n 这个环的方案数。也就是，减去 \prod x_i+3\prod_{i\neq 3}x_i。

我们钦定 x_i=1，即可得到 1+3。

然后再加上 2\to 5 的边，以及加两条 2\to 4 的边，通过一定计算会发现可以得到 1+3^2 和 1+3\times 2。

这启发我们求出要减去的部分，然后对减去的部分三进制分解，依次加入边。也就是，对于第 i 位，2\to i+2 的边数为减去部分第 i 位的值。

构造会有一些 corner case，所以可以找到比 n 大的第一个 3^x 或 3^x\times 2 或 3^x\times 4 然后去构造。具体细节可以看代码。

#include <bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
#define lowbit(i) (i&(-i))
using namespace std;
int a[40],b[40],c[40],cnt;
void solve(){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    int n; cin>>n;
    if(n==1){
        cout<<1<<" "<<0<<"\n";
        return ;
    }
    int now=1,cnted=0;
    cnt=0;
    while(now<n){
        if(now*2>=n){
            now*=2;
            a[++cnt]=3;
            a[1]=2;
            cnted+=2;
        }
        else{
            now*=3;
            a[++cnt]=3;
            cnted+=3;
        }
    }
    if(now==n){
        cout<<cnt+1<<" "<<cnted<<"\n";
        for(int i=1;i<=cnt;i++){
            for(int j=1;j<=a[i];j++) cout<<1<<" "<<i+1<<"\n";
        }
        return ;
    }
    if(cnted==101){
        cnt--;
        a[1]=3;
        a[cnt]=4;
        cnted=100;
    }
    for(int i=1;i<=cnt;i++) c[i]=1;
    c[2]=0;
    int ex=now-n,it=2;
    while(ex){
        int md=ex%3; ex/=3;
        b[it]=md;
        it++;
    }
    cout<<cnt+1<<" "<<cnted<<"\n";
    for(int i=1;i<=cnt;i++){
        if(i==1){
            if(a[1]==3) cout<<1<<" "<<2<<"\n";
            cout<<1<<" "<<2<<"\n";
            cout<<cnt+1<<" "<<2<<"\n";
            continue;
        }
        for(int j=1;j<=c[i];j++) cout<<i<<" "<<i+1<<"\n";
        for(int j=1;j<=b[i];j++) cout<<2<<" "<<i+1<<"\n";
        for(int j=1;j<=a[i]-c[i]-b[i];j++) cout<<1<<" "<<i+1<<"\n";
    }
}
signed main(){
    int t; cin>>t;
    while(t--) solve();
    return 0;
}