发表文章

[最新] 牛客网 Wannafly挑战赛17 C-简单环 状压dp

a302549450 1月前 0

链接:http://www.nowcoder.com/acm/contest/114/C
来源:牛客网

时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述


示例1

输入

4 6 3
1 2
2 3
3 4
4 1
2 4
1 3

输出

4
3
0


备注:


n<=20
m<=n*(n-1)/2
k<=n

思路:把路径转化为二进制状态,设置一个数组f[i][j]表示路径终点为j,二进制下状态为i的数目,为了避免重复,可以把i最小位的1设为起点,枚举状态和终点,若终点到起点有直接连接则为答案。最后每条环仍会重复计算两次,需要求除法逆元去重。

#include<cstdio>
#include<cmath>
#include<algorithm>
#define p 998244353
#define lowbit(x) x&(-x)
int n,m,k;
bool vis[21][21]={};
int f[1<<21][21]={};//f[i][j]保存路径终点为j,二进制下状态为i的个数
int ans[21]={},len[35]={};
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x!=y)
            vis[x][y]=vis[y][x]=true;
    }
    for(int i=1;i<=n;++i)
        f[1<<i][i]=1;
    for(int i=2;i<1<<(n+1);i+=2)
    {
        int st=lowbit(i),s;
        for(int j=1;j<=n;++j)
            if(1<<j==st)
            {
                s=j;
                break;
            }
        for(int j=1;j<=n;++j)
            if(f[i][j])
            {
                if(vis[j][s])(len[__builtin_popcount(i)]+=f[i][j])%=p;
                for(int k=s+1;k<=n;++k)//从s+1开始枚举,避免重复计算路径
                    if(vis[j][k]&&!(i&(1<<k)))
                        (f[i^(1<<k)][k]+=f[i][j])%=p;
            }
    }
    for(int i=3;i<=n;++i)
        (ans[i%k]+=len[i])%=p;
    for(int i=0;i<k;++i)
        printf("%d\n",ans[i]*((long long)(p+1)/2)%p);//每个环仍旧会被重复计算两次
    return 0;
}



相关推荐
最新评论 (0)
返回
发表文章
a302549450
文章数
25
评论数
0
注册排名
987936