Codeforces Round #539 Div. 1

2024-01-31 11:48:10

　　A：即求长度为偶数的异或和为0的区间个数，对前缀异或和用桶记录即可。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 300010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,a[N],cnt[1<<20][2];
ll ans;
signed main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	const char LL[]="%I64d\n";
#endif
	n=read();
	for (int i=1;i<=n;i++) a[i]=a[i-1]^read();
	cnt[0][0]=1;
	for (int i=1;i<=n;i++)
	{
		ans=ans+cnt[a[i]][i&1];
		cnt[a[i]][i&1]++;
	}
	cout<<ans;
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　B：显然如果有解，答案一定不大于2，因为原串是回文串，找到第一个不是回文串的前缀和对其对应后缀切掉并交换即可。无解直接判断是否字母都相同或只有最中间字母不同。然后只需要check是否为1，暴力枚举切割点暴力判断即可。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 5010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n;
char s[N],a[N];
signed main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	const char LL[]="%I64d\n";
#endif
	scanf("%s",s+1);n=strlen(s+1);
	if (n==1) {cout<<"Impossible";return 0;}
	bool flag=1;
	for (int i=2;i<=n;i++) if (s[i]!=s[1]) {flag=0;break;}
	if (flag) {cout<<"Impossible";return 0;}
	if (n&1)
	{
		bool flag=1;
		for (int i=2;i<=n;i++) if (s[i]!=s[1]&&i!=(n+1)/2) {flag=0;break;}
		if (flag) {cout<<"Impossible";return 0;}
	}
	for (int i=1;i<n;i++)
	{
		for (int j=1;j<=n-i;j++) a[j]=s[j+i];
		for (int j=n-i+1;j<=n;j++) a[j]=s[j-(n-i)];
		bool flag=1;
		for (int j=1;j<=n;j++) if (a[j]!=a[n-j+1]) {flag=0;break;}
		if (!flag) continue;
		for (int j=1;j<=n;j++) if (a[j]!=s[j]) {cout<<1;return 0;}
	}
	cout<<2;
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　D：显然枚举两点路径上有多少个点，选出这些点并排列，给路径上每条边插板分配权值，剩余边权值任意取。只剩下一个问题，就是如何计算固定这条路径后，树的形态个数。考虑将这条边缩点，一条边连接某两个点的方案数是1，而连接某个点和这条链的方案数则是其链长。将链长作为这个点的权值，其余点权值为1，于是我们要统计的东西相当于缩点后每棵树的所有点权值度数之积的和。注意到出现了度数，考虑prufer序列。序列中每个点出现次数=其度数+1，并且由于要统计所有树，每种对应的prufer序列都存在。这样由分配律可得方案数即为(i+1)*nn-2-i，其中i为路径上点的个数。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 1000010
#define P 1000000007
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,m,a,b,fac[N],inv[N],ans;
int ksm(int a,int k)
{
	int s=1;
	for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;
	return s;
}
int C(int n,int m){if (m>n) return 0;return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;}
signed main()
{
#ifndef ONLINE_JUDGE
	freopen("d.in","r",stdin);
	freopen("d.out","w",stdout);
	const char LL[]="%I64d\n";
#endif
	n=read(),m=read();read(),read();
	fac[0]=1;for (int i=1;i<=N-10;i++) fac[i]=1ll*fac[i-1]*i%P;
	inv[0]=inv[1]=1;for (int i=2;i<=N-10;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;
	for (int i=1;i<=N-10;i++) inv[i]=1ll*inv[i-1]*inv[i]%P;
	for (int i=1;i<n;i++)
	{
		int x;if (i==n-1) x=1;else x=1ll*(i+1)*ksm(n,n-2-i)%P;
		x=1ll*x*C(m-1,i-1)%P*C(n-2,i-1)%P*ksm(m,n-i-1)%P*fac[i-1]%P;
		ans=(ans+x)%P;
	}
	cout<<ans;
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　E：傻逼题，要是先开E而不是C说不定就码完了。对模数的质因子分别记录次数即可，线段树瞎维护。质因子的次幂可以预处理一下，略卡常。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 100010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,P,a[N],q,L[N<<2],R[N<<2],ans[N<<2],p[12],u[12][2][1000010],cnt;
ll lazy[N<<2][12];
int ksm(int a,ll k)
{
	return 1ll*u[a][0][k%1000000]*u[a][1][k/1000000]%P;
}
void exgcd(int &x,int &y,int a,int b)
{
	if (b==0)
	{
		x=1,y=0;
		return;
	}
	exgcd(x,y,b,a%b);
	int t=x;x=y;y=t-a/b*x;
}
int inv(int a)
{
	int x,y;
	exgcd(x,y,a,P);
	return (x%P+P)%P; 
}
void up(int k){ans[k]=(ans[k<<1]+ans[k<<1|1])%P;}
void update(int k)
{
	ans[k]=lazy[k][0];
	for (int i=1;i<=cnt;i++) ans[k]=1ll*ans[k]*ksm(i,lazy[k][i])%P;
}
void down(int k,int i)
{
	lazy[k<<1][i]+=lazy[k][i],lazy[k<<1|1][i]+=lazy[k][i];
	ans[k<<1]=1ll*ans[k<<1]*ksm(i,lazy[k][i])%P,ans[k<<1|1]=1ll*ans[k<<1|1]*ksm(i,lazy[k][i])%P;
	lazy[k][i]=0;
}
void down(int k)
{
	lazy[k<<1][0]=1ll*lazy[k<<1][0]*lazy[k][0]%P;
	lazy[k<<1|1][0]=1ll*lazy[k<<1|1][0]*lazy[k][0]%P;
	ans[k<<1]=1ll*ans[k<<1]*lazy[k][0]%P;
	ans[k<<1|1]=1ll*ans[k<<1|1]*lazy[k][0]%P;
	lazy[k][0]=1;
	for (int i=1;i<=cnt;i++)
	down(k,i);
}
void build(int k,int l,int r)
{
	L[k]=l,R[k]=r;lazy[k][0]=1;
	if (l==r)
	{
		ans[k]=lazy[k][0]=a[l];ans[k]%=P;
		for (int i=1;i<=cnt;i++)
		while (lazy[k][0]%p[i]==0)
		lazy[k][0]/=p[i],lazy[k][i]++;
		return;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	up(k);
}
void add(int k,int l,int r,int i,int x,int u)
{
	if (L[k]==l&&R[k]==r) {ans[k]=1ll*ans[k]*u%P;lazy[k][i]+=x;return;}
	down(k,i);
	int mid=L[k]+R[k]>>1;
	if (r<=mid) add(k<<1,l,r,i,x,u);
	else if (l>mid) add(k<<1|1,l,r,i,x,u);
	else add(k<<1,l,mid,i,x,u),add(k<<1|1,mid+1,r,i,x,u);
	up(k);
}
void mul(int k,int l,int r,int x)
{
	if (L[k]==l&&R[k]==r) {ans[k]=1ll*ans[k]*x%P;lazy[k][0]=1ll*lazy[k][0]*x%P;return;}
	down(k);
	int mid=L[k]+R[k]>>1;
	if (r<=mid) mul(k<<1,l,r,x);
	else if (l>mid) mul(k<<1|1,l,r,x);
	else mul(k<<1,l,mid,x),mul(k<<1|1,mid+1,r,x);
	up(k);
}
void add(int k,int p,int i,int x)
{
	if (L[k]==R[k]) {lazy[k][i]+=x;update(k);return;}
	down(k,i);
	int mid=L[k]+R[k]>>1;
	if (p<=mid) add(k<<1,p,i,x);else add(k<<1|1,p,i,x);
	up(k);
}
void mul(int k,int p,int x)
{
	if (L[k]==R[k]) {lazy[k][0]=1ll*lazy[k][0]*x%P;update(k);return;}
	down(k);
	int mid=L[k]+R[k]>>1;
	if (p<=mid) mul(k<<1,p,x);else mul(k<<1|1,p,x);
	up(k);
}
int query(int k,int l,int r)
{
	if (L[k]==l&&R[k]==r) return ans[k];
	down(k);
	int mid=L[k]+R[k]>>1;
	if (r<=mid) return query(k<<1,l,r);
	else if (l>mid) return query(k<<1|1,l,r);
	else return (query(k<<1,l,mid)+query(k<<1|1,mid+1,r))%P;
}
signed main()
{
#ifndef ONLINE_JUDGE
	freopen("e.in","r",stdin);
	freopen("e.out","w",stdout);
	const char LL[]="%I64d\n";
#endif
	n=read(),P=read();
	int v=P;
	for (int i=2;i*i<=v;i++)
	if (v%i==0)
	{
		p[++cnt]=i;
		while (v%i==0) v/=i;
	}
	if (v>1) p[++cnt]=v;
	for (int i=1;i<=cnt;i++)
	{
		u[i][0][0]=1;
		for (int j=1;j<=1000000;j++) u[i][0][j]=1ll*u[i][0][j-1]*p[i]%P;
		u[i][1][0]=1;
		for (int j=1;j<=1000000;j++) u[i][1][j]=1ll*u[i][1][j-1]*u[i][0][1000000]%P;
	}
	for (int i=1;i<=n;i++) a[i]=read();
	build(1,1,n);
	q=read();
	while (q--)
	{
		int op=read();
		if (op==1)
		{
			int l=read(),r=read(),x=read();
			for (int i=1;i<=cnt;i++)
			{
				int t=0;
				while (x%p[i]==0) t++,x/=p[i];
				if (t) add(1,l,r,i,t,ksm(i,t));
			}
			mul(1,l,r,x);
		}
		if (op==2)
		{
			int u=read(),x=read();
			for (int i=1;i<=cnt;i++)
			{
				int t=0;
				while (x%p[i]==0) t++,x/=p[i];
				if (t) add(1,u,i,-t);
			}
			mul(1,u,inv(x));
		}
		if (op==3)
		{
			int l=read(),r=read();
			printf("%d\n",query(1,l,r));
		}
	}
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　C实在不想补。

　　result：rank 37 rating +142

上一篇：IT十年人生过客-八-银总和2011总结


下一篇：近1个月订单占比城市TOP6