Submission #697268

#	Time	Username	Problem	Language	Result	Execution time	Memory
697268		vjudge1	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	1635 ms	6476 KiB

amusementpark

#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
	x=0;T f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-')f=-1;
	for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
template <typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);}
template <typename T> void print(T x)
{
	if(x<0) x=-x,putchar('-'); 
	if(x>9) print(x/10);
	putchar(x%10+48);
}
template <typename T> void print(T x,char c){print(x); putchar(c);}
template<typename T>inline void output(T x){print(x,' ');}
template<typename T,typename ...Arg>inline void output(T x,Arg ...arg){output(x);output(arg...);}
const int N=20,M=1<<20,mod=998244353;
struct Mint
{
	int x;
	Mint(int y=0){x=(y%mod+mod)%mod;}
	Mint &operator = (int y){return x=(y%mod+mod)%mod,*this;}
	Mint &operator = (long long y){return x=(y%mod+mod)%mod,*this;}
	Mint &operator +=(Mint y){return x=x+y.x>=mod?x+y.x-mod:x+y.x,*this;}
	Mint &operator -=(Mint y){return x=x-y.x<0?x-y.x+mod:x-y.x,*this;}
	Mint &operator *=(Mint y){return x=1ll*x*y.x%mod,*this;}
	Mint &operator ^=(int y)
	{
		Mint a=*this,c=1;
		for(;y;y>>=1,a*=a)
			if(y&1) c*=a;
		return x=c.x,*this;
	}
	Mint &operator /=(Mint y){return *this*=y^=mod-2;}
	Mint &operator +=(int y){return x=x+y>=mod?x+y-mod:x+y,*this;}
	Mint &operator -=(int y){return x=x-y<0?x-y+mod:x-y,*this;}
	Mint &operator *=(int y){return x=1ll*x*y%mod,*this;}
	Mint &operator /=(int y){return *this *= ((Mint(y))^=mod-2);}
	Mint &operator +=(long long y){return x=x+y>=mod?x+y-mod:x+y,*this;}
	Mint &operator -=(long long y){return x=x-y<0?x-y+mod:x-y,*this;}
	Mint &operator *=(long long y){return x=1ll*x*y%mod,*this;}
	Mint &operator /=(long long y){return *this *= ((Mint(y))^=mod-2);}
	template<class T>friend Mint operator +(Mint a,T b){return a+=b;}
	template<class T>friend Mint operator -(Mint a,T b){return a-=b;}
	template<class T>friend Mint operator *(Mint a,T b){return a*=b;}
	template<class T>friend Mint operator /(Mint a,T b){return a/=b;}
	friend Mint operator ^(Mint a,int b){return a^=b;}
	friend bool operator ==(Mint a,int b){return a.x==b;}
	friend bool operator !=(Mint a,int b){return a.x!=b;}
	friend Mint operator ^(Mint a,long long b){return a^=b;}
	friend bool operator ==(Mint a,long long b){return a.x==b;}
	friend bool operator !=(Mint a,long long b){return a.x!=b;}
	bool operator ! (){return !x;}
	Mint operator - (){return x?mod-x:0;}
	bool operator <(const Mint&b)const{return x<b.x;}
};
int n,m,k,x[N*N],y[N*N],cnt[M],can[M];
Mint dp[M];
int main()
{
	read(n,m); k=1<<n;
	for(int i=1;i<=m;i++) read(x[i],y[i]);
	for(int i=0;i<k;i++)
	{
		int sum=0;
		for(int j=i;j;j&=(j-1)) sum++;
		if(sum&1) cnt[i]=1;
		else cnt[i]=mod-1;
		for(int j=1;j<=m;j++)
			if((i&(1<<(x[j]-1)))&&(i&(1<<(y[j]-1))))
			{can[i]=1;break;}
	}
	dp[0]=1;
	for(int i=1;i<k;i++)
		for(int j=i;j;j=i&(j-1))
			if(!can[j]) dp[i]+=dp[i^j]*cnt[j];
	print((dp[k-1]*m/2).x,'\n');
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37