省选模拟2(Provincial selection simulation 2)

A. 守序划分问题

前 \(n\) 个正整数划分成 \(m\) 个集合,不存在一个分解线使得划分出来的值域分开

那么设 \(f_{i,j,k}\) 表示将前 \(i\) 数划分到 \(j\) 个集合里,其中还剩 \(k\) 个集合没有达到最大值

那么答案就是 \(f_{n,m,0}\) 边界 \(f_{0,0,0}=1\) 对于 \(i\neq0,n\) \(f_{i,j,0}=0\)

转移的话分别考虑是否新开一个集合,是否让一个集合达到最大值

\(f_{i,j,k}=f_{i-1,j-1,k-1}+f_{i-1,j-1,k+(k+1)f_{i-1,j,k+1}+kf_{i-1,j,k}}\)

#include<bits/stdc++.h>
#define int long long
#define rint signed
#define mod 998244353
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,m;
int f[2][510][510],cur;
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	freopen("partition.in","r",stdin);
	freopen("partition.out","w",stdout);
	n=read(),m=read();
	f[cur^1][0][0]=1;
	for(int i=1;i<=n;i++,cur^=1){
		memset(f[cur],0,sizeof(f[cur]));
		for(int j=1;j<=min(i,m);j++) for(int k=0;k<=min(i,m);k++){
			if(i!=n&&k==0) f[cur][j][k]=0;
			else f[cur][j][k]=(f[cur^1][j-1][k]+f[cur^1][j-1][k-1]+(k+1)*f[cur^1][j][k+1]+k*f[cur^1][j][k])%mod;
		}
	}
	printf("%lld\n",f[cur^1][m][0]);
	return 0;
}

B. 欧拉函数

第一种回答直接暴力求和然后 \(O(\sqrt n)\) 分解求欧拉函数

欧拉函数相当于将 \(n\) 分解质因数变成这样的形式 \(n=\prod\limits_{i=1}^{cnt}p_i^{k_i}\)

然后 \(\varphi(n)=n\times\prod\limits_{i=1}^{cnt}\frac{p_i-1}{p_i}\)

于是只要求出乘积和质因数是什么就行了

乘积可以朴素的解决,质因数用 \(bitset\) 记录就行,每次合并

#include<bits/stdc++.h>
#define int long long
#define rint signed
#define lson rt<<1
#define rson rt<<1|1
#define mod 1000000007
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,q;
int a[50010],inv[50010];
int prime[50010],id[50010],phi[50010],g[50010],cnt;
bool is[50010];
bitset<4210>B;
struct Seg{int sum,prod;bitset<4210>fac;}st[50010*4];
bitset<4210> getfac(int x){
	bitset<4210> tmp;
	while(x!=1){tmp[id[g[x]]]=1;x/=g[x];}
	return tmp;
}
inline int qpow(int x,int k){
	int res=1,base=x;
	while(k){if(k&1) res=res*base%mod;base=base*base%mod;k>>=1;}
	return res;
}
inline int euler(int x){
	int res=x;
	for(int i=1;i<=cnt&&prime[i]*prime[i]<=x;i++) if(x%prime[i]==0){
		res-=res/prime[i];
		while(x%prime[i]==0) x/=prime[i];
	}
	if(x!=1) res-=res/x;
	return res;
}
inline void pushup(int rt){
	st[rt].prod=st[lson].prod*st[rson].prod%mod;
	st[rt].sum=st[lson].sum+st[rson].sum;
	st[rt].fac=st[lson].fac|st[rson].fac;
}
void build(int rt,int l,int r){
	if(l==r) return st[rt].fac=getfac(a[l]),st[rt].sum=a[l],st[rt].prod=a[l],void();
	int mid=(l+r)>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	pushup(rt);
}
void upd(int rt,int l,int r,int pos,int k){
	if(l==r) return st[rt].sum=k,st[rt].prod=k,st[rt].fac=getfac(k),void();
	int mid=(l+r)>>1;
	if(pos<=mid) upd(lson,l,mid,pos,k);
	else upd(rson,mid+1,r,pos,k);
	pushup(rt);
}
int querys(int rt,int l,int r,int L,int R){
	if(L<=l&&r<=R) return st[rt].sum;
	int mid=(l+r)>>1,res=0;
	if(L<=mid) res+=querys(lson,l,mid,L,R);
	if(R>mid) res+=querys(rson,mid+1,r,L,R);
	return res;
}
int queryphi(int rt,int l,int r,int L,int R){
	if(L<=l&&r<=R) return B|=st[rt].fac,st[rt].prod;
	int mid=(l+r)>>1,res=1;
	if(L<=mid) res=res*queryphi(lson,l,mid,L,R)%mod;
	if(R>mid) res=res*queryphi(rson,mid+1,r,L,R)%mod;
	return res;
}
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	freopen("phi.in","r",stdin);
	freopen("phi.out","w",stdout);
	phi[1]=1;inv[1]=1;
	for(int i=2;i<=40000;i++){
		inv[i]=qpow(i,mod-2);
		if(!is[i]) prime[++cnt]=i,phi[i]=i-1,g[i]=i,id[i]=cnt;
		for(int j=1;j<=cnt&&i*prime[j]<=40000;j++){
			is[i*prime[j]]=1;g[i*prime[j]]=prime[j];
			if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}
			phi[i*prime[j]]=phi[i]*phi[prime[j]];
		}
	}
	n=read(),q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	build(1,1,n);
	for(int i=1,op,l,r,res;i<=q;i++){
		op=read(),l=read(),r=read();
		if(op==0){
			upd(1,1,n,l,r);
		}else if(op==1){
			printf("%lld\n",euler(querys(1,1,n,l,r)));
		}else{
			B.reset();res=queryphi(1,1,n,l,r);
			for(int j=1;j<=cnt;j++) if(B[j]) res=res*inv[prime[j]]%mod*(prime[j]-1)%mod;
			printf("%lld\n",res);
		}
	}
	return 0;
}

C. 点整的上圆

\(30pts\) 暴力证明可以参考圆上的整点

总之就是将 \(r\) 分解质因数

如果 \(\%4=1\) 那么贡献 \(2*k+1\)

然后预处理筛一下,在给每个数分解就行了

正解不会

#include<bits/stdc++.h>
#define int long long
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,r,ans;
int prime[10000010],g[10000010],cnt;
bool is[10000010];
inline int getfac(int x){
	int res=1,p,k;
	while(x!=1){
		p=g[x];k=0;
		while(x%p==0) k++,x/=p;
		if(p%4==1) res=res*(2*k+1);
	}
	return res*4;
}
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	freopen("jozb.in","r",stdin);
	freopen("jozb.out","w",stdout);
	for(int i=2;i<=10000000;i++){
		if(!is[i]) prime[++cnt]=i,g[i]=i;
		for(int j=1;j<=cnt&&i*prime[j]<=10000000;j++){
			is[i*prime[j]]=1;g[i*prime[j]]=prime[j];
			if(i%prime[j]==0) break;
		}
	}
	r=read(),n=read();
	for(int i=1;i<=r;i++) if(getfac(i)==n) ans++;
	printf("%lld\n",ans);
	return 0;
}
————————

A. Ordered partition problem

The first \ (n \) positive integers are divided into \ (m \) sets, and there is no decomposition line to separate the divided value ranges

Then let \ (f_{i, J, K} \) mean that the first \ (I \) number is divided into \ (J \) sets, of which there are still \ (K \) sets that do not reach the maximum value

Then the answer is \ (f {n, m, 0} \) boundary \ (f {0,0,0} = 1 \) for \ (I \ neq0, n \) \ (f {I, J, 0} = 0 \)

In case of transfer, consider whether to open a new set and whether to maximize a set

\(f_{i,j,k}=f_{i-1,j-1,k-1}+f_{i-1,j-1,k+(k+1)f_{i-1,j,k+1}+kf_ {i-1,j,k}}\)

#include<bits/stdc++.h>
#define int long long
#define rint signed
#define mod 998244353
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,m;
int f[2][510][510],cur;
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	freopen("partition.in","r",stdin);
	freopen("partition.out","w",stdout);
	n=read(),m=read();
	f[cur^1][0][0]=1;
	for(int i=1;i<=n;i++,cur^=1){
		memset(f[cur],0,sizeof(f[cur]));
		for(int j=1;j<=min(i,m);j++) for(int k=0;k<=min(i,m);k++){
			if(i!=n&&k==0) f[cur][j][k]=0;
			else f[cur][j][k]=(f[cur^1][j-1][k]+f[cur^1][j-1][k-1]+(k+1)*f[cur^1][j][k+1]+k*f[cur^1][j][k])%mod;
		}
	}
	printf("%lld\n",f[cur^1][m][0]);
	return 0;
}

B. Euler function

The first answer is to sum directly and then \ (O (\ sqrt n) \) decompose to find the Euler function

Euler function is equivalent to decomposing \ (n \) prime factor into such form \ (n = \ prod \ limits {I = 1} ^ {cnt}p_i ^ {k_i} \)

然后 \(\varphi(n)=n\times\prod\limits_{i=1}^{cnt}\frac{p_i-1}{p_i}\)

So just find out what the product and prime factor are

The product can be solved simply. The prime factor can be recorded with \ (BitSet \) and merged each time

#include<bits/stdc++.h>
#define int long long
#define rint signed
#define lson rt<<1
#define rson rt<<1|1
#define mod 1000000007
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,q;
int a[50010],inv[50010];
int prime[50010],id[50010],phi[50010],g[50010],cnt;
bool is[50010];
bitset<4210>B;
struct Seg{int sum,prod;bitset<4210>fac;}st[50010*4];
bitset<4210> getfac(int x){
	bitset<4210> tmp;
	while(x!=1){tmp[id[g[x]]]=1;x/=g[x];}
	return tmp;
}
inline int qpow(int x,int k){
	int res=1,base=x;
	while(k){if(k&1) res=res*base%mod;base=base*base%mod;k>>=1;}
	return res;
}
inline int euler(int x){
	int res=x;
	for(int i=1;i<=cnt&&prime[i]*prime[i]<=x;i++) if(x%prime[i]==0){
		res-=res/prime[i];
		while(x%prime[i]==0) x/=prime[i];
	}
	if(x!=1) res-=res/x;
	return res;
}
inline void pushup(int rt){
	st[rt].prod=st[lson].prod*st[rson].prod%mod;
	st[rt].sum=st[lson].sum+st[rson].sum;
	st[rt].fac=st[lson].fac|st[rson].fac;
}
void build(int rt,int l,int r){
	if(l==r) return st[rt].fac=getfac(a[l]),st[rt].sum=a[l],st[rt].prod=a[l],void();
	int mid=(l+r)>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	pushup(rt);
}
void upd(int rt,int l,int r,int pos,int k){
	if(l==r) return st[rt].sum=k,st[rt].prod=k,st[rt].fac=getfac(k),void();
	int mid=(l+r)>>1;
	if(pos<=mid) upd(lson,l,mid,pos,k);
	else upd(rson,mid+1,r,pos,k);
	pushup(rt);
}
int querys(int rt,int l,int r,int L,int R){
	if(L<=l&&r<=R) return st[rt].sum;
	int mid=(l+r)>>1,res=0;
	if(L<=mid) res+=querys(lson,l,mid,L,R);
	if(R>mid) res+=querys(rson,mid+1,r,L,R);
	return res;
}
int queryphi(int rt,int l,int r,int L,int R){
	if(L<=l&&r<=R) return B|=st[rt].fac,st[rt].prod;
	int mid=(l+r)>>1,res=1;
	if(L<=mid) res=res*queryphi(lson,l,mid,L,R)%mod;
	if(R>mid) res=res*queryphi(rson,mid+1,r,L,R)%mod;
	return res;
}
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	freopen("phi.in","r",stdin);
	freopen("phi.out","w",stdout);
	phi[1]=1;inv[1]=1;
	for(int i=2;i<=40000;i++){
		inv[i]=qpow(i,mod-2);
		if(!is[i]) prime[++cnt]=i,phi[i]=i-1,g[i]=i,id[i]=cnt;
		for(int j=1;j<=cnt&&i*prime[j]<=40000;j++){
			is[i*prime[j]]=1;g[i*prime[j]]=prime[j];
			if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}
			phi[i*prime[j]]=phi[i]*phi[prime[j]];
		}
	}
	n=read(),q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	build(1,1,n);
	for(int i=1,op,l,r,res;i<=q;i++){
		op=read(),l=read(),r=read();
		if(op==0){
			upd(1,1,n,l,r);
		}else if(op==1){
			printf("%lld\n",euler(querys(1,1,n,l,r)));
		}else{
			B.reset();res=queryphi(1,1,n,l,r);
			for(int j=1;j<=cnt;j++) if(B[j]) res=res*inv[prime[j]]%mod*(prime[j]-1)%mod;
			printf("%lld\n",res);
		}
	}
	return 0;
}

C. Upper circle of dot integer

\(30pts \) violence proof can refer to the whole point on the circle

In short, it is to decompose \ (R \) into prime factors

If \ (\% 4 = 1 \), then contribution \ (2 * k + 1 \)

Then the preprocessing screen is used to decompose each number

Positive solution will not

#include<bits/stdc++.h>
#define int long long
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,r,ans;
int prime[10000010],g[10000010],cnt;
bool is[10000010];
inline int getfac(int x){
	int res=1,p,k;
	while(x!=1){
		p=g[x];k=0;
		while(x%p==0) k++,x/=p;
		if(p%4==1) res=res*(2*k+1);
	}
	return res*4;
}
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	freopen("jozb.in","r",stdin);
	freopen("jozb.out","w",stdout);
	for(int i=2;i<=10000000;i++){
		if(!is[i]) prime[++cnt]=i,g[i]=i;
		for(int j=1;j<=cnt&&i*prime[j]<=10000000;j++){
			is[i*prime[j]]=1;g[i*prime[j]]=prime[j];
			if(i%prime[j]==0) break;
		}
	}
	r=read(),n=read();
	for(int i=1;i<=r;i++) if(getfac(i)==n) ans++;
	printf("%lld\n",ans);
	return 0;
}