【日常摸鱼】牛客挑战赛46
前言
日渐消沉，随便做几题，假装我还在练acm。
A 奇怪的计算器
水题略了
B 最小的指数
链接
https://ac.nowcoder.com/acm/contest/9510/B
题意
询问正整数x的质因数的指数的最小值。数据组数1e5，n的范围1e18。
题解
这个操作还挺有趣的。。
先筛掉4000以内的所有质数，然后剩下的质数的指数不会超过4。
然后如果最小指数是4，那肯定能开4次方，（其他情况会有更小的指数）
如果最小指数是3，那肯定能开3次方，（其他情况会有更小的指数）
如果最小指数是2，那就要求能开2次方，但不能开4次方。
其余的就是1次的了。
(Code)
#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define LD long double
using namespace std;
const int N=3e5+10;
const LL INF=1e18;
LL read(){
LL 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*10+ch-'0';ch=getchar();}
return x*f;
}
void print(LL x){
if(x>9) print(x/10);
putchar(x%10+'0');
}
int cnt=0;
bool vis[4050];
int p[4050];
LL qpow(LL x,int y){
LL res=1;
for(int i=1;i<=y;++i) {
if(res<=INF/x) res=res*x;
else res=INF;
}
return res;
}
LL sqr(LL x,int y){
LL l=1,r=1e9,mid;
while(l!=r){
mid=(l+r+1)>>1;
if(qpow(mid,y)<=x) l=mid;
else r=mid-1;
}
return l;
}
int main(){
for(int i=2;i<=4000;++i){
if(!vis[i]){
p[++cnt]=i;
for(int j=i+i;j<=4000;j+=i) vis[j]=1;
}
}
int T=read();LL n,x,y,mn;
while(T--){
n=read();mn=100;
if(n==1){
puts("0");
continue;
}
//cout<<n<<endl;
for(int i=1;i<=cnt;++i){
x=0;
while(n%p[i]==0){
n=n/p[i];
++x;
}
if(x)mn=min(mn,x);
}
//cout<<n<<endl;
if(n>1){
x=sqr(n,4);
if(x*x*x*x==n) mn=min(mn,(LL)4);
else{
x=sqr(n,3);
if(x*x*x==n) mn=min(mn,(LL)3);
else{
x=sqr(n,2);
if(x*x==n) mn=min(mn,(LL)2);
else mn=min(mn,(LL)1);
}
}
}
print(mn);puts("");
}
return 0;
}
C 排列
链接
https://ac.nowcoder.com/acm/contest/9510/C
题意
求长度为n，并且恰好有k个超级逆序对的排列的个数。n,k不超过500。超级逆序对就是两个数的数值之差至少为2的逆序对。
题解
就是前缀和优化一下DP就行了。
(Code)
#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define LD long double
using namespace std;
const int N=3e5+10;
const LL P=998244353;
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*10+ch-'0';ch=getchar();}
return x*f;
}
void print(LL x){
if(x>9) print(x/10);
putchar(x%10+'0');
}
void add(int &x,int y){
x+=y;if(x>=P)x-=P;
}
LL qpow(LL x,LL y){
LL re=1;
while(y){
if(y&1) re=re*x%P;
x=x*x%P;y>>=1;
}
return re;
}
int n,K;
int f[510][510][510+510];
int main(){
scanf("%d%d",&n,&K);
f[1][1][0]=1;
for(int i=1;i<=n;++i){
for(int j=i;j>=1;--j){
for(int k=0;k<=K;++k){
if(k>0) add(f[i][j][k],f[i][j+1][k-1]);
if(f[i][j][k]){
add(f[i+1][i+1][k],f[i][j][k]);
add(f[i+1][j][k+(i-j)+1],P-f[i][j][k]);
add(f[i+1][j][k+(i-j)],f[i][j][k]);
}
}
}
}
int ans=0;
for(int i=1;i<=n;++i) add(ans,f[n][i][K]);
printf("%lld
",qpow((LL)ans,P-2));
return 0;
}
D 数列
链接
https://ac.nowcoder.com/acm/contest/9510/D
题意
给一个长度为n的数列，求区间内每个数出现次数恰好为k的倍数的区间数。n，ai，k不超过1e6.
题解
给每个位置赋一个随机值，并且使任意连续的k个一样的数的随机值之和为0.
然后询问相当于有多少区间的赋值之和为0，这个就很容易做了。
(Code)
#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define LD long double
using namespace std;
const int N=1e6+10;
const LL P=998244353;
const LL INF=1e18;
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*10+ch-'0';ch=getchar();}
return x*f;
}
void print(LL x){
if(x>9) print(x/10);
putchar(x%10+'0');
}
unordered_map<LL,LL> mp;
int n,K;
int a[N],c[N];
vector<LL> ve[N];
LL sum[N],b[N];
int main(){
srand(time(0));
LL x,ans=0;
scanf("%d%d",&n,&K);mp[0]=1;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
++c[a[i]];
if(c[a[i]]<K){
x=rand()*rand()%INF*rand()%INF;
sum[a[i]]+=x;
ve[a[i]].push_back(x);
}
else if(c[a[i]]==K){
sum[a[i]]=-sum[a[i]];
ve[a[i]].push_back(sum[a[i]]);
}
b[i]=ve[a[i]][(c[a[i]]+K-1)%K];
b[i]+=b[i-1];
ans+=mp[b[i]];
mp[b[i]]++;
}
printf("%lld
",ans);
return 0;
}
E 反演
链接
https://ac.nowcoder.com/acm/contest/9510/E
题解
题目要求的式子 (sum_{i=1}^{n}sum_{j|m!}sigma_{0}(ij))
两数乘积的约数个数是可以转化成公约数有关的式子的。
(sum_{i=1}^{n}sum_{j|m!}sigma_{0}(ij)) (=) (sum_{i=1}^{n}sum_{j|m!}sum_{x|i}sum_{y|j}[(x,y)=1])
然后就是喜闻乐见的莫比乌斯反演推式子的套路。。这里直接给出推完之后的式子
(sum_{t|m!}mu(t)sum_{y|frac{m!}{t}}sigma_{0}(frac{m}{ty})sum_{i=1}^{lfloor frac{n}{t}
floor}lfloor frac{n}{it}
floor)
由于m不超过100，也就是说质数最多只有25个，有用的莫比乌斯函数也只有(2^{25})个，于是枚举莫比乌斯函数不为0的项加起来就可以了。
(Code)
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=3e5+10;
const LL P=998244353;
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*10+ch-'0';ch=getchar();}
return x*f;
}
void print(LL x){
if(x>9) print(x/10);
putchar(x%10+'0');
}
LL n,nn;
LL inv[100005],c[110];
int m,cnt;
int vis[110];
int p[110];
LL mp[1000000],MP[1000000];
LL F(LL x){
if(x<=nn&&mp[x]) return mp[x];
if(x>nn&&MP[(n/x)]) return MP[(n/x)];
LL res=0,v;
for(LL i=1,j;i<=x;i=j+1){
v=x/i;
j=x/v;
res+=v*(j-i+1);
}
res=res%P;
if(x<=nn) mp[x]=res;
if(x>nn) MP[(n/x)]=res;
return res;
}
LL ans;
void sol(int id,LL t,LL mu,LL sum){
if(t>n) return;
if(id>cnt){
ans+=mu*F(n/t)%P*sum%P;
return;
}
sol(id+1,t,mu,sum);
sol(id+1,t*(LL)p[id],P-mu,sum*inv[c[id]+2]%P*c[id]%P);
}
int main(){
inv[0]=inv[1]=1;
for(LL i=2;i<=100000;++i) inv[i]=(P-P/i)*inv[P%i]%P;
cin>>n>>m;nn=sqrt(n);cnt=0;ans=0;
for(int i=2;i<=m;++i){
if(!vis[i]){
p[++cnt]=i;
for(int j=i+i;j<=m;j+=i){
vis[j]=1;
}
}
}
int x;LL tot=1;
for(int i=1;i<=cnt;++i){
c[i]=0;x=m;
while(x>0){
x=x/p[i];
c[i]+=x;
}
tot=tot*(c[i]+2)%P*(c[i]+1)%P*inv[2]%P;
}
sol(1,1LL,1LL,tot);
ans=(ans%P+P)%P;
printf("%lld
",ans);
return 0;
}
F 柠檬树
链接
https://ac.nowcoder.com/acm/contest/9510/F
题解
我也还不会，这个LCT太神了QAQ