#T1随

又是liu_...................

数列n，m个操作，每次随机取a[i]，x=x*a[i]%k; 问题是求x期望%mod;

首先考虑到期望转移过程中存在%k,一般套路线性期望行不通，dp的话考虑转移神魔。

k较小，才不到1000左右，我们可以压余数。f[i][j]表示第i次，余数为j时概率，最终求出m次时整个剩余系的概率就好。

嗯？That‘s it？

NO！！！！！！！！！！！ m(max)=1e9;数组都开不下的。

以上内容纯属骗取部分分。。

现在很明显要用矩阵优化了，可是咱好像不会配矩阵，前几天NOI2020的美食家还在题库里晾着呢。。题目很良心，给出了原根的概念，尽管我还是不会。。好了，进入正解。首先看到原根的概念，mod以内的所有数都可以表示为root^{x%mod的形式，看到条件a[1]<mod，这样就更简单了。我们可以先找到原根，题目给了充要条件，n}2找就好，O(n)的我也不会。找到以后处理次幂对应的剩余系关系，输入进来a[i]后配相应位置的矩阵，套个快速幂就ok了。

需要注意的点很多，现在已经是由期望转成了计数，总方案数n^m(mod-2)很明显。我们的矩阵里配的是方案数，而且还是个简便的循环矩阵，最重要的是注意模数。方案数最终是mod1e9+7,而矩阵里面因为搞的是mod k 意义下的指数次幂，由欧拉定理可知mod k-1 。还有处理原根时mod 是k。

题目到此解决，本题方法很多：循环卷积，FFT，倍增。。。。好吧，我还是菜。考场上瞎胡了个假dp，特判了两个点，结果就十分，（我竟然把m放循环里乘了，放着qpow吹西北风。。。。。。。。。。）

code

#include<bits/stdc++.h>

#define int long long

using namespace std;

int n,m,mod=1e9+7,k;

int a[10000001],lg[100001],mi[100001],root;

struct node

{	int s[1002];

	inline void clear(){for(int i=0;i<k-1;++i)s[i]=0;}

	inline node operator *(const node &ZXB)const

	{	node ans;

		ans.clear();

		for(int i=0;i<k-1;++i)

		for(int j=0;j<k-1;++j)

		(ans.s[(i+j)%(k-1)]=ans.s[(i+j)%(k-1)]+s[i]*ZXB.s[j])%=mod;

		return ans;

	}

};

node ZXB;

inline node mmqpow(int mmm)

{	node aa,g;

	aa.s[lg[1]]++;

	while(mmm)

	{	if(mmm&1)aa=aa*ZXB;

		ZXB=ZXB*ZXB;

		mmm>>=1;

	}

	return aa;

}

inline int qpow(int a,int b)

{	int base=1;

	while(b)

	{	if(b&1)base=base*a%mod;

		a=a*a%mod;

		b>>=1;

	}

	return base;

}

inline int get_root()

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

	{	int base=1;bool bo=0;

		for(int j=1;j<k-1;++j)

		{	base=base*i%k;

			if(base==1){bo=1;break;}

		}

		if(!bo)return i;

	}

}

signed main()

{	scanf("%lld%lld%lld",&n,&m,&k);mi[0]=1;

	root=get_root();

	if(k==1){cout<<1<<endl;return 0;}

	for(int i=1;i<k-1;++i)mi[i]=mi[i-1]*root%k,lg[mi[i]]=i;

	for(int i=1;i<=n;++i)scanf("%lld",&a[i]),ZXB.s[lg[a[i]]]++;

	int inv=qpow(qpow(n,m),mod-2);

	node ans=mmqpow(m);

	int sum;

	for(int i=0;i<k-1;++i)(sum+=ans.s[i]*mi[i]%mod)%=mod;

	printf("%lld\n",sum*inv%mod);

}

#T2单

树上好题，挂上求和，暴力得完蛋，仔细看a和b，发现对于x 和 fa 来说，由fa转到x，b数值的变化即为：-x的子树a[i]和+else 接着else变做all -x的子树，（有些麻烦，x的子树就叫sum吧）则b[fa]-2*sum[x]+all=b[x];

截至到现在t==0的情况显然，冲个XIN_TEAM定住一个根，在来向下跑即可。

再来看t=1的情况，很有高斯的味道，但是O(n^3)我是受不了的，这启示我们手动消元。上面式子都推出来了，我还耸啥！！于是开始干，心情那叫个爽啊，大哥终于有会的题了哈哈。。

CAO！！！！！！！！！！！

手动消元等式两边系数全TM干成了0。。。。。陷入慌乱中，此时听到T1体面有误，肯定dp打假了，心情更完蛋。然后也没去好好思考，然后就没有然后了。

在考场上的成果其实很接近了，我到了定根算du[x]一步，等式乱搞得出a[fa]=（和儿子差分的和-（du[x]-2）×all））/2;这个式子是原创，其实思路也都差不多。

就差一个all了，手动消元干出了0，其实我的思路疏忽了d[root]=sum[2]......+sum[n];

有了这个all很易得到，唉，还是太菜了。。

行吧，反正有进步就好，不过我好像暴零了这题，原因是several cases 木有换行。。。。。。。30pts扔掉了。情绪波动暴力也懒得打了，错误分析数据导致放弃了高斯消元（我才不会说是我板子忘了哈哈）

code

#include<bits/stdc++.h>

#define int long long

using namespace std;

int T,n,t,a[100010],b[100010],head[100010],du[100010],tot,ppp;

int sum[1000010];

struct bbb

{int to,next;}bian[200010];

inline void XIN_TEAM(int x,int fa)

{	for(int i=head[x];i;i=bian[i].next)

	{	int v=bian[i].to;

		if(v==fa)continue;

		XIN_TEAM(v,x);

		ppp+=b[v]-b[x];

	}

}

inline void work1()

{	for(int i=1;i<=n;++i)scanf("%lld",&b[i]);ppp=0;

	XIN_TEAM(1,0);

	int all=(2*b[1]+ppp)/(n-1);

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

	{	int ans=0;

		for(int j=head[i];j;j=bian[j].next)

		{	int v=bian[j].to;

			ans+=b[v]-b[i];

		}

		printf("%lld ",(ans-(du[i]-2)*all)/2);

	}

	printf("\n");

}

inline void XIN_TEAM1(int x,int fa,int dep)

{	sum[x]=a[x];b[1]+=dep*a[x];

	for(int i=head[x];i;i=bian[i].next)

	{	int v=bian[i].to;

		if(v==fa)continue;

		XIN_TEAM1(v,x,dep+1);

		sum[x]+=sum[v];

	}

}

inline void XIN_TEAM2(int x,int fa)

{	for(int i=head[x];i;i=bian[i].next)

	{	int v=bian[i].to;

		if(v==fa)continue;

		b[v]=b[x]+sum[1]-sum[v]-sum[v];

		XIN_TEAM2(v,x);

	}

}

inline void work2()

{	for(int i=1;i<=n;++i)scanf("%lld",&a[i]);

	XIN_TEAM1(1,0,0);

	XIN_TEAM2(1,0);

	for(int i=1;i<=n;++i)printf("%lld ",b[i]);

	printf("\n");

}

inline void add(int u,int v)

{	bian[++tot].to=v;

	bian[tot].next=head[u];

	head[u]=tot;

}

inline void clear()

{	if(t)

	{	memset(head,0,sizeof(head));

		memset(du,0,sizeof(du));

		memset(b,0,sizeof(b));

		memset(a,0,sizeof(a));

		tot=0;

	}

	else

	{	b[1]=0;

		memset(head,0,sizeof(head));

		memset(du,0,sizeof(du));

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

		memset(b,0,sizeof(b));

		memset(a,0,sizeof(a));

		tot=0;

	}

}

signed main()

{		scanf("%lld",&T);

	while(T--)

	{	clear();

		scanf("%lld",&n);

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

		{	int a,b;

			scanf("%lld%lld",&a,&b);

			add(a,b);add(b,a);

			du[a]++;du[b]++;

		}

		scanf("%lld",&t);

		if(t)work1();

		else work2();

	}

}

T3题

这名字真简洁哈。

这算是个计数全家桶吧，又是dp又是组合数，还有catalan。

case 0:无限制，我没用catalan。考虑横向为i，纵向为n-i，则有ans+=A(n,n)/(A(i/2,i/2)A(i/2,i/2)A((n-i)/2,(n-i)/2)*A((n-i)/2,(n-i)/2).这个式子好想也好理解，就是n个操作瞎排最后比上重复计数（每种操作自己无需调换，是等效的，所以去重）

case 1：只能在x非负半轴，把向左理解为向左，向右理解为向上，其实就是要到达（n/2,n/2）这个点，很明显是板子，catalan第n项

case 2：考虑当前为i，且第一次回到原点为j。f[i]=f[i]+f[i-j]* 4 *ca(j-1);

case 3：只允许在第一象限动。还是分i和n-i。明显是ca(i/2)ca((n-i)/2)C(n,i).

code

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int mod=1000000007;int jc[200001];int inv[200001];

int n,t;

inline int qpow(int a,int b)

{	int base=1;

	while(b)

	{	if(b&1)base=base*a%mod;

		a=a*a%mod;

		b>>=1;

	}

	return base;

}

inline void work1()

{	int ans=0;n/=2;

	ans=jc[2*n]*inv[n]%mod*inv[n]%mod*qpow(n+1,mod-2)%mod;

	printf("%lld\n",ans);

}

inline void work3()

{	int ans=0;

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

	{(ans+=jc[i]*inv[i/2]%mod*inv[i/2]%mod*jc[n]%mod*inv[i]%mod*inv[n-i]%mod*jc[n-i]%mod*inv[(n-i)/2]%mod*inv[(n-i)/2]%mod*qpow(i/2+1,mod-2)%mod*qpow((n-i)/2+1,mod-2)%mod)%=mod;}

	printf("%lld\n",ans);

}

inline void work2()

{	int ans=0;

	for(int i=0;i<=n;i+=2)(ans+=(jc[n])*inv[i/2]%mod*inv[i/2]%mod*inv[(n-i)/2]%mod*inv[(n-i)/2])%=mod;

	printf("%lld",ans);

}

inline void work()

{	int ans=0,f[100001];n/=2;

	f[0]=1;f[1]=4;

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

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

	(f[i]+=f[i-j]*4%mod*jc[j*2-2]%mod*inv[j-1]%mod*inv[j-1]%mod*qpow(j,mod-2)%mod)%=mod;

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

}

signed main()

{

	scanf("%lld%lld",&n,&t);

	jc[0]=1;inv[0]=1;inv[1]=1;

	for(int i=1;i<=n*2;++i)inv[i]=qpow(i,mod-2);

	for(int i=2;i<=n*2;++i)inv[i]=inv[i-1]*inv[i]%mod;

	for(int i=1;i<=n*2;++i)jc[i]=jc[i-1]*i%mod;

	if(t==1)work1();

	if(t==0)work2();

	if(t==3)work3();

	if(t==2)work();

	return 0;

}

T4大佬

暴力好题。

考场上都没看，暴力分没拿。。。

关键点是想到分开打他和搞自己，自己的生命和其他是互不干扰的，而且打大佬的天数当然多多益善，所以先上dp求出我可以不回血的Day（max）。

现在有Daymax，我可以冲一个变形信队，整出来不同情况的伤害和天数，注意中途hash去重。

最后盘大佬，C[i]<Day 显然，我只要一天干他一滴血他就得挂。上面变形信队突出来了不同情况的伤害和对应天数，因为不能大于两次攻击，所以分两种情况。不管是一次还是两次，都要保证不能干成副的，干成0当然最好，剩下的天数一滴一滴干也可以。在sort后我要找的差值还是单调的，那就更容易了，好了，本题到此结束。

code

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int mod=100003;

int n,m,mc,maxn,Day,cnt,dp[1001][101],C[1001],hack[1001],cure[1001],tot,head[1100001];

struct node

{int i,f,l;

};

struct sss

{int x,y,next;

}bian[1000012];

pair<int,int>asd[1000001];

struct ppp

{	inline bool query(int F,int D)

	{	int p=(F*131+D)%mod;

		for(int i=head[p];i;i=bian[i].next)if(bian[i].x==F and bian[i].y==D)return 1;

		return 0;

	}

	inline void add(int u,int v)

	{	int p=(u*131+v)%mod;

		bian[++cnt].x=u;

		bian[cnt].y=v;

		bian[cnt].next=head[p];

		head[p]=cnt;

	}

}hash;

namespace AYX

{	inline void XIN_TEAM()

	{	queue<node> Q;Q.push((node){1,1,0});

		while(!Q.empty())

		{	node now=Q.front();Q.pop();

			if(now.i==Day)continue;

			Q.push((node){now.i+1,now.f,now.l+1});

			if(now.l>1 and now.f*now.l<=maxn and !hash.query(now.f*now.l,now.i+1))

			{	hash.add(now.f*now.l,now.i+1);

				Q.push((node){now.i+1,now.f*now.l,now.l});

				asd[++tot]=make_pair(now.f*now.l,now.i+1);

			}

		}

	}

	inline short main()

	{	scanf("%lld%lld%lld",&n,&m,&mc);

		for(int i=1;i<=n;++i)scanf("%lld",&hack[i]);

		for(int i=1;i<=n;++i)scanf("%lld",&cure[i]);

		for(int i=1;i<=m;++i)scanf("%lld",&C[i]),maxn=max(maxn,C[i]);

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

		for(int j=hack[i];j<=mc;++j)

		{	dp[i][j-hack[i]]=max(dp[i][j-hack[i]],dp[i-1][j]+1);

			dp[i][min(mc,j-hack[i]+cure[i])]=max(dp[i][min(mc,j-hack[i]+cure[i])],dp[i-1][j]);

		}

		for(int i=1;i<=n;++i)for(int j=1;j<=mc;++j)Day=max(Day,dp[i][j]);

		XIN_TEAM();

		sort(&asd[1],&asd[tot+1]);

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

		{	if(C[i]<=Day){printf("1\n");continue;}

			bool bo=0;int mm=0x7fffffff;

			for(int j=tot,k=1;j;--j)

			{	while(k<tot and asd[k].first+asd[j].first<=C[i])mm=min(mm,asd[k].second-asd[k].first),++k;

				if(mm+C[i]-asd[j].first<=Day-asd[j].second){bo=1;printf("1\n");break;}

				if(asd[j].first<=C[i] and C[i]-asd[j].first<=Day-asd[j].second){bo=1;printf("1\n");break;}

			}

			if(!bo)printf("0\n");

		}

		return 0;

	}

}

signed main()

{return AYX::main();

}

巴特西

NOIP 模拟四考试总结

#T1随

#T2单

T3题

T4大佬

最新文章

热门文章

巴特西

NOIP 模拟四 考试总结

#T1随

#T2单

T3题

T4大佬

最新文章

热门文章

NOIP 模拟四考试总结