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

牛奶

https://ac.nowcoder.com/acm/contest/11161/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]);
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-06 22:26
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 18:27
天津大学_2023
点赞 评论 收藏
转发
9 收藏 评论
分享

全站热榜

正在热议