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}}\)
Code
#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\) 记录就行，每次合并
Code
#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\)
然后预处理筛一下，在给每个数分解就行了
正解不会
Code
#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;
}