AGC 043 C - Giant Graph SG函数 dp 贪心

LINK：Giant Graph

神仙题目。

容易发现在图中选择某个点的贡献为\(10^{18\cdot(x+y+z)}\) 这等价于多选一个点多大一点就多乘了一个\(10^{18}\)

所以显然是贪心的选取是最优的。

直接贪复杂度较高考虑一个点的是否选取只和其某个维度上相邻的点有关。

形式化的设\(f_{i,j,k}\)表示当前这个点是否选择那么有\(f_{i,j,k}=\Pi [f_{i',j'.k'}=0]\)

可以观察出来这是一个DAG.接下来的一步就比较神仙了。

这个dp转移每次只是依据一个维度所以可以三个维度分开做。

就是说三个维度变成三张图分别做合起来等价于把三张图的游戏结果合起来。

这其实本质上就是三个公平游戏利用SG函数合起来即可。值得一提的是听说SG函数的上界为\(\sqrt m\) 所以不需要FWT可以直接暴力枚举。

复杂度O(m).

code

//#include<bits\stdc++.h>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<queue>

#include<deque>

#include<stack>

#include<vector>

#include<algorithm>

#include<utility>

#include<bitset>

#include<set>

#include<map>

#define ll long long

#define db double

#define INF 10000000000000010ll

#define ldb long double

#define pb push_back

#define put_(x) printf("%d ",x);

#define get(x) x=read()

#define gt(x) scanf("%d",&x)

#define gi(x) scanf("%lf",&x)

#define put(x) printf("%d\n",x)

#define putl(x) printf("%lld\n",x)

#define gc(a) scanf("%s",a+1)

#define rep(p,n,i) for(RE int i=p;i<=n;++i)

#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])

#define fep(n,p,i) for(RE int i=n;i>=p;--i)

#define vep(p,n,i) for(RE int i=p;i<n;++i)

#define pii pair<int,int>

#define mk make_pair

#define RE register

#define P 1000000007

#define gf(x) scanf("%lf",&x)

#define pf(x) ((x)*(x))

#define uint unsigned long long

#define ui unsigned

#define EPS 1e-8

#define sq sqrt

#define S second

#define F first

#define mod 998244353

using namespace std;

char buf[1<<15],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;

}

inline int read()

{

    RE int x=0,f=1;RE char ch=getc();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}

    while(ch>='0'&&ch<='9'){x=((ll)x*10+ch-'0')%mod;ch=getc();}

    return x*f;

}

const int MAXN=100010,M=1000000000000000000ll%mod;

int c[MAXN];int n,m;

inline int add(int x,int y){return x=x+y>=mod?x+y-mod:x+y;}

inline int mul(int x,int y){return (ll)x*y%mod;}

struct wy

{

	int f[MAXN],g[MAXN],len;

	int lin[MAXN],ver[MAXN],nex[MAXN];

	inline void add(int x,int y)

	{

		ver[++len]=y;

		nex[len]=lin[x];

		lin[x]=len;

	}

	inline void topsort()

	{

		fep(n,1,j)

		{

			go(j)c[f[tn]]=1;

			int ww=0;

			while(c[ww])++ww;

			f[j]=ww;

			go(j)c[f[tn]]=0;

		}

		int ww=M;

		rep(1,n,i)

		{

			g[f[i]]=(g[f[i]]+ww)%mod;

			ww=mul(ww,M);

			//cout<<g[f[i]]<<' '<<ww<<endl;

		}

	}

}A[3];

int main()

{

	//freopen("1.in","r",stdin);

	get(n);

	rep(0,2,i)

	{

		get(m);

		rep(1,m,j)

		{

			int get(x),get(y);

			if(x>y)swap(x,y);

			A[i].add(x,y);

		}

		A[i].topsort();

	}

	int ans=0;

	rep(0,511,i)rep(0,511,j)

	ans=add(ans,mul(mul(A[0].g[i],A[1].g[j]),A[2].g[i^j]));

	put(ans);return 0;

}

巴特西

AGC 043 C - Giant Graph SG函数 dp 贪心

最新文章

热门文章