技术教程 编程教程 退役IV次后做题记录 正文

退役IV次后做题记录

2023-05-02,,

退役IV次后做题记录

我啥都不会了。。。。

AGC023 D

如果所有的楼房都在\(S\)同一边可以直接得出答案。

否则考虑最左最右两边的票数，如果左边>=右边，那么最右边会投给左边，因为就算车往右开，只要没走到最左边，最后也要折回左边，所以不如先走完左边然后直接过来。左边<右边一样。

然后递归下去变成了一个子问题，可以看做一边的票数+=另一边，然后删除另一边。

AGC023 E

考虑枚举两个位置\(i,j\)计算这两个位置产生逆序对的排列数量。

如果\(A_i=A_j\)很好算，方案数都是对称的，就是总的排列数/2。

总的排列数计算方法：设\(C_i=\sum_{j=1}^n[A_j\ge i],sum=\Pi_{i=1}^n(C_i-n+i)\)

如果\(A_i<A_j\)也很好算，如果\(P_j\)取\(>A_i\)的值显然没有贡献，所以将\(A_j\)强制设为\(A_i\)再算即可，变成上面的情况

因为减少了一个\(A\)，所以会减少一段\(C\)，也就是排列的数量会变，乘一个\(\Pi\frac{C_i-n+i-1}{C_i-n+i}\)

设\(d_i=\frac{C_i-n+i-1}{C_i-n+i}\)，也就是会乘一段\(d\)，但是\(d\)有\(0\)不能直接前缀鸡所以分段搞一下就行了。

如果\(A_i>A_j\)正难则反考虑用总方案-没有逆序对的方案数，这个就是将\(A_i\)强制设为\(A_j\)后总排列数/2，和上面一样，也是对\(d\)分段搞。

AGC023 F

先考虑有一堆序列，怎么拼成一段最优的序列，推推式子就知道答案是按照\(cnt_0/cnt_1\)从大到小选

然后搬到树上来，也是对的，就是每次选一个\(cnt_0/cnt_1\)最小的点，将这个点现在的序列合并到其父亲

（虽然感觉很玄学但却是就是对的。。。

loj2409

qwq多项式都不会打了qwq

计算\(F(x)=\sum x^if_i\)

\(=\sum_{i=1}^nx^i\sum_{j=1}^na_j^i\)

\(\sum_{j=1}^n\sum_{i=1}^nx^ia_j^i\)

\(\sum_{i=1}^n\frac{1}{1-a_ix}\)

然后这个可以分治通分跑了qwq但是常数很大qwq然后就神仙了qwq

\(\sum_{i=1}^n1-\frac{a_ix}{1-a_ix}\)

\(n-x\sum_{i=1}^n\frac{a_i}{1-a_ix}\)

我也不知道怎么就能看出来这里可以积分了qwq

\(n-x\sum_{i=1}^n(\ln(1-a_ix))'\)

\(n-x(\ln\Pi_{i=1}^n(1-a_ix))'\)

就可以较快地分治ntt做了qwq好牛批啊qwq

bzoj3462

首先\(S\)肯定是\(\Pi p_i\)的形式（\(p\)互不相同）

然后就变成了一个背包

将\(n\)减去\(\sum p\)，就变成了一个完全背包方案数

然后我发现我不会

这题还有一个性质就是\(p\)是\(S\)约数所以很优秀

设\(n=\sum p_ic_i,P_i=S/p_i\)，将\(c_i\)拆成\(xP_i+y\)的形式，其中\(y<P_i\)，那么实际上\(p_iP_ix\)就是\(S\)倍数了，后面的\(p_iy\)就小于\(S\)了于是可以枚举有多少个整的\(S\)，分配给\(m\)个质数，剩下的做一个完全背包

#include<bits/stdc++.h>

#define mod 1000000007

typedef long long ll;

ll gi(){

	ll x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch))f^=ch=='-',ch=getchar();

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

	return f?x:-x;

}

int p[10],m,bag[14000010],_bag[14000010],inv[10],ifact;

int C(ll n,int m){

	int ret=ifact;

	for(int i=0;i<m;++i)ret=(n-i)%mod*ret%mod;

	return ret;

}

int Get(ll n,int m){return n?C(n+m-1,m-1):1;}

int main(){

#ifdef XZZSB

	freopen("in.in","r",stdin);

	freopen("out.out","w",stdout);

#endif

	int S=gi(),q=gi();

	for(int i=2,s=S;i<=s;++i)

		if(s%i==0){

			s/=i;p[++m]=i;

			if(s%i==0){while(q--)puts("0");return 0;}

		}

	int N=m*S,sum=0;

	bag[0]=1;

	for(int _=1,x;_<=m;++_){

		x=p[_];sum+=x;

		memcpy(_bag,bag,sizeof bag);

		for(int i=1;i<=x;++i){

			for(int j=i,sum=i==x;j<=N;j+=x){

				if(j-S>=0)sum=(sum-_bag[j-S]+mod)%mod;

				bag[j]=(bag[j]+sum)%mod;

				sum=bag[j];

			}

		}

	}

	inv[1]=1;for(int i=2;i<=m;++i)inv[i]=mod-1ll*inv[mod%i]*(mod/i)%mod;

	ifact=1;for(int i=2;i<m;++i)ifact=1ll*ifact*inv[i]%mod;

	while(q--){

		ll n=gi();int ans=0;if(n<sum){puts("0");continue;}

		n-=sum;

		for(int i=0,lim=std::min(n/S,m-1ll);i<=lim;++i)

			ans=(ans+1ll*Get(n/S-i,m)*bag[n%S+S*i])%mod;

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

	}

	return 0;

}

bzoj3481

枚举一个数\(x\)，要求满足\(xy\equiv Q(\mod P)\)的\(y\)数量

也就是满足\(Ax+Py=Q\)的\(x\)数量

根据exgcd的理论，首先当\(Q\)是\(\gcd(A,P)\)倍数时才有解，然后每隔\(P/\gcd(A,P)\)会出现一个\(x\)，也就是\([0,P)\)中解的数量就是\(\gcd(A,P)\)

答案就是\(\sum_{i=0}^{P-1}\gcd(i,P)[\gcd(i,P)|Q]\)

再推推就是\(\sum_{d|P,d|Q}^{P-1}d\cdot\varphi(\frac Pd)\)

然后用pr分解一下。。。（pr都不会写了kk）

#include<bits/stdc++.h>

typedef long long ll;

#define mod 1000000007

ll gi(){

    ll x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch))f^=ch=='-',ch=getchar();

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

    return f?x:-x;

}

ll mul(ll x,ll y,ll mo){

    ll r=x*y-(ll)((long double)x/mo*y)*mo;

    return(r%mo+mo)%mo;

}

ll pow(ll x,ll y,ll mo){

    ll ret=1;

    while(y){

        if(y&1)ret=mul(ret,x,mo);

        x=mul(x,x,mo);y>>=1;

    }

    return ret;

}

bool MR(ll x){

    static int pr[]={2,3,5,61,23333,19260817};

    if(x==1)return 0;

    for(int i=0;i<6;++i)if(x==pr[i])return 1;

    int t=0;

    ll _=x-1;

    while(~_&1)_>>=1,++t;

    for(int i=0;i<6;++i){

        ll s=pow(pr[i],_,x);

        if(s==1||s==x-1)continue;

        int T=t;

        while(T--){

            s=mul(s,s,x);

            if(s==x-1)break;

        }

        if(T==-1)return 0;

    }

    return 1;

}

int PRC;ll PRX;

ll f(ll y){return(mul(y,y,PRX)+PRC)%PRX;};

ll PR(ll x){

    if(~x&1)return 2;

    PRX=x;

    PRC=rand()%(x-1)+1;

    ll a=rand()%x,b=a;

    int i=1,s=2;

    for(;;){

        ll y=std::__gcd(llabs(b-a),x);

        if(y>1&&y<x)return y;

        a=f(a);

        if(a==b)return 1;

        if(++i==s)b=a,s<<=1;

    }

}

int iP[10010],pE[10010],qE[10010],m,xP[10010];

std::map<ll,int>M;

void fact(ll x,int*E){

    if(x==1)return;

    if(MR(x)){if(!M.count(x))M[x]=++m,xP[m]=x%mod;++E[M[x]];return;}

    ll y;while(y=PR(x),y==1);

    fact(y,E),fact(x/y,E);

}

int ans;

int main(){

#ifdef XZZSB

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    srand(19260817);

    int n=gi();

    int P=1,Q=1;ll x;

    for(int i=1;i<=n;++i)x=gi(),P=x%mod*P%mod,fact(x,pE);

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

        x=gi();

        if(!x){

            memcpy(qE,pE,sizeof pE);

            break;

        }

        Q=x%mod*Q%mod,fact(x,qE);

    }

    for(int i=1;i<=m;++i)iP[i]=pow(xP[i],mod-2,mod);

    for(int i=1;i<=m;++i)qE[i]=std::min(qE[i],pE[i]);

    ans=P;

    for(int i=1;i<=m;++i)ans=1ll*ans*((pE[i]==qE[i])+1ll*(qE[i]+1-(pE[i]==qE[i]))*(xP[i]-1)%mod*iP[i]%mod)%mod;

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

    return 0;

}

bzoj3512

\(\sum_{i=1}^n\sum_{j=1}^m\varphi(ij)\)

\(=\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)f(\gcd(i,j))\)

这里\(f(x)=\frac{x}{\varphi(x)}\)

用一些套路的推法，\(=\sum_{i=1}^n\varphi(i)\sum_{d|i}f(d)\sum_{j=1}^m\varphi(j)[\gcd(i,j)=d]\)

构造\(g(x)\)使得\(\sum_{d|n}g(d)=f(n)\)（n在1e5范围所以直接减就行了）

\(=\sum_{i=1}^n\varphi(i)\sum_{d|i}g(d)\sum_{d|j}^m\varphi(j)\)

\(=\sum_{d=1}^ng(d)\left(\sum_{d|i}^n\varphi(i)\right)\left(\sum_{d|j}^m\varphi(j)\right)\)

然后这个形式就很优秀了，现在要求\(\sum_{d|x}^n\varphi(x)\)

怎么求呢？我不会。。。然后瞎b推

\(=\varphi(d)\sum_{i=1}^{n/d}\varphi(i)f(\gcd(i,d))\)

\(=\varphi(d)\sum_{j|d}^{n/d}f(j)\left(\sum_{j|i}^{n/d}\varphi(i)\right)\)

然后后面这部分怎么又是这个形式了。。就写个递归

然后跑的飞快？？？

#include<bits/stdc++.h>

typedef long long ll;

#define mod 1000000007

ll gi(){

	ll x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch))f^=ch=='-',ch=getchar();

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

	return f?x:-x;

}

int pow(int x,int y){

	int ret=1;

	while(y){

		if(y&1)ret=1ll*ret*x%mod;

		x=1ll*x*x%mod;y>>=1;

	}

	return ret;

}

const int N=5000000;

int pr[N+10],phi[N+10],sphi[N+10],P,s[N+10];

bool yes[N+10];

int Phi(int x){

	if(x<=N)return sphi[x];

	int ret=1ll*x*(x+1)/2%mod;

	for(int l=2,r;l<=x;l=r+1)r=x/(x/l),ret=(ret-1ll*Phi(x/l)*(r-l+1)%mod+mod)%mod;

	return ret;

}

int dPhi(int x,int n){//\sum_{x|i}^n\varphi(x)

	if(x==1)return Phi(n);

	if(n<x)return 0;

	int ret=0;

	for(int i=1;i*i<=x;++i)

		if(x%i==0){

			ret=(ret+1ll*s[i]*dPhi(i,n/x))%mod;

			if(i*i<x)ret=(ret+1ll*s[x/i]*dPhi(x/i,n/x))%mod;

		}

	return 1ll*ret*phi[x]%mod;

}

int main(){

#ifdef XZZSB

	freopen("in.in","r",stdin);

	freopen("out.out","w",stdout);

#endif

	int n=gi(),m=gi();

	for(int i=2;i<=N;++i){

		if(!yes[i])pr[++P]=i,phi[i]=i-1;

		for(int j=1;j<=P&&i*pr[j]<=N;++j){

			yes[i*pr[j]]=1;

			if(i%pr[j]==0){

				phi[i*pr[j]]=phi[i]*pr[j];

				break;

			}

			phi[i*pr[j]]=phi[i]*(pr[j]-1);

		}

	}

	phi[1]=1;

	for(int i=1;i<=n;++i)s[i]=1ll*i*pow(phi[i],mod-2)%mod;

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

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

			if(i%j==0){

				s[i]=(s[i]-s[j]+mod)%mod;

				if(j!=1&&j*j!=i)s[i]=(s[i]-s[i/j]+mod)%mod;

			}

	}

	for(int i=1;i<=N;++i)sphi[i]=(phi[i]+sphi[i-1])%mod;

	int ans=0;

	for(int i=1;i<=n;++i)ans=(ans+1ll*s[i]*dPhi(i,n)%mod*dPhi(i,m))%mod;

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

	return 0;

}

bzoj3560

显然可以质因子分开算，然后直接算就行了= =

#include<bits/stdc++.h>

typedef long long ll;

#define mod 1000000007

ll gi(){

	ll x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch))f^=ch=='-',ch=getchar();

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

	return f?x:-x;

}

int pr[666010],P,d[10000010],pd[10000010],sd[10000010];

std::vector<int>vec[666010];

bool yes[10000010];

int pp[100];

int main(){

#ifdef XZZSB

	freopen("in.in","r",stdin);

	freopen("out.out","w",stdout);

#endif

	int n=gi(),N=10000000;

	for(int i=2;i<=N;++i){

		if(!yes[i])pr[++P]=i,pd[i]=i,d[i]=P,sd[i]=1;

		for(int j=1;j<=P&&i*pr[j]<=N;++j){

			yes[i*pr[j]]=1;d[i*pr[j]]=j;

			if(i%pr[j]==0){

				pd[i*pr[j]]=pd[i]*pr[j];

				sd[i*pr[j]]=sd[i]+1;

				break;

			}

			pd[i*pr[j]]=pr[j];

			sd[i*pr[j]]=1;

		}

	}

	for(int i=1,x;i<=n;++i){

		x=gi();

		while(x>1)vec[d[x]].push_back(sd[x]),x/=pd[x];

	}

	int ans=1;

	for(int i=1;i<=P;++i){

		if(vec[i].empty())continue;

		int k=1,y=pr[i];

		pp[0]=1;pp[1]=y;

		while(1ll*pp[k]*y<=N)pp[k+1]=pp[k]*y,++k;

		for(int j=1;j<=k;++j)pp[j]=(pp[j]+pp[j-1])%mod;

		int res=0;

		for(int j=0,x;j<vec[i].size();++j){

			x=vec[i][j];

			res=(1ll*res*pp[x]+pp[x-1]*(y-1))%mod;

		}

		ans=1ll*ans*(res+1)%mod;

	}

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

	return 0;

}

退役IV次后做题记录的相关教程结束。

《退役IV次后做题记录.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!