日志 - zhouyuyang的博客

uoj544 的Hack数据是怎么造的

2020-06-24 23:43:44 By zhouyuyang

这题的正确做法要求若干个二阶余子式的值。

但是，在基尔霍夫矩阵的秩恰好为n-2时，可能会出现生成树方案数模$998244353$为$0$，但是每条边出现次数不为$0$的情况。

这个问题在智商锁中也没有得到特别好的解决，特来讲述一下构造方法。

设$f(x)$表示图$x$的生成树个数，$g(x)$表示强制合并$1,2$号点的生成树个数。

此时我们考虑合并两张图$x,y$，并且连接$x$中的1号节点和$y$中的$1$号节点。同时连接并且连接$x$中的$2$号节点和$y$中的$2$号节点。

手动枚举一下新加的两条边，不难发现方案数=$f(x)g(y)+g(x)f(y)+2f(x)f(y)$。

因此，我们可以随机$100000$个$15$个节点的随机连通图后meet in middle合并即可。

平均$5 \sim 6s$就可以跑出来一个Hack点。

如果采用map存储$\frac{g(x)}{f(x)}$的值，在meet in middle时只需要在map上查询比值即可。这样子可以对更大的质数进行构造。

#include<bits/stdc++.h>
#define mo 998244353
using namespace std;
const int N=100005;
int e1[20][20],e2[20][20],n=15,ee[100005];
int c[20][20],vf[100005],vg[100005];
bool G[100005][20][20];
int Det(int e[20][20],int n){
    memset(c,0,sizeof(c));
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++){
            c[i][j]-=e[i][j];
            c[j][i]-=e[i][j];
            c[i][i]+=e[i][j];
            c[j][j]+=e[i][j];
        }
    for (int i=1;i<=n;i++)    
        for (int j=1;j<=n;j++)
            c[i][j]=(c[i][j]+mo)%mo;
    int ans=1;
    for (int i=1;i<n;i++){
        for (int j=i+1;j<n;j++)
            for (;c[j][i];){
                ans=mo-ans;
                int tmp=c[i][i]/c[j][i];
                for (int k=i;k<n;k++) c[i][k]=(c[i][k]+mo-1ll*tmp*c[j][k]%mo)%mo;
                for (int k=i;k<n;k++) swap(c[i][k],c[j][k]);
            }
        ans=1ll*ans*c[i][i]%mo;
    }
    return ans;
}
void GEN(int id){
    memset(e1,0,sizeof(e1));
    memset(e2,0,sizeof(e2));
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            if (rand()&1){
                e1[i][j]++;
                e2[i][min(j,n-1)]++;
                G[id][i][j]=1; 
                ++ee[id];
            }
    vf[id]=Det(e1,n);
    vg[id]=Det(e2,n-1);
    if (id%1000==0) cerr<<id<<' '<<vf[id]<<' '<<vg[id]<<endl;
}
int main(){
    srand(time(NULL));
    freopen("ex_count5.in","w",stdout);
    for (int i=1;i<=100000;i++) for (;!vf[i];) GEN(i);
    for (int i=1;i<=100000;i++)
        for (int j=i;j<=100000;j++){
            long long fuck=1ll*vf[i]*vg[j]+1ll*vg[i]*vf[j]+2ll*vf[i]*vf[j];
            if (fuck%mo==0){
                cout<<30<<' '<<ee[i]+ee[j]+2<<endl;
                for (int p1=1;p1<=15;p1++)
                    for (int p2=p1+1;p2<=15;p2++)
                        if (G[i][p1][p2]) cout<<p1<<' '<<p2<<' '<<250*(rand()%233+1)<<endl;
                for (int p1=1;p1<=15;p1++)
                    for (int p2=p1+1;p2<=15;p2++)
                        if (G[j][p1][p2]) cout<<p1+15<<' '<<p2+15<<' '<<250*(rand()%233+1)<<endl;
                cout<<14<<' '<<29<<' '<<250*(rand()%233+1)<<endl;
                cout<<15<<' '<<30<<' '<<250*(rand()%233+1)<<endl;
                exit(0);
            }//cerr<<i<<' '<<j<<' '<<fuck<<' '<<vf[i]<<' '<<vg[j]<<' '<<vg[i]<<' '<<vf[j]<<endl;
        }
}