前言

找大佬嫖到个号来划水打比赛了，有的题没写或者不是我写的就不放了。
目前只有：1004,1005,1007,1008,1011

正题

题目链接:https://acm.hdu.edu.cn/contests/contest_show.php?cid=990

1004 Link with Balls

题目大意

两种盒子各有$n$个，每个盒子中球的颜色不同

第一种第$i$个盒子中可以取出$ik(k\in N)$个球
第二种第$i$个盒子中可以取出不超过$i$个球

求取出$m$个球的方案数。

$1\leq T\leq 10^5,1\leq n,m\leq 10^6$

解题思路

用生成函数推导，第一种球的函数是$\frac{1-x^{i}{1-x}$，第二种球的函数是$\frac{1}{1-x}i}$，发现相乘可以抵消。最后乘出来是
$(1-x^n)(\frac{1}{1-x})^{n+1}$
然后化回来就是
$\binom{n+m}{n}-\binom{m-1}{n}$
就好了

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=2e6+10,P=1e9+7;

ll T,inv[N],fac[N],n,m;

ll C(ll n,ll m)

{return fac[n]*inv[m]%P*inv[n-m]%P;}

signed main()

{

	inv[1]=1;

	for(ll i=2;i<N;i++)inv[i]=P-inv[P%i]*(P/i)%P;

	inv[0]=fac[0]=1;

	for(ll i=1;i<N;i++)fac[i]=fac[i-1]*i%P,inv[i]=inv[i-1]*inv[i]%P;

	scanf("%lld",&T);

	while(T--){

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

		ll ans=C(m+n,n);

		m-=n+1;

		if(m>=0)ans=(ans-C(m+n,n)+P)%P;

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

	}

}

1005 Link with EQ

题目大意

$n$个格子的凳子，开始第一个同学会随机选择一个位置坐下，剩下的同学会选择随机一个距离已有同学最远的位置坐下，求没有位置的周围都没有同学时期望坐下了多少个同学。
$1\leq T\leq 10^5,1\leq n\leq 10^6$

解题思路

设$f_i$表示只有$i$个格子且边边都有同学时还能做多少个人，这个可以很容易$dp$出来。

然后主要考虑第一个人的座位，特判一下头尾两个位置然后剩下的对$f$求个前缀和就可以很快计算了。

时间复杂度$O(n+T\log P)$

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=1048576,P=1e9+7;

ll T,n,f[N],g[N],s[N];

ll power(ll x,ll b){

	ll ans=1;

	while(b){

		if(b&1)ans=ans*x%P;

		x=x*x%P;b>>=1;

	}

	return ans;

}

signed main()

{

	for(ll i=3;i<N;i++){

		ll mid=(i+1)/2;

		f[i]=f[mid-1]+f[i-mid]+1;

		s[i]=(s[i-1]+f[i]*2)%P;

	}

	for(ll i=1;i<N;i++)g[i]=f[i]+2;

	scanf("%lld",&T);

	while(T--){

		scanf("%lld",&n);

		if(n<=2){puts("1");continue;}

		if(n==3){puts("666666673");continue;}

		ll ans=(3*(n-4)+s[n-4])%P;

		(ans+=g[n-2]*2+g[n-3]*2)%=P;

		ans=ans*power(n,P-2)%P;

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

	}

	return 0;

}

1007 Link with Limit

题目大意

给出置换$f$，然后$f_i(x)$表示$x$置换$i$次之后的位置。
定义
$g(x)=\lim_{n->+\infty}\frac{1}{n}\sum_{i=1}^nf_i(x)$

求是否对于所有$g(x)(x\in [1,n])$都是相同的值。

$1\leq n\leq 10^5$

解题思路

最后肯定会置换到一个环内，考虑每个环的平均值是否相等即可

时间复杂度$O(n)$

代码由我们伟大的$\text$写出，所以我没有

1011 Yiwen with Formula

题目大意

给出$n$个数的一个可重集合$a$。求它的所有子集的和的乘积。模$998244353$。

$1\leq T\leq 10,1\leq n\leq 10^5,\sum n\leq 2.5\times 10^5,\sum a_i\leq 4\times 10^5$

解题思路

暴力用分治$NTT$求出每个和的方案数，然后因为是当指数的所以要模$\varphi(998244353)$所以要用任意模数就可暴草过去了。

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

using namespace std;

const ll N=4e5*4+10,sqq=32768,p=998244352,P=998244353;

const double Pi=acos(-1);

struct complex{

    double x,y;

    complex (double xx=0,double yy=0)

    {x=xx;y=yy;return;}

}A[N],B[N],C[N],D[N];

struct Poly{

	ll a[N],n;

}F[20];

ll power(ll x,ll b,ll P){

	ll ans=1;

	while(b){

		if(b&1)ans=ans*x%P;

		x=x*x%P;b>>=1;

	}

	return ans;

}

complex operator+(complex a,complex b)

{return complex(a.x+b.x,a.y+b.y);}

complex operator-(complex a,complex b)

{return complex(a.x-b.x,a.y-b.y);}

complex operator*(complex a,complex b)

{return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}

complex w[N];

ll n,m,T,u[N],v[21],r[N];

void FFT(complex *f,ll op,ll n){

    for(ll i=0;i<n;i++)

        if(i<r[i])swap(f[i],f[r[i]]);

    for(ll p=2;p<=n;p<<=1){

        ll len=p>>1;

        for(ll k=0;k<n;k+=p)

            for(ll i=k;i<k+len;i++){

                complex tmp=w[n/len*(i-k)];

                if(op==-1)tmp.y=-tmp.y;

                complex tt=f[i+len]*tmp;

                f[i+len]=f[i]-tt;

                f[i]=f[i]+tt;

            }

    }

    if(op==-1){

        for(ll i=0;i<n;i++)

            f[i].x=(ll)(f[i].x/n+0.49);

    }

    return;

}

void MTT(ll *a,ll *b,ll *c,ll m,ll k){

    ll n=1;

    while(n<=m+k)n<<=1;

    for(ll i=0;i<n;i++){

        r[i]=(r[i>>1]>>1)|((i&1)?(n>>1):0);

    	A[i].x=A[i].y=B[i].x=B[i].y=0;

    	C[i].x=C[i].y=D[i].x=D[i].y=0;

	}

    for(ll len=1;len<n;len<<=1)

        for(ll i=0;i<len;i++)

            w[n/len*i]=complex(cos(i*Pi/len),sin(i*Pi/len));

    for(ll i=0;i<m;i++)A[i].x=a[i]/sqq,B[i].x=a[i]%sqq;

    for(ll i=0;i<k;i++)C[i].x=b[i]/sqq,D[i].x=b[i]%sqq;

    FFT(A,1,n);FFT(B,1,n);FFT(C,1,n);FFT(D,1,n);

    complex t1,t2;

    for(ll i=0;i<n;i++){

        t1=A[i]*C[i];t2=B[i]*D[i];

        B[i]=A[i]*D[i]+B[i]*C[i];

        A[i]=t1;C[i]=t2;

    }

    FFT(A,-1,n);FFT(B,-1,n);FFT(C,-1,n);

    for(ll i=0;i<n;i++){

    	c[i]=0;

        (c[i]+=(ll)(A[i].x)*sqq%p*sqq%p)%=p;

        (c[i]+=(ll)(B[i].x)*sqq%p)%=p;

        (c[i]+=(ll)(C[i].x))%=p;

    }

    return;

}

void Mul(Poly &a,Poly &b){

	MTT(a.a,b.a,a.a,a.n,b.n);

	a.n=a.n+b.n-1;return;

}

ll findq(){

	for(ll i=0;i<20;i++)

		if(!v[i]){v[i]=1;return i;}

}

ll Solve(ll l,ll r){

	if(l==r){

		ll p=findq();

		for(ll i=0;i<=u[l];i++)

			F[p].a[i]=0;

		F[p].a[0]=1;F[p].a[u[l]]=1;

		F[p].n=u[l]+1;return p;

	}

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

	ll ls=Solve(l,mid),rs=Solve(mid+1,r);

	Mul(F[ls],F[rs]);v[rs]=0;return ls;

}

signed main(){

	scanf("%lld",&T);

	while(T--){

		scanf("%lld",&n);

		bool flag=0;ll ans=1,sum=0;

		for(ll i=1;i<=n;i++){

			scanf("%lld",&u[i]);

			flag|=!u[i];sum+=u[i];

		}

		if(flag){puts("0");continue;}

		ll id=Solve(1,n);u[id]=0;

		for(ll i=1;i<=sum;i++)

			ans=ans*power(i,F[id].a[i],P)%P;

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

	}

}

巴特西

2021“MINIEYE杯”中国大学生算法设计超级联赛(7)部分题解

前言

正题

1004 Link with Balls

题目大意

解题思路

code

1005 Link with EQ

题目大意

解题思路

code

1007 Link with Limit

题目大意

解题思路

1011 Yiwen with Formula

题目大意

解题思路

code

最新文章

热门文章