# 省选模拟2(Provincial selection simulation 2)-其他

## 省选模拟2(Provincial selection simulation 2)

### A. 守序划分问题

$$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;
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);
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. 欧拉函数

#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;
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]];
}
}
build(1,1,n);
for(int i=1,op,l,r,res;i<=q;i++){
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$$ 暴力证明可以参考圆上的整点

#include<bits/stdc++.h>
#define int long long
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
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;
}
}
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;
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);
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} \)

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;
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]];
}
}
build(1,1,n);
for(int i=1,op,l,r,res;i<=q;i++){
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;
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;
}
}