noip42

T1

朴素dp很好想，设 \(dp_{u,0/1}\) ，表示以 \(u\) 为根的子树，选/不选 \(u\) 所产生的最大贡献。

转移方程则有，

\[dp_{u,0} = \prod_{v\in son_{u}}\max(dp_{v,0},dp_{v,1})
\]

\[dp_{u,1} = w_{u}\prod_{v\in son_{u}}dp_{v,0}
\]

发现在dp过程中直接取模，大小关系无法确定。

考虑对每个难度取 \(\log\) ，在dp的过程中记录dp到当前值的 \(\log\) 和，dp转移时的比较大小时由比值改成比 \(\log\) 即可，dp数组仍然记录当前最大值，dp时就可以取模了。

当值很大，比较大小时，直接计算不太好搞尤其是再带个取模，可以通过取 \(log\) 将乘法变为加法。

当然，也可以用高精，1e9+7进制，最后一位就是答案，但毕竟不是人人都是太虚真人

Code

#include<cmath>

#include<cstdio>

#define MAX 200020

#define re register

#define int long long

int n,w[MAX];

double sum[MAX][2];

struct graph

{

	int next;

	int to;

}edge[MAX<<1];

int cnt=1,head[MAX];

inline void add(int u,int v)

{ edge[++cnt] = (graph){head[u],v},head[u] = cnt; }

namespace read

{

	struct stream

	{

		template<typename type>inline stream &operator >>(type &s)

		{

			int w=1; s=0; char ch=getchar();

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

			while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }

			return s*=w,*this;

		}

	}cin;

}using read::cin;

namespace OMA

{

	int dp[MAX][2];

	const int p = 1e9+7;

	inline int max(int a,int b)

	{ return a>b?a:b; }

	inline void dfs(int u,int fa)

	{

		dp[u][1] = w[u],dp[u][0] = 1;

		for(re int i=head[u],v; i; i=edge[i].next)

		{

			v = edge[i].to;

			if(v!=fa)

			{

				dfs(v,u);

				(dp[u][1] *= dp[v][0]) %= p;

				sum[u][1] += sum[v][0];

				//(dp[u][0] *= max(dp[v][0],dp[v][1])) %= p;

				if(sum[v][0]>sum[v][1])

				{ (dp[u][0] *= dp[v][0]) %= p,sum[u][0] += sum[v][0]; }

				else

				{ (dp[u][0] *= dp[v][1]) %= p,sum[u][0] += sum[v][1]; }

			}

		}

	}

	signed main()

	{

		//system("./data");

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

		cin >> n;

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

		{ cin >> w[i]; sum[i][1] = log(w[i]); }

		for(re int i=2,u,v; i<=n; i++)

		{ cin >> u >> v; add(u,v),add(v,u); }

		dfs(1,0);

		//printf("%0.6lf %0.6lf\n",sum[1][0],sum[1][1]);

		//printf("%lld %lld\n",dp[1][0],dp[1][1]);

		printf("%lld\n",sum[1][0]>sum[1][1]?dp[1][0]:dp[1][1]);

		return 0;

	}

}

signed main()

{ return OMA::main(); }

T2

考虑将 \(n\) 划分成形如 \(p,2p,,,,2^{k}p\) 的形式，其中 \(p\) 为奇数。

举个例子，\(n=8\) , 则划分成了：

1 2 4 8
3 6
5
7

不难发现，链长都是 \(log\) 级别的，每次都是乘上2出来下一个数。且 \(A,B\) 在同一条链上肯定是间隔着选的。

考虑将链分奇偶来考虑。

对于链长为奇数的，则必然是 \(A\) 比 \(B\) 多一个，或者 \(B\)比 \(A\) 多一个，所以最终 \(A\) 的大小会在一个区间 \([l,r]\) 内，\(l\) 全少个1，\(r\) 全多个1。比 \(l\) 多的那部分必然都是由奇数链贡献来的，所以最后计算组合数 \(\tbinom{k_{1}}{m-l}\) ，其中，\(k_{1}\) 表示奇数链的个数。
对于链长为偶数的，则必然是给 \(A\) 分一半， \(B\) 分一半，则对答案会产生2的贡献。每条链都能产生2的贡献，设一共有 \(k_{2}\) 条偶数链，则对答案产生的贡献为 \(2^{k_{2}}\)

则对于每次询问，最后答案即为 \(2^{k_{2}}\tbinom{k_{1}}{m-l}\) ，要用到 \(lucas\) 。

Code

#include<cstdio>

#define MAX 100100

#define re register

#define int long long

int n,q,l,pow=1,tub;

const int p = 10000019;

int c[p+1],inv[p+1];

namespace read

{

	struct stream

	{

		template<typename type>inline stream &operator >>(type &s)

		{

			int w=1; s=0; char ch=getchar();

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

			while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }

			return s*=w,*this;

		}

	}cin;

}using read::cin;

namespace OMA

{

	inline int quickpow(int a,int b)

	{

		int ans = 1;

		while(b)

		{

			if(b&1)

			{ ans = ans*a%p; }

			a = a*a%p;

			b >>= 1;

		}

		return ans;

	}

	inline int C(int n,int m)

	{ return m>n?0:c[n]*inv[m]%p*inv[n-m]%p; }

	inline int lucas(int n,int m)

	{ return (m>n||m<0)?0:(!m?1:lucas(n/p,m/p)*C(n%p,m%p)%p); }

	signed main()

	{

		cin >> n >> q;

		c[0] = inv[0] = 1;

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

		{ c[i] = i*c[i-1]%p; }

		inv[n] = quickpow(c[n],p-2);

		for(re int i=n-1; i; i--)

		{ inv[i] = (i+1)*inv[i+1]%p; }

		int last = n,cnt = 1;

		for(re int i=0; ~i; i++)

		{

			if(!last)

			{ break ; }

			int tmp = last-n/cnt;

			l += (tmp+(last&1))/2*(i/2);

			if(i&1)

			{ (tub += (tmp+(last&1))/2) %= p; }

			else

			{ pow = pow*quickpow(2,(tmp+(last&1))/2)%p; }

			last = n/cnt;

			cnt *= 2;

		}

		for(re int i=1,m; i<=q; i++)

		{ cin >> m; printf("%lld\n",pow*lucas(tub,m-l)%p); }

		return 0;

	}

}

signed main()

{ return OMA::main(); }

T3

阴间dp

首先，对于本题的dp，有两种，

设 \(f_{i,j}\) 表示当前dp到数字 \(i\) 即最大数为 \(i\) ，总和为 \(j\) 的方案数。转移则有，\(f_{i,j}=f_{i-1,j}+f_{i-1,j-k}\;,k\in[1,j]\) 。
设 \(g_{i,j}\) 表示划分成了\(i\) 个数，总和为 \(j\) 的方案数。转移则有，\(g_{i,j}=g_{i-1,j}+g_{i,j-i}\) 。

两种dp单独搞都是 \(O(n^{2})\) 。

有一个比较没见过的常见的套路然而我并不知道，将 \(n\) 按 \(\sqrt{n}\) 分成两部分，分别使用两种dp，可做到 \(O(n\sqrt{n})\) 。

Code

#include<cmath>

#include<cstdio>

#include<cstring>

#define MAX 100010

#define re register

namespace OMA

{

	int x,y,n,p;

	int f[MAX],g[MAX],sum[MAX];

	inline int max(int a,int b)

	{ return a>b?a:b; }

	inline int DP(int a)

	{

		memset(f,0,sizeof(f));

		memset(g,0,sizeof(g));

		memset(sum,0,sizeof(sum));

		f[0] = g[0] = sum[0] = 1;

		int b = max(sqrt(n),a);

		for(re int i=a; i<=b; i++)

		{

			for(re int j=i; j<=n; j++)

			{ (f[j] += f[j-i]) %= p; }

		}

		for(re int i=1; i<=n/b; i++)

		{

			int c = i*b+i;

			for(re int j=i; j+c<=n; j++)

			{ (g[j] += g[j-i]) %= p; }

			for(re int j=0; j+c<=n; j++)

			{ (sum[j+c] += g[j]) %= p; }

		}

		int ans = 0;

		for(re int i=0; i<=n; i++)

		{ (ans += 1LL*f[i]*sum[n-i]%p) %= p; }

		return ans;

	}

	signed main()

	{

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

		printf("%d\n",((DP(x)-DP(y+1))%p+p)%p);

		return 0;

	}

}

signed main()

{ return OMA::main(); }

T4

暴力乱搞10pts。

正解：

要用manacher，不会，所以咕了。

官方题解

巴特西

noip42

T1

T2

T3

T4

最新文章

热门文章