A.次芝麻

因为$n+m$始终为定值，所以可以发现每次操作相当与对$n$或$m$任意一个数在模$n+m$意义下$\times 2$，直接上快速幂。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n,m,K;

ll qpow(ll a,ll b,ll mod)

{

	ll res=1;

	while(b)

	{

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

		a=a*a%mod;

		b>>=1;

	}

	return res;

}

int main()

{

	scanf("%lld%lld%lld",&n,&m,&K);

	ll tot=n+m;

	ll ans=n*qpow(2,K,n+m)%(n+m);

	cout<<min(ans,tot-ans)<<endl;

	return 0;

}

B.喝喝喝

$a\% b=K$-->$a-K=x\times b$

记录每一个数第一次出现的位置，对于每个$a[i]$枚举它的约数就可以更新坏对右端点，利用端点距离统计答案即可。注意特判。

#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

int read()

{

	int x=0,f=1;char ch=getchar();

	if(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0',ch=getchar();}

	return x*f;

}

const int N=1e5+5;

int a[N],n,K,b[N];

int main()

{

	n=read();K=read();

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

		a[i]=read();

	ll ans=0;int maxx=0;

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

	{

		int pos=K>=a[i]?0:max(b[0],b[a[i]]);

		maxx=max(maxx,pos);

		ans+=i-maxx;

		if(a[i]<K)continue;

		int val=a[i]-K;

		if(!val)

		{

			b[0]=i;

			continue;

		}

		int sqt=sqrt(val);

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

			if(val%j==0)b[j]=b[val/j]=i;

	}

	cout<<ans<<endl;

	return 0;

}

C.长寿花

怎么这几天的T3都是不可做dp啊？

考虑每一层具体选哪些颜色显然是没有用的，所以直接设$f[i][j]$为第i层用j种颜色的方案数，发现只用组合数转移比较困难。再定义$g[i][j]$为i个位置放j种颜色，保证相邻位置颜色不同的方案数；也就是把i个元素放到j个集合里，且相邻两个元素不在同一集合的方案数。

可以递推求出$g[]$。对于$g[i][j]$来说，应当有两个转移来源：一是之前有i-1个元素，j个集合，这个新元素不创建新的集合，但也不能和之前那个的集合相同；二是之前有i-1个元素，j-1个集合，且这个新元素创建了一个新集合。

所以递推式为$g[i][j]=g[i-1][j]*(j-1)+g[i-1][j-1]*j$

关于系数：第一种情况新加的元素只能从它上一个元素所属的集合之外选集合，所以有$j-1$种；第二种情况的新元素有着船新的颜色，所以它的位置不受约束，可以有$j-1+1=j$种情况。

有了$g[]$，我们再统计一下$sum[i]=\sum f[i][j]$，$f[]$的转移也就十分简单了：$f[i][j]=sum[i-1] \times g[i][j] \times C_m^j -f[i-1][j] \times g[i][j]$

还有一件事QAQ，这里的模数不一定是质数，所以需要$exLucas$或者分解质因数。注意分解质因数维护质因子的桶时也要递推维护，不然复杂度就假了。当然统计答案爆扫就行。

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

const int N=1e6+5;

int read()

{

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

int n,m,p;

int a[N];

ll g[5005][5005],C[5005],f[2][5005],sum[N];

int pr[N],vis[N],res[N],tot,bu[N];

void getprime()

{

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

	{

		if(!vis[i])pr[++tot]=i,res[i]=tot;

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

		{

			if(i*pr[j]>m)break;

			vis[i*pr[j]]=1,res[i*pr[j]]=j;

			if(i%pr[j]==0)break;

		}

	}

}

void dv(int x,int val)

{

	while(x!=1)bu[res[x]]+=val,x/=pr[res[x]];

}

void getC()

{

	dv(m,1);

	C[1]=C[0]=1;

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

		if(bu[i])

			for(int j=1;j<=bu[i];j++)

				(C[1]*=pr[i])%=p;

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

	{

		if(i>m)break;

		dv(m-i+1,1);dv(i,-1);

		C[i]=1;

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

			if(bu[j])

				for(int k=1;k<=bu[j];k++)

					(C[i]*=pr[j])%=p;

	}

}

int main()

{

	n=read();m=read();p=read();

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

		a[i]=read();

	getprime();

	g[1][1]=1;

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

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

			g[i][j]=(1LL*g[i-1][j]*(j-1)%p+g[i-1][j-1]*j%p)%p;

	getC();

	int now=1,pre=0;

	for(int i=1;i<=a[1];i++)

		f[now][i]=g[a[1]][i]*C[i]%p,(sum[1]+=f[now][i])%=p;

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

	{

		now^=1;pre^=1;

		memset(f[now],0,sizeof(f[now]));

		for(int j=1;j<=m&&j<=a[i];j++)

		{

			f[now][j]=sum[i-1]*g[a[i]][j]%p*C[j]%p;

			f[now][j]-=f[pre][j]*g[a[i]][j]%p;

			while(f[now][j]<0)f[now][j]+=p;

			(sum[i]+=f[now][j])%=p;

		}

	}

	cout<<sum[n]<<endl;

	return 0;

}

巴特西

[NOIP模拟测试34]反思+题解

$Solutions:$

A.次芝麻

B.喝喝喝

C.长寿花

最新文章

热门文章