C++14(g++5.4) 解法, 执行用时: 1317ms, 内存消耗: 90744K, 提交时间: 2018-06-09 15:36:15

#include<bits/stdc++.h>
#define MAXN 2000005
#define P 998244353
#define ll long long
using namespace std;
bool b[20][20];
int f[1048576][20],i,j,k,n,m,N,ans[20],o[1048576],w[1048576];
int main()
{
    for(i=2;i<1048576;i++)o[i]=o[i>>1]+1;
    cin>>n>>m>>N;
    while(m--)
    {
        cin>>i>>j;
        i--;
        j--;
        b[i][j]=b[j][i]=1;
    }
    for(i=0;i<n;i++)f[1<<i][i]=1;
    for(i=1;i<1<<n;i++)
	for(j=0;j<=o[i];j++)if(i>>j&1)
	for(k=0;k<o[i];k++)if(!(i>>k&1)&&b[j][k])
    {
        f[i|1<<k][k]+=f[i][j];
        if(f[i|1<<k][k]>=P)f[i|1<<k][k]-=P;
    }
    for(i=1;i<1<<n;i++)
    {
        w[i]=w[i>>1]+(i&1);
        if(w[i]>=3)for(j=0;j<o[i];j++)if((i>>j&1)&&b[o[i]][j])
        {
            ans[w[i]%N]+=f[i][j];
            if(ans[w[i]%N]>=P)ans[w[i]%N]-=P;
        }
    }
    for(i=0;i<N;i++)cout<<(ll)ans[i]*(P+1)/2%P<<endl;
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 1155ms, 内存消耗: 62124K, 提交时间: 2022-08-24 23:22:38

#include<bits/stdc++.h>
using namespace std;
const int N=21,P=998244353; int n,m,k,a[N][N],f[N][1<<N],g[N],h[N];
int main() {
	int i,j,p,q,x,y;
	scanf("%d%d%d",&n,&m,&k);
	for (i=1;i<=m;i++) {
		scanf("%d%d",&x,&y);
		if (x!=y) a[x][y]=a[y][x]=1;
	}
	for (i=1;i<=n;i++) f[i][1<<i-1]=1;
	for (j=1;j<=(1<<n);j++) {
		for (i=1;i<=n;i++)
			if (j&(1<<i-1)) {p=i; break;}
		for (i=1;i<=n;i++)
			if (f[i][j]) {
				if (a[i][p]) q=__builtin_popcount(j),g[q]=(g[q]+f[i][j])%P;
				for (q=p+1;q<=n;q++)
					if (a[i][q]&&!(j&(1<<q-1)))
						f[q][j^(1<<q-1)]=(f[q][j^(1<<q-1)]+f[i][j])%P;
			}
	}
	for (i=3;i<=n;i++) h[i%k]=(h[i%k]+g[i])%P;
	for (i=0;i<k;i++) printf("%d\n",(1ll*h[i]*((P+1)/2))%P);
}