题解-HAOI2018全套

时间：2024-04-27 00:03:52

去冬令营转了一圈发现自己比别人差根源在于刷题少，见过的套路少(>ω<)

于是闲来无事把历年省选题做了一些

链接放的都是洛谷的，bz偷懒放的也是链接

AM.T1 奇怪的背包

Problem

HAOI-2018奇怪的背包

Solution

暴力 \(60\)，加上送的 \(10\) 有 \(70\) ，暴力进队

首先在模意义下倍数能表达的东西……裴蜀定理！即 \(\{kx\bmod p\}=\{k\cdot \gcd(x,p)\bmod p\}\)，所以输入的 \(V_i\) 可以先与 \(P\) 取个 \(\gcd\)

然后发现这样处理之后所有的 \(V_i|P\)，即都是 \(P\) 的因子，而 \(P\leq 10^9\) 时，不同的因子最多大约有 \(2^{10}\) 个。

所以可以很快列出方程：

\[f[i][j] += f[i-1][j]\\
f[i][\gcd(j,V_i)]+=(2^{c_i}-1)\cdot f[i][j]
\]

其中 \(f[i][j]\) 表示考虑前 \(i\) 个因子且选取数的 \(\gcd\) 为 \(j\) 时的方案数，由于这个状态两维是同阶的，所以计算次数在 \(10^6\) 左右

最后统计答案，考虑统计 \(x\) 的答案，为 \(\sum_{d|x}g[d]\)，其中 \(g[d]\) 表示选择中 \(\gcd\) 为 \(d\) 的方案总数，由 \(f\) 可得

而若 \(d\not | P\)，则 \(g[d]=0\) 不需要考虑，所以只需要考虑 \(\sum_{d|\gcd(x,P)}g[d]\)，而 \(\gcd(x,P)\) 又是 \(P\) 的因子了，可以预处理

Code

偷懒用了 \(map\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

template <typename _tp> inline void read(_tp&x){

	char c11=getchar(),ob=0;x=0;

	while(c11!='-'&&!isdigit(c11))c11=getchar();if(c11=='-')ob=1,c11=getchar();

	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();if(ob)x=-x;

}

const int N = 2047, p = 1e9+7;

int bs[N],tp;

int c[N],f[N][N],g[N];

int n,Q,P;

inline void pls(int&A,const int&B) {A += B; if(A >= p) A -= p;}

inline int qpow(int A,int B){

	int res = 1; while(B){

		if(B&1) res = (ll)res * A%p;

		A = (ll)A * A%p, B >>= 1;

	}return res;

}

map <int,int> mp;

int main(){

	read(n),read(Q),read(P);

	for(int i=1;i*i<=P;++i)

		if(P % i == 0)

			bs[++tp] = i, bs[++tp] = P/i;

	if(bs[tp] == bs[tp-1]) --tp;

	sort(bs+1,bs+tp+1);

	for(int i=1;i<=tp;++i)

		mp[bs[i]] = i;

	for(int i=1,x;i<=n;++i){

		read(x), x = __gcd(x,P);

		++c[mp[x]];

	}

	f[0][tp] = 1;

	for(int i=1;i<=tp;++i)

	for(int j=1;j<=tp;++j){

		f[i][j] = f[i-1][j];

		pls(f[i][mp[__gcd(bs[i],bs[j])]], (ll)f[i-1][j]*(qpow(2,c[i])-1)%p);

	}

	for(int i=1;i<=tp;++i)

		g[i] = f[tp][i];

	for(int i=tp;i;--i)

	for(int j=i+1;j<=tp;++j)

		if(bs[j] % bs[i] == 0)

			pls(g[j],g[i]);

	int x;

	while(Q--){

		read(x), x = __gcd(x,P);

		printf("%d\n",g[mp[x]]);

	}

	return 0;

}

AM.T2 反色游戏

Problem

HAOI-2018反色游戏

Solution

首先 \(70\) 可以动态线性基……

然后一个环同时取反影响不变，所以可以找出一棵生成树

进一步的，生成树上的边全部线性无关，而非树边取任意状态都可以在生成树上找到一个对应状态，设非树边有 \(t\) 条，答案为 \(2^t\)

然后题目要求删除每个点后的答案……明显和HNOI2012矿场搭建类似求出点双分别维护即可

如果没想全所有情况可能会很难调

Code

#include <bits/stdc++.h>

inline void cmin(int&A,const int&B) {if(A > B) A = B;}

inline void read(int&x){

	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();

	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();

}

const int N = 101000, p = 1e9+7;

struct Edge{int v,nxt;} a[N+N];

int head[N],dfn[N],low[N];

int id[N],blk[N],cut[N],fuck[N],di[N];

int sz_blk[N],son_blk[N];

int deg[N],bin[N];char s[N];

int n,m,T,_,O,dfc;

inline int qm(int x) {return x < p ? x : x - p;}

inline void ad(){

	static int x,y; read(x), read(y);

	a[++_].v = y, a[_].nxt = head[x], head[x] = _, ++deg[x];

	a[++_].v = x, a[_].nxt = head[y], head[y] = _, ++deg[y];

}

void dfs(int x){

	dfn[x] = low[x] = ++dfc;

	id[x] = O, sz_blk[x] = blk[x];

	di[x] = (x != O);

	for(int i=head[x];i;i=a[i].nxt){

		if(!dfn[a[i].v]){

			dfs(a[i].v);

			cmin(low[x], low[a[i].v]);

			sz_blk[x] += sz_blk[a[i].v];

			if(dfn[x] <= low[a[i].v]){

				++di[x];

				son_blk[x] += son_blk[a[i].v];

				if(x != O) cut[x] = 1;

				if(sz_blk[a[i].v]&1) ++fuck[x];

			}

		}else cmin(low[x], dfn[a[i].v]);

	}

	if(x == O and a[head[x]].nxt) cut[x] = 1;

}

int main(){

	bin[0] = 1;

	for(int i=1;i<N;++i) bin[i] = qm(bin[i-1] << 1);

	read(T);

	while(T--){

		read(n),read(m);

		for(int i=1;i<=m;++i) ad();

		scanf("%s",s+1);

		for(int i=1;i<=n;++i) blk[i] = s[i] - '0';

		int con = 0, sum = 0;

		for(int i=1;i<=n;++i)

			if(!dfn[i]){

				O = i, dfs(i), ++con;

				sum += (sz_blk[i] & 1);

			}

		printf("%d",sum ? 0 : bin[m-n+con]);

		for(int x=1;x<=n;++x){

			int res = bin[m - n + con - deg[x] + di[x]];

			if(fuck[x]) res = 0;

			if(sz_blk[id[x]] - son_blk[x] - blk[x] & 1) res = 0;

			if(sum - (sz_blk[id[x]] & 1)) res = 0;

			printf(" %d",res);

		}

		dfc = _ = 0;

		for(int i=1;i<=n;++i){

			head[i] = sz_blk[i] = son_blk[i] = fuck[i] = di[i] = 0;

			id[i] = deg[i] = blk[i] = dfn[i] = low[i] = cut[i] = 0;

		}

		putchar(10);

	}

	return 0;

}

AM.T3 字串覆盖

Problem

HAOI-2018字串覆盖

Solution

直接想还是很难的……

但是看到部分分那么具有提示性，肯定是拼接程序

对于 \(r-l\) 比较大的时候：建出后缀数组，可以找到一个匹配区间，建出主席树每次贪心选取

对于 \(r-l\) 比较小的时候：使用 \(O((r-l)n)\) 的空间预处理一下即可

Code

我确信我写出了一份完美的代码，只是这里地方太小，放不下 懒得写

PM.T1 苹果树

Problem

HAOI-2018苹果树

Solution

这题很坑的一点是 \(p\) 不为质数不能直接除

然后二叉树、n≤2000、随机等字样时刻提醒着要 \(O(n^2)\) Dp

为了考虑合并两个子树时新产生的距离，要维护一个深度和数组 \(g[i]\)

为了考虑合并两个子树时的带权关系，要维护一个生成树种类数组 \(h[i]\)

然后要求答案，设 \(f[i]\) 表示当前子树有 \(i\) 个节点时的期望距离和

首先 \(h[i]=i!\)，因为第 \(i\) 个点有 \(i\) 种放置方法

\[g[i]=i\cdot h[i]+\sum_{L+R+1=i}\binom {i-1}{L}(g[L]h[R]+g[R]h[L])
\]

\[f[i]=\sum_{L+R+1=i}\binom {i-1}{L}\bigl[f[L]h[R]+f[R]h[L]+g[R]h[L](L+1)+g[L]h[R](R+1)\bigr]
\]

时间复杂度 \(O(n^2)\)

Code

#include <cstdio>

typedef long long ll;

const int N = 2017;

int c[N][N],fac[N],f[N],g[N];

int n,p;

int main(){

	scanf("%d%d",&n,&p);

	fac[0] = c[0][0] = 1;

	for(int i=1;i<=n;++i){

		fac[i] = (ll)fac[i-1] * i%p;

		c[i][0] = 1;

		for(int j=1;j<=i;++j)

			c[i][j] = (c[i-1][j-1] + c[i-1][j])%p;

	}

	g[1] = 1;

	for(int i=2;i<=n;++i){

		g[i] = (ll)fac[i] * i%p;

		for(int j=0;j<i;++j){

			int L = j, R = i-j-1;

			g[i] = (g[i] + (ll)c[i-1][j] * (((ll)g[L] * fac[R] + (ll)g[R] * fac[L])%p))%p;

			f[i] = (f[i] + (ll)c[i-1][j] * (((ll)f[L] * fac[R] + (ll)g[R] * fac[L]%p * (L+1))%p))%p;

			f[i] = (f[i] + (ll)c[i-1][j] * (((ll)f[R] * fac[L] + (ll)g[L] * fac[R]%p * (R+1))%p))%p;

		}

	}

	printf("%d\n",f[n]);

	return 0;

}

PM.T2 染色

Problem

HAOI-2018染色

Solution

好吧，一开始看错题了以为是道累加贡献的水题……然而也不难

由于直接计算不方便，计算 \(g(i)\) 表示恰好出现 \(S\) 次的颜色有至少 \(i\) 种，\(f(i)\) 表示恰好 \(i\) 种

\[g(i)=\binom mi\frac {P_n^{iS}}{(S!)^i}(m-i)^{n-iS}
\]

\[g(i)=\sum_{j=i}^m\binom ji f(j)\Leftrightarrow f(i)=\sum_{j=i}^m(-1)^{j-i}\binom jig(j)
\]

最后答案为 \(\sum_i w_if_i\)，可以 \(ntt\) 加速（不用再把 \(g(j)\) 拆开了，直接求出 \(g(x)\) 后再与二项式系数做卷积）

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline void read(int&x){

	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();

	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();

}

const int N = 10001000, M = 301000, p = 1004535809, G = 3;

int rev[M];

inline int qm(const int&x) {return x < p ? x : x-p;}

inline int qpow(int A,int B){

	int res = 1; while(B){

		if(B&1) res = (ll)res * A%p;

		A = (ll)A * A%p, B >>= 1;

	}return res;

}

void ntt(int*a,int n,int sgn){

	for(int i=1;i<n;++i) if(i < rev[i]) swap(a[i],a[rev[i]]);

	for(int i=1;i<n;i<<=1){

		int gn = qpow(G, (p-1)/(i<<1));

		for(int j=0;j<n;j+=(i<<1)){

			int g = 1;

			for(int k=0;k<i;++k,g=(ll)g*gn%p){

				int x = a[j+k], y = (ll)g*a[j+k+i]%p;

				a[j+k] = qm(x+y), a[j+k+i] = qm(x-y+p);

			}

		}

	}

	if(!sgn){

		int iv = qpow(n,p-2); reverse(a+1,a+n);

		for(int i=0;i<n;++i) a[i] = (ll)a[i] * iv%p;

	}

}

void Conv(int*arr,int*brr,int n){

	int nn = 1, len = 0;

	while(nn<n+n) nn <<= 1, ++len;

	for(int i=1;i<nn;++i) rev[i] = (rev[i>>1]>>1)|((i&1)<<(len-1));

	ntt(arr,nn,1),ntt(brr,nn,1);

	for(int i=0;i<nn;++i) arr[i] = (ll)arr[i]*brr[i]%p;

	ntt(arr,nn,0);

}

int w[M],fac[N],inv[N],g[M],brr[M];

int n,m,S,L;

inline int P(int nn,int mm) {return (ll)fac[nn] * inv[nn-mm]%p;}

inline int C(int nn,int mm) {return (ll)fac[nn] * inv[mm]%p * inv[nn-mm]%p;}

int main(){

	read(n),read(m),read(S); L = min(m,n/S);

	for(int i=0;i<=m;++i) read(w[i]);

	fac[0] = inv[0] = 1;

	int MX = max(n,m);

	for(int i=1;i<=MX;++i) fac[i] = (ll)fac[i-1] * i%p;

	inv[MX] = qpow(fac[MX], p-2);

	for(int i=MX;i;--i) inv[i-1] = (ll)inv[i] * i%p;

	for(int i=0;i<=L;++i)

		g[i] = (ll)C(m,i) * P(n,i*S)%p * qpow(qpow(fac[S],i),p-2)%p * qpow(m-i,n-i*S)%p;

	for(int i=0;i<=m;++i){

		g[i] = (ll)g[i] * fac[i]%p;

		brr[i] = (i&1? p-inv[i] : inv[i]);

	}

	reverse(brr,brr+m+1);

	Conv(g,brr,m);

	int Ans = 0;

	for(int i=0;i<=m;++i)

		Ans = (Ans + (ll)w[i] * g[i+m]%p * inv[i])%p;

	printf("%d\n",Ans);

	return 0;

}

相关文章