uoj#279. 【UTR #2】题目交流通道（容斥+数数）

r囧r小猫 2021-12-23 05:34 207阅读 0赞

[传送门][Link 1]

先考虑无解的情况，为以下几种：\\(dis\_\{i,j\}+dis\_\{j,k\}<dis\_\{i,k\}\\)，\\(dis\_\{i,i\}\\neq 0\\)，\\(dis\_\{i,j\}\\neq dis\_\{j,i\}\\)，\\(dis\_\{i,j\}>K\\)。先大力特判掉

然后来考虑没有边权为\\(0\\)的时候，把原图中所有的边分类，对于\\((i,j)\\)，如果存在\\(k\\)使得\\(dis\_\{i,k\}+dis\_\{k,j\}=dis\_\{i,j\}\\)，那么称其为\\(B\\)类边，否则为\\(A\\)类边。显然\\(A\\)类边的权值就是\\(dis\_\{i,j\}\\)，因为从其他地方走权值都大于自己。然后大力猜想一发对于所有\\(B\\)类边，权值可以取\\(\[dis\_\{i,j\},K\]\\)之间的数，接下来证明它

因为存在一条路径从\\(i\\)到\\(j\\)且权值为\\(dis\_\{i,j\}\\)，那么这条路径\\(F\\)上的边数大于等于\\(2\\)，如果其上都是\\(A\\)类边，那么就算所有\\(B\\)取值为\\(K\\)也没关系。那么反证，假设其上有一条边为\\(B\\)类边，那么这条\\(B\\)类边也有对应一条与它权值相等的路径\\(G\\)。\\(G\\)不可能与\\(F\\)有任何一条边重复，否则我们可以在\\(F\\)上不走那条\\(B\\)边而是走\\(G\\)，那么少走了重复的那几条边，路径权值会变小，与\\(F\\)是最短路矛盾

综上，所有\\(A\\)类边取值固定，\\(B\\)类边可以取\\(\[dis\_\{i,j\},K\]\\)之间的边，判断一下边的类型，用乘法原理统计答案就好了

信心满满交上去结果只有\\(30\\)分，发现自己忘记考虑边权为\\(0\\)的情况了

如果有边权为\\(0\\)，那么我们可以把这两个点缩成一个点，而且不难发现最短路为\\(0\\)是具有传递性的，所以我们可以把互相之间最短路为\\(0\\)的点缩到一起，记其中点的个数为\\(size\_i\\)，缩完点之后的图就是没有边权为\\(0\\)的情况了

考虑一个连通块内部，如果把\\(0\\)边当成实边，那么\\(0\\)边需要让所有的点联通，而其它的边的取值无所谓。记\\(f\_i\\)为\\(i\\)个点的连通块中\\(0\\)边使所有点联通的方案数，那么有\\\[f\_i=(K+1)^\{C\_\{i\}^2\}-\\sum\_\{j=1\}^\{i-1\}K^\{(i-j)\\times j\}(K+1)^\{C\_\{i-j\}^2\}C\_\{i-1\}^\{j-1\}f\_j\\\]  
上面的式子的意思就是，总共的方案减去不合法的方案，不合法的方案可以枚举与\\(1\\)同一个联通快的点的大小\\(j\\)，那么内部的方案就是\\(f\_j\\)，然后\\(j\\)和\\(i-j\\)之间的边能为\\(0\\)，\\(i-j\\)内部随便连

上面是连通块的贡献，然后考虑边的贡献，设一条边连接的两个连通块大小分别为\\(i,j\\)，两个连通块之间的最短路长度为\\(d\\)，如果这条边是\\(B\\)类边，那么方案数就是\\((K-d+1)^\{i\\times j\}\\)，如果是\\(A\\)类边，就是\\((K-d+1)^\{i\\times j\}-(K-d)^\{i\\times j\}\\)即合法的减去不合法的

然后就没有然后了

//minamoto
    #include<bits/stdc++.h>
    #define R register
    #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
    #define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
    #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
    using namespace std;
    char buf[1<<21],*p1=buf,*p2=buf;
    inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    int read(){
        R int res,f=1;R char ch;
        while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
        for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
        return res*f;
    }
    const int N=505,P=998244353;
    inline int add(R int x,R int y){return x+y>=P?x=y-P:x+y;}
    inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
    inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
    int ksm(R int x,R int y){
        R int res=1;
        for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);
        return res;
    }
    int a[N][N],vis[N][N],fa[N],f[N],fac[N],inv[N],sz[N];
    int n,K,res=1;
    inline int C(R int n,R int m){if(m>n)return 0;return mul(fac[n],mul(inv[m],inv[n-m]));}
    int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    bool ck(){
        fp(i,1,n)if(a[i][i]!=0)return false;
        fp(i,1,n)fp(j,i+1,n){
            if(a[i][j]!=a[j][i])return false;
            if(a[i][j]>K)return false;
            fp(k,1,n)if(a[i][j]+a[j][k]<a[i][k])return false;
        }return true;
    }
    void init(){
        inv[0]=fac[0]=1;fp(i,1,n)fac[i]=mul(fac[i-1],i);
        inv[n]=ksm(fac[n],P-2);fd(i,n-1,1)inv[i]=mul(inv[i+1],i+1);
        fp(i,1,n)fa[i]=i;
        fp(i,1,n)fp(j,i+1,n)if(a[i][j]==0)fa[find(j)]=find(i);
        fp(i,1,n)++sz[find(i)];
        fp(i,1,n){
            f[i]=ksm(K+1,C(i,2));
            fp(j,1,i-1)f[i]=dec(f[i],1ll*ksm(K,j*(i-j))*ksm(K+1,C(i-j,2))%P*C(i-1,j-1)%P*f[j]%P);
        }
    }
    int main(){
    //  freopen("testdata.in","r",stdin);
        n=read(),K=read();
        fp(i,1,n)fp(j,1,n)a[i][j]=read();
        if(!ck())return puts("0"),0;
        init();
        fp(i,1,n)find(i);
        fp(i,1,n)if(fa[i]==i)
            fp(j,i+1,n)if(fa[j]==j){
                bool flag=0;
                fp(k,1,n)if(fa[k]==k)
                    if(k!=i&&k!=j&&a[i][k]+a[j][k]==a[i][j]){flag=1;break;}
                if(flag)res=mul(res,ksm(K-a[i][j]+1,sz[i]*sz[j]));
                else res=mul(res,dec(ksm(K-a[i][j]+1,sz[i]*sz[j]),ksm(K-a[i][j],sz[i]*sz[j])));
            }
        fp(i,1,n)if(find(i)==i)res=mul(res,f[sz[i]]);
        printf("%d\n",res);
        return 0;
    }

转载于:https://www.cnblogs.com/bztMinamoto/p/10246448.html

[Link 1]: http://uoj.ac/problem/279