LOJ#2340. WC2018 주 구분
#include
#define ri register int
#define fi first
#define se second
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
static char buf[rlen],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
return ans;
}
typedef long long ll;
const int mod=998244353;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline void update(int&a,const int&b){a=a+b>=mod?a+b-mod:a+b;}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}
namespace dsu{
int fa[25],du[25];
inline void init(const int&up){for(ri i=1;i<=up;++i)du[fa[i]=i]=0;}
inline int find(const int&x){return x^fa[x]?fa[x]=find(fa[x]):x;}
inline void merge(int x,int y){
++du[x],++du[y],x=find(x),y=find(y);
if(x^y)fa[x]=y;
}
}
const int N=1<<21|5;
typedef pair<int,int> pii;
pii e[650];
int sum[N],w[25],isum[N],n,m,p,g[22][N],f[22][N],bitcnt[N];
inline int calc(const int&x){return !p?1:(p<2?x:mul(x,x));}
inline void init(int sta){
dsu::init(n);
for(ri i=1,u,v;i<=m;++i){
u=e[i].fi,v=e[i].se;
if(((sta>>(u-1))&1)&&((sta>>(v-1))&1))dsu::merge(u,v);
}
bool f=1;
int ss=0;
for(ri pre=0,i=1;i<=n;++i){
if(!((sta>>(i-1))&1))continue;
if(dsu::du[i]&1)f=0;
if(!pre)pre=dsu::find(i);
else if(pre^dsu::find(i))f=0;
update(ss,w[i]);
}
isum[sta]=ksm(sum[sta]=calc(ss),mod-2);
sum[sta]*=1-f;
}
int lim;
inline void fmt(int*a,const int&type){
for(ri mid=1;mid<lim;mid<<=1)for(ri i=0;i<lim;++i)
if(i&mid)a[i]=~type?add(a[i],a[i^mid]):dec(a[i],a[i^mid]);
}
inline void update(int up){
for(ri i=1;i<=up;++i)for(ri j=0;j<lim;++j)update(f[up][j],mul(f[up-i][j],g[i][j]));
fmt(f[up],-1);
for(ri i=0;i<lim;++i)f[up][i]=bitcnt[i]^up?0:mul(f[up][i],isum[i]);
}
int main(){
freopen("lx.in","r",stdin);
n=read(),m=read(),p=read();
for(ri i=1;i<=m;++i)e[i].fi=read(),e[i].se=read();
for(ri i=1;i<=n;++i)w[i]=read();
lim=1<<n;
for(ri i=1;i<lim;++i){
init(i);
g[bitcnt[i]=bitcnt[i>>1]+(i&1)][i]=sum[i];
}
for(ri i=1;i<=n;++i)fmt(g[i],1);
f[0][0]=1,fmt(f[0],1);
for(ri i=1;i<n;++i)update(i),fmt(f[i],1);
update(n);
cout<<f[n][lim-1];
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.