UOJ Logo 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;
        }
}

#500 题解

2020-01-23 18:33:46 By zhouyuyang

算法1

我会暴力!

直接写了一个$O(nq)$的暴力。

期望得分5分。

算法2

我会拉板子!

直接拉了一个$O(Q \log^2 n)$的多点求值。

期望得分20分。

算法3

我会拉很牛逼的板子!

期望得分35分。

算法4

我会看性质!

不难发现求的是$q_0*qx^k$的点值。

不难构造函数$g(x)$满足$f(x)=g(x/q_0)$

问题转化为求$V(j)=\sum a_i qx^{ij}$

根据$\binom{i+j}{2}=\binom{i}{2}+\binom{j}{2}+ij$,转写上面的式子。

$V(j) qx^{\binom{j}{2}}=\sum a_i qx^{-\binom{i}{2}} qx^{\binom{i+j}{2}}$

不难发现本质是两个序列做的一次减法卷积。

时间复杂度$O(Q \log Q)$

结合算法3期望得分60分。

算法5

我会推性质!

根据已知条件多点求值暂时没有$O(n\log^2 n)$的算法。

因此随机性质一定有用!。

假设我们已知$n$次多项式$f(x)$,则我们可以:

在$O(n)$的时间复杂度内找到一个$n$次多项式$g(x)$满足$g(x)=f(x*k)$。

在$O(n \log n)$的时间复杂度内找到一个$n$次多项式$h(x)$满足$h(x)=h(x+k)$。

再看看询问的东西,不难发现第i次询问的是$q_0 qx^i+\sum \limits_{j=0}^{j \le i-1} qy qx^j$

乘上$qx-1$得到$q_0 qx^i(qx-1)+qy qx^i-qy$

加上$qy$得到$(q_0(qx-1)+qy)qx^i$

欸变成算法4了!

$q_0(qx-1)+qy$为0时询问值总为0不会产生影响。

同时输入范围保证$qx \geq 2$所以上文所有变换均合法。

由于每一次变换复杂度均为$O(n \log n)$

时间复杂度$O(Q \log Q+n \log n)$

期望得分100分。

#395. 【NOI2018】你的名字 val挂了

2019-10-01 19:01:50 By zhouyuyang

Hack #8475的串T长度似乎为1000000...

挂掉的提交链接

如果有管理员看到了这个博客麻烦修一下val加上$|T| \leq 500000$。

谢谢。

关于Goodbye wuxu C的一些假算法的探讨

2019-02-09 08:36:29 By zhouyuyang

这题标算大概是数据结构优化DP之类的东西。

但是出题人想到了这题会有很多乱搞做法,现在将已知的一一说明。

1.直接暴力树剖一定最优,或者最大的子树大小>=剩下子树大小的若干倍时直接走重儿子。

考虑一颗树,1号节点有两个儿子,一个儿子上面是一个很大的菊花,另外一个儿子上面连着一条链。

此时我们发现走链更优,但是这个算法会走菊花。

如果你特判的深度差<=2的节点,可以把菊花的每个叶子转换成长度较小(<=5)的链也可以叉掉。

如果有其他乱搞,可以私信出题人。

UOJ的bug?

2019-02-01 21:14:09 By zhouyuyang
zhouyuyang Avatar