牛客挑战赛48 D-牛奶 题解

大家应该普遍用的是州区划分那题的做法，毕竟这题求一个集合的贡献是很容易的，再套一个子集卷积优化递推就做完了。

这里提供一种不同的做法。假设求出来集合贡献的生成函数为 ，那么答案其实就是子集卷积意义下的 。

update： 被评论区大佬教育了，事实上这个等比数列不需要恰好求到第 项， 以上的不影响答案（并且 也不影响答案），所以可以写成 然后用求逆解决。

有一种常用的集合幂级数转化为形式幂级数的方法，也就是先用子集卷积的做法求一次FMT，设 表示做子集卷积的数组，那么对于一个 ，令 ，我们就可以对 这个形式幂级数求上面这个式子了，求出来再填回 数组内，逆变换回去就是答案。

求上面的式子需要多项式快速幂以及多项式求逆，这个存在 递推的小常数做法，不需要多项式全家桶板子。

然而事实上这个做法不仅难写，难调，速度也比另一种做法慢，我赛时兴致大发冲了一顿没调出来（赛时还得急急忙忙写另一种做法来补救，还因为没判重边WA穿了），赛后调出来了还得卡常……这个做法看着一乐就好了，以后比赛还是不建议搞这种奇怪的操作。

update： 换成一次求逆做法后速度接近另一种做法，并且也好写很多qwq……

时间复杂度 ，代码如下（现在是update后一次求逆的写法）：

#include <bits/stdc++.h>
using namespace std;
#define maxn 300010
#define bin(x) (1<<(x))
#define mod 998244353

int n,m;
void reduce(int &x){x+=x>>31&mod;}
void FMT(int *f,int type=1){
    for(int mid=1;mid<bin(n);mid<<=1)
        for(int j=0;j<bin(n);j+=(mid<<1))
            for(int i=0;i<mid;i++){
                if(type)reduce(f[j+i+mid]+=f[j+i]-mod);
                else reduce(f[j+i+mid]-=f[j+i]);
            }
}
int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
int A[20];long long B[20];
void getinv(int *f,long long *g,int ln){
    g[0]=ksm(f[0],mod-2);
    for(int i=1;i<=ln;i++){
        g[i]=0;for(int j=1;j<=i;j++)
            g[i]+=1ll*f[j]*g[i-j]%mod;
        g[i]=1ll*(mod-g[i]%mod)*g[0]%mod;
    }
}
int cnt[maxn],F[20][maxn],G[20][maxn];
void solve(int *f,int *g,int lg){
    for(int i=1;i<bin(lg);i++)cnt[i]=cnt[i-(i&-i)]+1;
    for(int i=1;i<bin(lg);i++)F[cnt[i]][i]=f[i];for(int i=1;i<=lg;i++)FMT(F[i]);
    for(int i=0;i<bin(lg);i++){
        for(int j=0;j<=lg;j++)reduce(A[j]=-F[j][i]);
        reduce(A[0]+=1-mod);getinv(A,B,lg);
        for(int j=0;j<=lg;j++)G[j][i]=B[j];
    }
    for(int i=0;i<=lg;i++)FMT(G[i],0);
    for(int i=0;i<bin(lg);i++)g[i]=G[cnt[i]][i];
}
int f[20][20];
int s[1<<19][19],g[1<<19],ans[1<<19];

int main()
{
    cin>>n>>m;
    memset(f,63,sizeof(f));
    for(int i=1,x,y,z;i<=m;i++){
        cin>>x>>y>>z;x--;y--;
        f[x][y]=f[y][x]=min(z,f[x][y]);
    }
    for(int i=0;i<n;i++)f[i][i]=0;
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)if(i!=k)
            for(int j=0;j<n;j++)if(j!=k&&j!=i)
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    static int cnt[1<<18|1];
    for(int i=0;i<18;i++)cnt[1<<i]=i;
    for(int S=1;S<(1<<n);S++)
        for(int i=0;i<n;i++)
            s[S][i]=s[S-(S&-S)][i]+f[cnt[S&-S]][i];
    for(int S=1;S<(1<<n);S++){
        g[S]=2e9;
        for(int i=0;i<n;i++)if(S>>i&1)
            g[S]=min(g[S],s[S][i]);g[S]++;
    }
    solve(g,ans,n);
    printf("%d\n",ans[(1<<n)-1]);
}