T1：random

我又来白剽博客了：

详细证明请看土哥

土哥写的不是很详细，我在这里详细写一下：

首先，对于f[n]的式子：

加一是那一个对的贡献，大C是选其余的几个数，\(2^{N}\)是总的子集个数。

逆序对的期望个数是：

首先，所有数字两两匹配，共有\(n*(n-1)\)对，，然后，某个对成为逆序对的的概率是50%，所以变成了四分之。

上代码：

#include<bits/stdc++.h>

using namespace std;

namespace STD

{

	#define rr register

	#define inf INT_MAX

	typedef long long ll;

	const ll mod=998244353;

	ll n;

	ll read()

	{

		rr ll x_read=0,y_read=1;

		rr char c_read=getchar();

		while(c_read<'0'||c_read>'9')

		{

			if(c_read=='-') y_read=-1;

			c_read=getchar();

		}

		while(c_read<='9'&&c_read>='0')

		{

			x_read=(x_read<<3)+(x_read<<1)+(c_read^48);

			c_read=getchar();

		}

		return x_read*y_read;

	}

	ll qpow(ll base,ll exp)

	{

		ll ret=1ll;

		while(exp)

		{

			if(exp&1) ret=ret*base%mod;

			base=1ll*base*base%mod;

			exp>>=1;

		}

		return ret;

	}

};

using namespace STD;

int main()

{

	n=read();

	ll inv=qpow(9,mod-2);

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

	{

		ll x=read()%mod;

		cout<<(x*x%mod-1+mod)*inv%mod<<'\n';

	}

}

T2:string

气死，这题我改了一整天，结果发现是二分与Hash表的指针打错了，气死。

这题的思路是Hash+Trie。

手写Hash，快的一批。

注意后缀要倒着插，前缀要正着插。

代码：

#include<bits/stdc++.h>

using namespace std;

namespace STD

{

	#define rr register

	#define inf INT_MAX

	#define scanf ybbb=scanf

	typedef long long ll;

	typedef unsigned long long ull;

	const int N=1e5+4;

	const int LEN=2e5+4;

	const ull base=131;

	int m,ybbb;

	int pre[N],suc[N];

	char s[N]="";

	ull mi[N],has[N],rehas[N];

	struct node

	{

		node * nxt;

		ull key;

		int sum;

		node()

		{

			key=sum=0;

			nxt=NULL;

		}

		node(ull key_,int sum_)

		{

			key=key_,sum=sum_;

			nxt=NULL;

		}

	};

	class Hash

	{

		private:

			node * head[LEN];

		public:

			void insert(ull,int);

			node * find(ull);

	}h[2];

	void Hash::insert(ull key,int sum)

	{

		ull x=key%(LEN-4);

		if(head[x]==NULL)

		{

			head[x]=new node(key,sum);

			return ;

		}

		node * temp=head[x];

		node * pre=NULL;

		while(temp!=NULL&&(temp->key!=key))

		{

			pre=temp;

			temp=temp->nxt;

		}

		if(temp==NULL)

		{

			temp=new node(key,sum);

			if(pre!=NULL)

				pre->nxt=temp;

			return;

		}

		temp->sum=sum;

	}

	node * Hash::find(ull key)

	{

		ull x=key%(LEN-4);

		node * temp=head[x];

		while(temp!=NULL&&temp->key!=key)

			temp=temp->nxt;

		return temp;

	}

	class Trie

	{

		private:

			int tot;

			int ch[LEN][28];

			int cnt[LEN];

		public:

			int sp;

			Trie(){tot=1;}

			void insert(char*,char*);

			void get(int,ull);

	}t[2];

	void Trie::insert(char * st,char * en)

	{

		int p=1;

		if(st>=en)

		{

			for(rr char * i=st;i>=en;i--)

			{

				int x=(*i)-'a'+1;

				if(ch[p][x]==0) ch[p][x]=++tot;

				p=ch[p][x];

				cnt[p]++;

			}

		}

		else

		{

			for(rr char * i=st;i<=en;i++)

			{

				int x=(*i)-'a'+1;

				if(ch[p][x]==0) ch[p][x]=++tot;

				p=ch[p][x];

				cnt[p]++;

			}

		}

	}

	void Trie::get(int id,ull has)

	{

		for(rr int i=1;i<=26;i++)

		{

			if(ch[id][i])

			{

				cnt[ch[id][i]]+=cnt[id];

				h[sp].insert(has*base+i,cnt[ch[id][i]]);

				get(ch[id][i],has*base+i);

			}

		}

	}

	int read()

	{

		rr int x_read=0,y_read=1;

		rr char c_read=getchar();

		while(c_read<'0'||c_read>'9')

		{

			if(c_read=='-') y_read=-1;

			c_read=getchar();

		}

		while(c_read<='9'&&c_read>='0')

		{

			x_read=(x_read<<3)+(x_read<<1)+(c_read^48);

			c_read=getchar();

		}

		return x_read*y_read;

	}

	void Pre()

	{

		mi[0]=1;

		for(rr int i=1;i<=N-2;i++)

			mi[i]=mi[i-1]*base;

	}

	inline ull substr(int l,int r){return has[r]-has[l-1]*mi[r-l+1];}

	inline ull resubstr(int l,int r){return rehas[l]-rehas[r+1]*mi[r-l+1];}

};

using namespace STD;

int main()

{

	Pre();

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

	m=read();

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

	{

		char a[N]="";

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

		int len=strlen(a+1);

		t[0].insert(a+1,a+len);

		t[1].insert(a+len,a+1);

	}

	t[0].sp=0,t[1].sp=1;

	t[0].get(1,0),t[1].get(1,0);

	int len=strlen(s+1);

	for(rr int i=1;i<=len;i++)

		has[i]=has[i-1]*base+s[i]-'a'+1;

	for(rr int i=len;i>=1;i--)

		rehas[i]=rehas[i+1]*base+s[i]-'a'+1;

	//suc

	for(rr int i=1;i<=len;i++)

	{

		int l=1,r=i;

		while(l<r)

		{

			int mid=(l+r)>>1;

			ull x=resubstr(mid,i);

			node * temp=h[1].find(x);

			if(temp==NULL) l=mid+1;

			else r=mid;

		}

		ull x=resubstr(l,i);

		node * temp=h[1].find(x);

		if(temp!=NULL)

			suc[i]=temp->sum;

	}

	//pre

	for(rr int i=len;i>=1;i--)

	{

		int l=i,r=len;

		while(l<r)

		{

			int mid=(l+r+1)>>1;

			ull x=substr(i,mid);

			node * temp=h[0].find(x);

			if(temp==NULL) r=mid-1;

			else l=mid;

		}

		ull x=substr(i,l);

		node * temp=h[0].find(x);

		if(temp!=NULL)

			pre[i]=temp->sum;

	}

	ll ans=0;

	for(rr int i=1;i<len;i++)

		ans+=1ll*suc[i]*pre[i+1];

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

}

T3:queen

emmmm。。。。官方题解已经很详细了，就不写了，但是土哥给了两个优化，还是很香的。

一个是对于\(\sum_{i=0}^{n}\)\(C^{m}_{i}\)=\(C^{m+1}_{n+1}\)的优化（证明是杨辉三角裂项)。

另一个是\(\sum_{i=1}^{n}\)\(i^{2}\)=\(n*(n+1)*(2*n+1)/6\)。

真的棒极了。

巴特西

NOIP模拟「random·string·queen」

T1：random

T2:string

T3:queen

最新文章

热门文章