本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-08-12 11:54:12

做法

可以快速得出 $x \in [1,100]$ 的答案。
将其记录下来，通过矩阵乘法转移到 $x \in [2,101]$ 的答案。
以此类推。

Code

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const ll mod=1e9+7;
	const int maxn=1e5+5;
	const int mamx=105;
	int n,x,d[maxn];
	struct Matrix
	{
		ll imap[mamx][mamx];
		void init()
		{
			memset(imap,0,sizeof imap);
		}
		Matrix operator*(const Matrix& b)
		{
			Matrix ans;
			ans.init();
			for(int i=1;i<=101;i++)
			{
				for(int j=1;j<=101;j++)
				{
					for(int k=1;k<=101;k++)
					{
						ans.imap[i][j]+=imap[i][k]*b.imap[k][j];
						ans.imap[i][j]%=mod;
					}
				}
			}
			return ans;
		}
	}A,B,out;
	Matrix ksm(Matrix a,ll b)
	{
		Matrix ret;
		ret.init();
		for(int i=1;i<=101;i++)ret.imap[i][i]=1;
		while(b)
		{
			if(b&1)ret=ret*a;
			a=a*a;
			b>>=1;
		}
		return ret;
	}
	ll f0[105],f[105],cnt[105];
	void main()
	{
		scanf("%d%d",&n,&x);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&d[i]);
			cnt[d[i]]++;
		}
		f0[0]=1;
		for(int i=1;i<=100;i++)
		{
			for(int j=1;j<=i;j++)
			{
				f0[i]+=cnt[j]*f0[i-j];
				f0[i]%=mod;
			}
		}
		f[0]=1;
		for(int i=1;i<=100;i++)
		{
			f[i]=f[i-1]+f0[i];
			f[i]%=mod;
		}
		if(x<=100)
		{
			printf("%lld",f[x]);
			return;
		}
		A.init();
		B.init();
		for(int i=1;i<=101;i++)
		{
			A.imap[1][i]=f[100-i+1];
		}
		for(int i=1;i<=100;i++)
		{
			B.imap[i][1]=cnt[i];
		}
		B.imap[101][1]=1;\/\/根节点没选，选上
		for(int i=1;i<=99;i++)
		{
			B.imap[i][i+1]=1;
		 } 
		B.imap[101][101]=1;
		out=A*ksm(B,x-100);
		printf("%lld",out.imap[1][1]);
	}
}
int main()
{
	Main::main();
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-08-16 16:04:50

做法

做法很显然，就是贪心的使低位尽量小。

对于每一位，都尽量选择在它后面的，且最小的元素与之交换。

如果后面有多个最小的，那怎么做呢？

因为要使字典序尽可能小，而交换的时候必然有一位变大，所以使变大的这一位尽量靠后。

所以，做法就是，对于每一位，将其与在它后面的，最小且最远的元素交换。

另外要注意，由题目性质可以得出，两个元素交换之后，它们之间的元素（包括自己）就不能进行交换操作了，要进行判断。

Code

#include <bits\/stdc++.h> \/\/ scanf
using namespace std;
const int MAXN = 1e7+5; \/\/ Set a right value according to your solution.
int n, a[MAXN];

namespace Generator {

	unsigned long long k1, k2;
	int thres;

	inline unsigned long long xorShift128Plus() {
		unsigned long long k3 = k1, k4 = k2;
		k1 = k4, k3 ^= (k3 << 23), k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
		return k2 + k4;
	}

	inline void generate() {
		for (int i = 1; i <= n; ++i) {
			a[i] = xorShift128Plus() % thres;
		}
	}

} \/\/ namespace Generator.
int imin[MAXN];
int pos[MAXN];
int main() {
	scanf("%d", &n);
	scanf("%llu %llu %d", &Generator::k1, &Generator::k2, &Generator::thres);
	Generator::generate();
	\/\/ Now array a[1..n] represents the sequence A in the statement.
	imin[n]=a[n];
	pos[n]=n;
	for(register int i=n-1;i>=1;i--)
	{
		if(a[i]<imin[i+1])
		{
			imin[i]=a[i];
			pos[i]=i;
		}
		else
		{
			imin[i]=imin[i+1];
			pos[i]=pos[i+1];
		}
	}
	register int _pos;
	for(register int i=1;i<=n;i++)
	{
		if(imin[i]==a[i])continue;
		_pos=pos[i];
		swap(a[i],a[pos[i]]);
		i=_pos;
	}
	unsigned long long ans=0;
	for(register int i=1;i<=n;i++)
	{
		ans=(ans+(unsigned long long)i*(unsigned long long)a[i]);
	}
	printf("%llu",ans);
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-08-18 19:31:20

做法

基础贪心：用优先队列维护值最大的点，选了一个点之后将其退出优先队列
改进：由于选一个点周围两个点可能比选了这个点更优，所以建立一个新的点，代表选了这两个点的收益（要减去选中间点的收益抵消影响）（权值：$a_{mid-1}+a_{mid+1}-a_{mid}$）

就是可反悔的贪心。

Code

正在写。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-08-19 12:39:37

题外话

感觉这道题有点降智（应该只是对我来说），就写一篇题解记录一下。

做法

我们可以这样理解：分母乘上一个数 $x$ ，就代表这个分数除以 $x$；分子乘上一个数 $x$，就代表这个分数乘 $x$。

我们先假设：
$\frac{a \cdot x}{b \cdot y} = \frac{c}{d}$
转化为：
$\frac{a}{b} \cdot \frac{x}{y} = \frac{c}{d}$
然后计算得出：
$\frac{x}{y} = \frac{c}{d} \cdot \frac{b}{a}$
这样我们就知道了，$\frac{a}{b}$ 分子和分母各乘上多少，才能与 $\frac{c}{d}$ 相等。

如果 $x = 1$，那么分子不需要作乘法，否则分子需要进行一次乘法。
同理，如果 $y=1$，那么分母不需要作乘法，否则分母需要进行一次乘法。

这样就结束了吗？没有。

分子可能为 $0$。

如果两个分数的分子中有一个为 $0$，那么只需要将另一个分数的分子乘上 $0$，就行了。

如果两个分数的分子都为 $0$，那么不需要处理。

Code

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	int t;
	ll gcd(ll a,ll b)
	{
		return !b?a:gcd(b,a%b);
	}
	ll lcm(ll a,ll b)
	{
		return a\/gcd(a,b)*b;
	}
	void main()
	{
		scanf("%d",&t);
		while(t--)
		{
			ll a,b,c,d;
			scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
			if(a==0&&c!=0)
			{
				printf("1\n");
				continue;
			}
			else if(a!=0&&c==0)
			{
				printf("1\n");
				continue;
			}
			if(a==0&&c==0)
			{
				printf("0\n");
				continue;
			}
			a*=d;
			b*=c;
			ll _gcd=gcd(a,b);
			a\/=_gcd;
			b\/=_gcd;
			int ans=0;
			if(b>1)ans++;
			if(a>1)ans++;
			printf("%d\n",ans);
		}
	}
}
int main()
{
	Main::main();
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-08-21 12:12:45

高位到低位贪心。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-08-21 22:01:09

题外话

第一次打出 $1200$ 以上的表现分，上绿了。

A&B&C

略过

D

枚举每一个位置作为 $x$，然后利用前缀和二分得出 $y,z,w$。

E

设状态 $dp_{i,j,k}$ 表示第一种组合使用数量为 $i$，第二种组合使用数量为 $j$，第三种组合数量为 $k$ 的方案数。

#include <bits\/stdc++.h>
using namespace std;
namespace Main {
	typedef long long ll;
	const ll mod=998244353;
	const int maxn=305;
	map<pair<ll,ll>,bool> mp;
	ll f[maxn][maxn][maxn];
	int n,m;
	ll A,B,C,D,E,F;
	void main() {
		scanf("%d%d",&n,&m);
		scanf("%lld%lld%lld%lld%lld%lld",&A,&B,&C,&D,&E,&F);
		ll x,y;
		for(int i=1; i<=m; i++) {
			scanf("%lld%lld",&x,&y);
			mp[make_pair(x,y)]=1;
		}
		f[0][0][0]=1;
		for(ll i=0; i<=n; i++) {
			for(ll j=0; j<=n-i; j++) {
				for(ll k=0; k<=n-i-j; k++) {
					if(mp[make_pair(i*A+j*C+k*E,i*B+j*D+k*F)]) {
						continue;
					}
					if(i) {
						f[i][j][k]+=f[i-1][j][k];
					}
					if(j) {
						f[i][j][k]+=f[i][j-1][k];
					}
					if(k) {
						f[i][j][k]+=f[i][j][k-1];
					}
					f[i][j][k]%=mod;
				}
			}
		}
		ll ans=0;
		for(ll i=0; i<=n; i++) {
			for(ll j=0; j<=n-i; j++) {
				ll k=n-i-j;
				ans+=f[i][j][k];
				ans%=mod;
			}
		}
		printf("%lld",ans);
	}
}
int main() {
	Main::main();
	return 0;
}  

F

在想

G

这道题由于我之前维护 $6$ 个 tag 的做法假了，所以我只会邹神的做法。 我搞的分块做法 AC了。
感觉 $6$ 个 tag 的做法应该还是能做的，但是修改很麻烦，我一个 pushdown 能写几十行。

区间逆序对的数量由 $(1,0),(2,0),(2,1)$ 这样数对的数量决定。

维护序列，那就用线段树。

想一下如何合并左右子树信息（就是怎么让左右子树信息可以相加得到当前信息）。

显然是左右子树区间各自的逆序对数，以及左右子树区间之间形成的逆序对数相加。（也就说明了和左右子树区间原本的答案，以及左右区间各自的每个数出现的次数有关）

所以：

对于每一个节点，用 $g_{i,j}$ 维护它对应的区间的逆序对数（相当于记录自己原本的答案，合并到父节点时要用到），具体是：有多少个数值 $i$ 在数值 $j$ 前面。

同时每个节点都还要维护一个 $cnt$ 数组，代表它对应的区间每个值出现次数，方便合并信息。

左右子树合并信息时，用各自的 $g$ 数组和 $cnt$ 数组就能快速（常数时间）得到结果了。现在

那修改操作怎么办？

每个节点维护一个数组 $turn$ 代表这个节点对应的区间每个数应该以什么形式转换。（相当于对于子树的 lazy_tag）

进行修改时，就在标记下方的时候，按照常规操作，把子树的 lazy_tag 加上当前的 lazy_tag，并将子树的信息按照本节点的 lazy_tag 进行转换。

查询的时候，就将查找区间内找到的几个节点记录下来，直接把对应区间记录的信息扒下来就行了，注意一个区间可以由好几个节点组成，要将这几个节点按照左右顺序合并再输出答案（合并方式就是之前所说的合并左右子树的方式，直接相加信息）
$O(n + q\log n)$

#include <bits\/stdc++.h>
using namespace std;
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
namespace Main {
	typedef long long ll;
	const int maxn=1e5+5;
	int n;
	int a[maxn];
	int q;
	struct Replace {
		int turn[3];
		void init() {
			turn[0]=0;
			turn[1]=1;
			turn[2]=2;
		}
		Replace operator +(const Replace& b) {
			Replace res;
			for(int i=0; i<3; i++) {
				res.turn[i]=b.turn[turn[i]];
			}
			return res;
		}
	};
	struct Information {
		ll g[3][3];
		ll cnt[3];
		Information() {
			memset(g,0,sizeof g);
			memset(cnt,0,sizeof cnt);
		}
		Information operator +(const Information& b) {
			Information res;
			for(int i=0; i<3; i++)res.cnt[i]=cnt[i]+b.cnt[i];
			for(int i=0; i<3; i++) {
				for(int j=0; j<3; j++) {
					res.g[i][j]=g[i][j]+b.g[i][j];
					res.g[i][j]+=cnt[i]*b.cnt[j];
				}
			}
			return res;
		}
		ll sum()
		{
			ll res=0;
			for(int i=0;i<3;i++)
			{
				for(int j=0;j<i;j++)
				{
					res+=g[i][j];
				}
			}
			return res;
		}
	};
	Information Modify(Information information,Replace replace) {
		Information res;
		for(int i=0; i<3; i++) {
			res.cnt[replace.turn[i]]+=information.cnt[i];
		}
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				res.g[replace.turn[i]][replace.turn[j]]+=information.g[i][j];
			}
		}
		return res;
	}
	struct Tree {
		Information information;
		Replace replace_tag;
		int l,r;
	} tree[maxn<<2];
	void pushup(int i)
	{
		tree[i].information=tree[ls(i)].information+tree[rs(i)].information;
	}
	void pushdown(int i)
	{
		tree[ls(i)].replace_tag=tree[ls(i)].replace_tag+tree[i].replace_tag;
		tree[ls(i)].information=Modify(tree[ls(i)].information,tree[i].replace_tag);
		tree[rs(i)].replace_tag=tree[rs(i)].replace_tag+tree[i].replace_tag;
		tree[rs(i)].information=Modify(tree[rs(i)].information,tree[i].replace_tag);
		tree[i].replace_tag.init();
	}
	void build(int i,int l,int r)
	{
		tree[i].l=l;
		tree[i].r=r;
		tree[i].replace_tag.init();
		if(l==r)
		{
			tree[i].information.cnt[a[l]]=1;
			return;
		}
		int mid=l+r>>1;
		build(ls(i),l,mid);
		build(rs(i),mid+1,r);
		pushup(i);
	}
	
	void change(int i,int l,int r,Replace replace)
	{
		if(tree[i].l>=l&&tree[i].r<=r)
		{
			tree[i].replace_tag=tree[i].replace_tag+replace;
			tree[i].information=Modify(tree[i].information,replace);
			return;
		}
		if(tree[i].r<l||tree[i].l>r)return;
		pushdown(i);
		int mid=tree[i].l+tree[i].r>>1;
		if(mid>=l)change(ls(i),l,r,replace);
		if(mid<r)change(rs(i),l,r,replace);
		pushup(i);
	}
	Information query(int i,int l,int r)
	{
		if(tree[i].l>=l&&tree[i].r<=r)
		{
			return tree[i].information;
		}
		pushdown(i);
		int mid=tree[i].l+tree[i].r>>1;
		Information ans;
		if(mid>=l)ans=ans+query(ls(i),l,r);
		if(mid<r)ans=ans+query(rs(i),l,r);
		return ans;
	}
	void main() {
		scanf("%d%d",&n,&q);
		for(int i=1; i<=n; i++) {
			scanf("%d",&a[i]);
		}
		build(1,1,n);
		int op,l,r,s,t,u;
		while(q--) {
			scanf("%d",&op);
			if(op==1)
			{
				scanf("%d%d",&l,&r);
				printf("%lld\n",query(1,l,r).sum());
			}
			if(op==2)
			{
				scanf("%d%d%d%d%d",&l,&r,&s,&t,&u);
				Replace rep;
				rep.turn[0]=s;
				rep.turn[1]=t;
				rep.turn[2]=u;
				change(1,l,r,rep);
			}
		}
	}
}
int main() {
	Main::main();
	return 0;
}  

我再说一下这道题的分块做法。

我的做法是，整块打 lazytag 进行修改，散块暴力修改，同时维护区间答案。

查询时整块直接查询区间答案加上lazytag，散块暴力（也要加上所在块的 lazytag），同时将查询到的信息合并。

来说一下细节：

1. 对整块修改时，将区间的 lazytag 根据 $S,T,U$ 进行转换。
2. 对散块修改时，暴力修改元素的时候，不仅还要算上本次修改的，还要算上本区间之前的 lazytag（如果这个区间还有 tag，那说明之前没修改完）。另外由于本次修改时已经算上了之前的 lazytag，还要将对应区间的 lazytag 去掉，防止当前修改的这些元素被重复修改。但是这个区间有的元素之前被打了修改标记，但是当前并没有完成修改，直接去掉区间 lazytag 会导致漏修改这些元素，所以还要把那些 lazytag 被去掉但是之前的修改没有被应用的元素，在 lazytag 去掉之前完成修改（显然这个修改就要根据本区间原来已有的tag，而不包括本次修改加上的 tag了）。

总结一句话，细节超多。
$O(n+q \sqrt n)$

#include <bits\/stdc++.h>
using namespace std;
namespace Main {
	typedef long long ll;
	const int maxn=1e5+5;
	int n;
	int a[maxn];
	int q;
	struct Replace {
		int turn[3];
		void init() {
			turn[0]=0;
			turn[1]=1;
			turn[2]=2;
		}
		Replace operator +(const Replace& b) {
			Replace res;
			for(int i=0; i<3; i++) {
				res.turn[i]=b.turn[turn[i]];
			}
			return res;
		}
	};
	struct Information {
		ll g[3][3];
		ll cnt[3];
		Information() {
			memset(g,0,sizeof g);
			memset(cnt,0,sizeof cnt);
		}
		Information operator +(const Information& b) {
			Information res;
			for(int i=0; i<3; i++)res.cnt[i]=cnt[i]+b.cnt[i];
			for(int i=0; i<3; i++) {
				for(int j=0; j<3; j++) {
					res.g[i][j]=g[i][j]+b.g[i][j];
					res.g[i][j]+=cnt[i]*b.cnt[j];
				}
			}
			return res;
		}
		ll sum()
		{
			ll res=0;
			for(int i=0;i<3;i++)
			{
				for(int j=0;j<i;j++)
				{
					res+=g[i][j];
				}
			}
			return res;
		}
	};
	Information Modify(Information information,Replace replace) {
		Information res;
		for(int i=0; i<3; i++) {
			res.cnt[replace.turn[i]]+=information.cnt[i];
		}
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				res.g[replace.turn[i]][replace.turn[j]]+=information.g[i][j];
			}
		}
		return res;
	}
	int blocks,len;
	int id[maxn];
	Information lazy[maxn];\/\/记录块整体信息 
	Replace lazyrep[maxn];
	Information val[maxn];\/\/单个元素信息 
	int L[maxn],R[maxn];\/\/每个块的左右端点 
	ll query(int l,int r)
	{
		Information res;
		if(id[l]==id[r])
		{
			for(int i=l;i<=r;i++)
			{
				res=res+Modify(val[i],lazyrep[id[l]]);
			}
			return res.sum();
		}
		if(id[l]!=id[r])
		{
			for(int i=l;i<=R[id[l]];i++)
			{
				res=res+Modify(val[i],lazyrep[id[l]]);
			}
			for(int i=id[l]+1;i!=id[r];i++)
			{
				res=res+Modify(lazy[i],lazyrep[i]);
			}
			for(int i=L[id[r]];i<=r;i++)
			{
				res=res+Modify(val[i],lazyrep[id[r]]);
			}
			return res.sum();
		}
	}
	void change(int l,int r,Replace replace)
	{
		if(id[l]==id[r])
		{
			for(int i=l;i<=r;i++)
			{
				val[i]=Modify(val[i],lazyrep[id[l]]+replace);
			}
			Information tmp;
			for(int i=L[id[l]];i<=R[id[l]];i++)
			{
				if(i<l||i>r)
				    val[i]=Modify(val[i],lazyrep[id[l]]);
				tmp=tmp+val[i];
			}
			lazy[id[l]]=tmp;
			lazyrep[id[l]].init();
		}
		if(id[l]!=id[r])
		{
			for(int i=l;i<=R[id[l]];i++)
			{
				val[i]=Modify(val[i],lazyrep[id[l]]+replace);
			}
			Information tmp;
			for(int i=L[id[l]];i<=R[id[l]];i++)
			{
				if(i<l)
				    val[i]=Modify(val[i],lazyrep[id[l]]);
				tmp=tmp+val[i];
			}
			lazy[id[l]]=tmp;
			lazyrep[id[l]].init();
			for(int i=id[l]+1;i!=id[r];i++)
			{
				lazyrep[i]=lazyrep[i]+replace;
			}
			for(int i=L[id[r]];i<=r;i++)
			{
				val[i]=Modify(val[i],lazyrep[id[r]]+replace);
			}
			Information tmp2;
			for(int i=L[id[r]];i<=R[id[r]];i++)
			{
				if(i>r)
				    val[i]=Modify(val[i],lazyrep[id[r]]);
				tmp2=tmp2+val[i];
			}
			lazy[id[r]]=tmp2;
			lazyrep[id[r]].init();
		}
	}
	void main() {
		scanf("%d%d",&n,&q);
		len=sqrt(n);
		for(int i=1; i<=n; i++) {
			scanf("%d",&a[i]);
			val[i].cnt[a[i]]++;
			id[i]=(i-1)\/len+1;
			lazy[id[i]]=lazy[id[i]]+val[i];
		}
\/\/		printf("sum: %lld\n",lazy[1].sum());
		for(int i=1;i<=n;i++)
		{
			if(id[i]!=id[i-1])
			{
				L[id[i]]=i;
			}
			if(id[i]!=id[i+1])
			{
				R[id[i]]=i;
			}
			lazyrep[id[i]].init();
		}
		int op,l,r,s,t,u;
		while(q--) {
			scanf("%d",&op);
			if(op==1)
			{
				scanf("%d%d",&l,&r);
				printf("%lld\n",query(l,r));
			}
			if(op==2)
			{
				scanf("%d%d%d%d%d",&l,&r,&s,&t,&u);
				Replace rep;
				rep.turn[0]=s;
				rep.turn[1]=t;
				rep.turn[2]=u;
				change(l,r,rep);
			}
		}
	}
}
int main() {
	Main::main();
	return 0;
}  

Ex

在想

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-08-30 20:08:39

做法

分类讨论。

经简单计算得知，$1,5,7$ 可以随意交换，也就是说插在哪里都可以，所以先忽略它们的存在。

剩下的数 $2,3,4,6,8,9$ 中，$6$ 不能与其他任何数交换，也就是说 $6$ 的位置是固定的，相当于把序列分成了好几段。

再剩下的数 $2,3,4,8,9$ 中，$2,4,8$ 这三个数不能互相交换，$3,9$ 不能互相交换，这样分成了两类，每一类的内部不能互相交换，位置是相对固定的。

所以，本题的做法：

1. 先忽略 $1,5,7$ 的存在，并用 $6$ 将数列分成一些段。
2. 对于每一段，设 $x,y$ 分别代表第一，二类的元素数量，由于每一类的内部相对位置是固定的，所以答案就是在总共 $x+y$ 个元素中选出 $x$ 个元素作为第一类元素的位置（当然换成选 $y$ 个作为第二类元素的位置也是可以的），答案就是 $C_{x+y}^x$。
3. 求出每一段的答案后，拼起来。
4. 然后考虑将 $1,5,7$ 插入的方案数，直接算就行，这个答案就很显然了。

Code

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const ll mod=998244353;
	const int maxn=1e5+5;
	inline int read()
	{
		int x=0;
		char ch=getchar();
		while(isdigit(ch))
		{
			x=(x<<1)+(x<<3)+(ch^48);
			ch=getchar();
		}
		return x;
	}
	int n;
	int a[maxn];
	int _c1,_c5,_c7;
	int _cla1,_cla2; 
	ll fact[maxn];
	ll ksm(ll a,ll b)
	{
		ll ret=1;
		while(b)
		{
			if(b&1)ret=ret*a%mod;
			a=a*a%mod;
			b>>=1;
		}
		return ret;
	}
	ll inv(ll a)
	{
		return ksm(a,mod-2);
	}
	inline ll C(int n,int m)
	{
		if(m>n)return 0;
		return fact[n]*inv(fact[m])%mod*inv(fact[n-m])%mod;
	}
	void main()
	{
		n=read();
		for(int i=1;i<=n;i++)
		{
			a[i]=read();
			_c1+=(a[i]==1);
			_c5+=(a[i]==5);
			_c7+=(a[i]==7);
		}
		fact[0]=1;
		for(int i=1;i<=n;i++)
		{
			fact[i]=fact[i-1]*i%mod;
		}
		int l=1;
		ll ans=1;
		for(int i=1;i<=n;i++)
		{
			if(a[i]==2||a[i]==4||a[i]==8)_cla1++;
			if(a[i]==3||a[i]==9)_cla2++;
			if(a[i]==6)
			{
                ans*=C(_cla1+_cla2,_cla1);
                ans%=mod;
                _cla1=_cla2=0;
			}
		}
		if(_cla1||_cla2)
		{
			ans*=C(_cla1+_cla2,_cla1);
 			ans%=mod;
		}
		ans=ans*C(n,_c1)%mod*C(n-_c1,_c5)%mod*C(n-_c1-_c5,_c7)%mod;
		printf("%lld",ans);
	}
}
int main()
{
	Main::main();
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-08-31 23:19:36

做法

dfs 每个点作为根，计算答案。

dfs 时，设当前点是 $u$，转移到其子节点 $v$ 时，考虑一下答案变化：

以 $v$ 为根节点的子树所有节点深度减一。

所有不在 $v$ 的子树的节点深度加一。

所以预处理每个节点子树的大小，然后 dfs 转移就行。

Code

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
int n;
int head[maxn];
struct EDGE
{
	int to,nxt;
}edge[maxn<<1];
int cnt;
inline void add(int u,int to)
{
	edge[++cnt].to=to;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
int size[maxn];
void dfs(int u,int _fa)
{
	size[u]++;
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int to=edge[i].to;
		if(to==_fa)continue;
		dfs(to,u);
		size[u]+=size[to];
	}
}
ll f[maxn];
void redfs(int u,int _fa)
{
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int to=edge[i].to;
		if(to==_fa)continue;
		f[to]=f[u]+ll(n-2*size[to]);
		redfs(to,u);
	}
}
int main()
{
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
	{
		f[1]+=(ll)size[i];
	}
	redfs(1,0);
	ll ans=0;
	int out=1;
	for(int i=1;i<=n;i++)
	{
		if(f[i]>ans)
		{
			ans=f[i];
			out=i;
		}
	}
	printf("%d",out);
	return 0;
}  

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-06 17:12:12

考前半个月

被迫停止 OI，整 whk

Day1

看了看考场，初一七班，我的座位.......刚好吹不到风扇，刚好看不到时间，刚好有个窗帘在我考试的桌子上摇摆.............没办法只能每隔半个小时（估摸着）问一下老师时间，寄

先考的语蚊。
看了一下卷，和之前一样，还是相同的题型，我知道我语蚊很菜，所以就死死按住作文题，防止看到之后感觉不会写心态炸裂
花了 0.5h 干完了填空，鲁滨逊漂流记有个细节忘了，寄。
又用了 0.5h 做完阅读题。看时间还充足，静下心来思考作文题
一看，以 "在火星上捡到一块钱" 为开头，题目自拟，600字，tnnd 限制了开头还怎么写！想了一会，发现之前好像看过类似的东西，然后就有了思路..........还剩 35min，拿起笔狂写，看着 600 字逐渐接近，我继续加快速度，继续扩大内容，但是，我忘了一件事。很快，我的字数就超过了 800 字，我还打算再写几百字，但是我忘了要结尾！，一分钟后，老师："还剩 5 分钟结束，请检查名字是否写完整.........."，而我作文离结尾还远着，人当场傻掉，用 50 字草草结尾，然后惨惨离场
寄

课间对了下答案，第一个选择题就 WA 了，寄

第二场政治
花了 30min，写完了选择题。
然后看时间不多了慌的一批，我只好给题目按分值排了个序，先干分值高的。
然后 12 分的题能让我答 15 条
我用了尽快的速度答完 8 分以上的题，然后用了几分钟切了 4 分的题。
写完之后，刚刚想喘口气，还没等我喘气就打铃了............
侥幸没有 TLE

第三个考英语，这次不考听力，乘三分之四（对我来说不是啥好事，寄）（rp 都让四天前的模拟考试耗光了）
没啥好说的，比较匀速的做完了整张卷之后，不怎么紧张

然后考生物
没啥好说，感觉发挥比较好

Day2

这次我带表了
先考的数学。
我之前说过我的目标是 120，因为我想当数学课代表，而不是整天一堆事的组长（关键是只要组平均分低了我第一个寄掉）

没遇到什么难题，匀速得做完了除了最后一道大题得最后一问。
此时我看这最后一问不需要证明，而且只剩 10min了。我就想了一下是该放弃这道题，蒙一个结论上去，检查之前的题，还是攻下这道题，不检查之前的题。
最后还是决定检查，事后证明这是个错误的决定，因为并没有检查出错，但是我这唯一一道蒙的题，蒙 错 了（应该是 2 到 3 分）
寄 课间和同学对了下答案，我的同学有道大题正负号写反了，在此默哀 3 秒钟（其余的题答案一样，包括我蒙的那道题）
又和数学巨佬 ljc 对了一下蒙的那道题，不一样，说明我错了（然而他第一道选择题错了，3分）

后面的历史，地理，没啥好说，略

UPD:

数学地理双 2nd，语文政治 40th 以外。

总结一句话：除了语文政治其他五科都在前几名，语文政治寄了。

7 科综合排名：10th(上次) $\rightarrow$ 7th(这次)
还是个蒟蒻

UPD2:

记录一下期末考试结束之后职位竞选的过程。

前 $30$ 名参加。

一个人只能竞选一种职位。

我以为像往常一样，课代表是固定的，每科前三名当，不需要竞选。

然后我就想着，我的数学地理都是前三，生物也应该是前几名，只要我什么都不竞选，那就稳稳数学课代表，就算不能当数学课代表也能当地理课代表。

然后，我什么职位都没填就把职位竞选表交了上去。

上面写着 没有能力，不参与竞选

很快，其他职位竞选结束，开始安排课代表。

老师这时对我说：那你课代表总有能力吧

我以为终于能当上数学课代表了，就赶紧说：这个有能力

然后老师就让我当了 yw 课代表。

还没等我说什么就：请坐

人傻了

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-09 23:04:15

题外话

赛时因为 B 题被卡了半天才 AC，导致本来会的 D 题没时间做了，最终比赛失败（用小号打的，没有掉 rating）
总结一句话：没先去做 D，$\color{red}\text{血亏}$

A

模拟

注意：

鬼子出生的时候身高可能不是 1cm，而是 $t - xd$，在 $t \ge xd$ 的时候

B

给定一个点，坐标为 $(a,b)$，以及一个角度 $d(0 \le d \le 360)$。求这个点绕原点旋转 $d$ 度之后新的坐标。
$a_1 = a \cdot \cos(d) - b \cdot \sin(d)$
$b_1 = b \cdot \cos(d) + a \cdot \sin(d)$
注意 cmath 库中的 cos，sin 函数的参数是弧度制的，要将 $d$ 转换成对应的弧度

C

还没做

D

总体思路

将所有相交的圆连边，然后从起始圆（$(sx,sy)$ 所在的圆）出发爆搜，如果能到达终点圆（$(tx,ty)$ 所在的圆），那么就是 Yes，否则 No

细节

• 如何判断两圆是否相交？
  设 $(x_1,y_1)$ 为第一个圆的圆心坐标，$(x_2,y_2)$ 为第二个圆的圆心坐标，设 $d$ 为两个圆的圆心之间的距离，设 $r_1,r_2(r_2 \ge r_1)$ 分别为两个圆的半径。
  若 $r_2- r_1 \le d \le r_2+r_1$，那么两个圆相交
• 如何避免精度问题
  计算距离的时候，可以将等式两边分别平方，这样就避免了开根。

Code

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const int maxn=3005;
    vector<int> imap[maxn];
    ll dis2(ll x1,ll y1,ll x2,ll y2)
    {
        return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
    }
    bool islb(ll x1,ll y1,ll r1,ll x2,ll y2,ll r2)
    {
        ll d=dis2(x1,y1,x2,y2);
        if(r2<r1)swap(r2,r1);
        if((r2-r1)*(r2-r1)<=d&&d<=(r2+r1)*(r2+r1))return 1;
        return 0;
    }
    int n;
    struct Circle
    {
        ll x,y,r;
    }cir[maxn];
    bool vis[maxn];
    int sta,en;
    bool dfs(int u)
    {
        if(vis[u])return 0;
        vis[u]=1;
        if(u==en)
        {
            return 1;
        }
        for(int i=0;i<imap[u].size();i++)
        {
            int to=imap[u][i];
            if(dfs(to))
            {
                return 1;
            }
        }
        return 0;
    }
    void main()
    {
        cin>>n;
        ll sx,sy,tx,ty;
        cin>>sx>>sy>>tx>>ty;
        for(int i=1;i<=n;i++)
        {
            cin>>cir[i].x>>cir[i].y>>cir[i].r;
            ll diss=dis2(cir[i].x,cir[i].y,sx,sy);
            if(diss==cir[i].r*cir[i].r)
            {
                sta=i;
            }
            diss=dis2(cir[i].x,cir[i].y,tx,ty);
            if(diss==cir[i].r*cir[i].r)
            {
                en=i;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(islb(cir[i].x,cir[i].y,cir[i].r,cir[j].x,cir[j].y,cir[j].r))
                {
                    imap[i].emplace_back(j);
                    imap[j].emplace_back(i);
                }
            }
        }
        if(dfs(sta))
        {
            printf("Yes");
        }
        else printf("No");
    }
}
int main()
{
    Main::main();
    return 0;
}