[UOJ摸鱼]UOJ Round #1解题报告
前言
还有好多题没补，先摸会儿鱼~
缩进优化
链接
题解
先推柿子！
要算的是找一个(K)使得(sum_{i=1}^{n}{lfloor frac{a_n}{K}
floor + a_n mod K})最小
化简一下就是(sum_{i-1}^{n}{a_i - (K-1) imes lfloor frac{a_n}{K}
floor})
显然(K)应该满足(1leq K leq max(a_i)) 。
当我们确定一个(K)的时候，(1)到(max(a_i))内最多有(lfloor frac{max(a_i)}{K}
floor)个不同的(lfloor frac{x}{K}
floor)的值。
于是我们直接枚举(K)，算出所有可能答案取个min就行。效率是(O(max(a_i)log(max(a_i))))。
(Code)
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL P=998244353;
const int N=1e6+10;
int n;
LL a[N],c[N];
LL ans,sum,mx,res,now;
int main(){
scanf("%d",&n);sum=0;mx=0;
for(int i=1;i<=n;++i) {
scanf("%lld",&a[i]);
sum+=a[i];mx=max(mx,a[i]);++c[a[i]];
}
for(int i=1;i<=mx;++i) c[i]+=c[i-1];
ans=sum;
for(LL k=2;k<=mx;++k){
now=0;
for(LL l=k,r=k+k-1;l<=mx;l+=k,r+=k){
r=min(r,mx);
now+=(c[r]-c[l-1])*(l/k);
}
now=now*(k-1);
res=sum-now;
ans=min(ans,res);
}
printf("%lld
",ans);
return 0;
}
外星人
链接
题解
首先可以发现我们对一个数取模多次相当于一次。。一个数对比它大的数取模不变。
第一步一定是排序emm
然后考虑第一问怎么做，由于(n)和(a_i)都不大，考虑(O(n^2))的递推。
如果(i)可以被模出来，那么再用它来对所有(a_i)取次一模，找到新的能被模出来的数。
最后找到最大的比a_1小的能模出来的数，就是第一问的答案了。记为ans1。
然后是第二问，和第一问思路类似。
用第一问答案反推。令(f_i)表示在(i)的时候，只考虑比(i)小的模数，最后得到ans1的方案数。
那么我们在算(f_i)的时候，只需要枚举第一个用来模的数，然后乘个组合数什么的就行了。
总效率是(O(n^2))的。
(Code)
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL P=998244353;
const int N=1e6+10;
int n,X;
int a[5005];
bool vis[5005];
LL f[5005];
int cnt[5005];
LL jc[5005];
LL ny[5005];
LL C(int x,int y){
if(y>x) return 0;
return jc[x]*ny[y]%P*ny[x-y]%P;
}
LL add(LL &x,LL y){
x+=y;if(x>=P)x-=P;
}
int main(){
jc[0]=jc[1]=ny[0]=ny[1]=1;
for(LL i=2;i<=5000;++i){
jc[i]=jc[i-1]*i%P;
ny[i]=(P-P/i)*ny[P%i]%P;
}
for(LL i=2;i<=5000;++i){
ny[i]=ny[i-1]*ny[i]%P;
}
scanf("%d%d",&n,&X);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
vis[X]=1;
for(int i=X;i>=1;--i){
if(vis[i])
for(int j=1;j<=n;++j){
if(i>=a[j]) vis[i%a[j]]=1;
}
}
int ans1=0;
for(int i=1;i<a[1];++i) if(vis[i]) ans1=i;
printf("%d
",ans1);
for(int i=1,j=0;i<=X;++i){
while(j<n&&a[j+1]<=i) ++j;
cnt[i]=j;
}
f[ans1]=1;
int Y;
for(int i=ans1+1;i<=X;++i){
for(int j=n;j>=1;--j){
if(a[j]>i) continue;
Y=i%a[j];
add(f[i],f[Y]*C(cnt[i]-1,cnt[Y])%P*jc[cnt[i]-1-cnt[Y]]%P);
}
}
LL ans=f[X];
ans=ans*C(n,cnt[X])%P*jc[n-cnt[X]]%P;
cout<<ans<<endl;
return 0;
}
这个仙人掌太难了，还没写QAQ