T1 集合均值
打了一个比较稳的\(70pts\)，本地测极限数据跑了\(0.2s\)，然后\(Waitingcoders\)上面\(T\)成了\(35\)，究极疑惑
其实和正解就差在了一个线性复杂度的求逆元，因为我的复杂度是\(O(nmlog(nm))\)的。。。
那么考场上推了推发现个规律
就是说他的所有情况不要按照每种情况一一计算贡献，要按照所有情况的每一列计算贡献，
这样你会发现每一列的答案是公差为\(p[1]\)的等差数列，其中\(p[1]\)即等差数列的第一项，他等于\(sum(nm)\times (nm-1)!\)
然后这不是答案，而是你计算每一列的总和，然后你再除以一个\(A\)集合的大小就算出平均数了，然后最后再除以总方案数\(nm!\)就是答案
mos
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int NN=2e7+5,mod=998244353;
namespace AE86{
auto 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;
};
auto write=[](int x,char opt='\n'){
char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');
do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
for(short i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);
};
inline int qmo(int a,int b,int ans=1){
int c=mod;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;
return ans;
}
}using namespace AE86;
int n,m,a[100005],ans,T,tmp;
int h[NN],v[NN];
inline void pre(){
h[0]=h[1]=1; v[0]=v[1]=1;
for(int i=2;i<=m*n+1;++i)h[i]=h[i-1]*i%mod;
tmp=qmo(h[n*m],mod-2); v[n*m+1]=qmo(h[n*m+1],mod-2);
for(int i=n*m;i>=2;--i) v[i]=v[i+1]*(i+1)%mod;
}
namespace WSN{
inline short main(){
freopen("mos.in","r",stdin);
freopen("mos.out","w",stdout);
n=read(); m=read(); pre();
for(int i=1;i<=n;++i) a[i]=read(),T+=a[i];
T%=mod; T=T*m%mod;
T=T*h[n*m-1]%mod;
for(int i=1;i<=n*m;++i)
ans=(ans+T*i%mod*v[i+1]%mod*h[i]%mod)%mod;
ans=ans*tmp%mod;
write(ans);
return 0;
}
}
signed main(){return WSN::main();}
T2 聚烷撑乙二醇
考场上读错题了以为第一个部分分所有的\(l=r\)并且等于同一个数，然后就直接输出了第一项，然后爆蛋了
然而他不相等啊！！那么，直接输出最大值就好了
考虑正解，不难发现在一段区间随机选择一个数的贡献是\(\frac{l+r}{2}\)
那么我们记每一个生成器的贡献为\(d_i\)，然后设\(f_i\)表示从第\(i\)个开始游戏的最大期望
他这种设法有些模糊，我觉得就是表示一个答案，他这么说的就好像是从哪里开始游戏是随便选择的一样
不难发现最后的答案\(f_n\)就是\(d_n\)，那么可以倒着转移，分三种情况转移
\(f_{n-1}= \begin{cases} d_{n-1} &\mathrm{ if }L_{n-1}>f_n\\ f_n &\mathrm{ if }R_{n-1}<f_n\\ \frac{f_n-L_{n-1}}{R_{n-1}-L_{n-1}}\times f_n &\mathrm{ if }x<f_n\\ \frac{R_{n-1}-f_n}{R_{n-1}-L_{n-1}}\times(\frac{f_n+R_{n-1}}{2}) &\mathrm{ if }x\geq f_n \end{cases}\)
如果\(f_{i+1}\)没有落在当前考虑的\([L_i,R_i]\)区间上，直接选择较优的转移即可
如果在\([L_i,R_i]\)区间上，考虑第\(i\)个生成器生成的数\(X\)和\(f_{i+1}\)的大小关系合并转移即可
pag
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int NN=1e6+5;
namespace AE86{
auto 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;
};
auto write=[](int x,char opt='\n'){
char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');
do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
for(short i=len-1;i>=0;--i){putchar(ch[i]);}putchar(opt);
};
}using namespace AE86;
typedef long double D;
int n,tmp;
D f[NN],d[NN];
struct node{D l,r;}s[NN];
namespace WSN{
inline short main(){
freopen("pag.in","r",stdin);
freopen("pag.out","w",stdout);
n=read();
for(int i=1;i<=n;i++){
s[i].l=read(),s[i].r=read();
d[i]=(s[i].l+s[i].r)/2;
if(s[i].l==s[i].r) ++tmp;
}
if(tmp==n){
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,(int)s[i].l);
printf("%.5lf\n",1.0*ans);
return 0;
}
f[n]=d[n];
for(int i=n-1;i;i--){
if(f[i+1]<s[i].l){
f[i]=d[i];
}else if(f[i+1]>s[i].r){
f[i]=f[i+1];
}else{
f[i]=(s[i].r-f[i+1])/(s[i].r-s[i].l)*(f[i+1]+s[i].r)/2;
f[i]+=(f[i+1]-s[i].l)/(s[i].r-s[i].l)*f[i+1];
}
}
printf("%.5Lf\n",f[1]);
return 0;
}
}
signed main(){return WSN::main();}
T3 技术情报局
比较明显是要建出大根堆笛卡尔树的，不过在\(T1\)花时间太多而且还想做\(T4\)于是就直接打了一个部分分和一个线段树走了
预计得分\(40pts\)，实际得分\(20\)，因为卡了\(O(n)\)的常，没事，正常正常。。。。。
考虑建出笛卡尔树后如何合并答案，想到原来做过的一道题斐波
没错还是他，我好像已经两次在别的博客里面拿出这套题的链接了
这道题的维护方式和他一样，那么我们只需要记录四个值就可以合并区间答案了，时间复杂度\(O(n)\)
tio
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int NN=1e7+5;
namespace AE86{
auto 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;
};
auto write=[](int x,char opt='\n'){
char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');
do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
for(short i=len-1;i>=0;--i){putchar(ch[i]);}putchar(opt);
};
auto max_=[](int a,int b){return a>b?a:b;};
auto min_=[](int a,int b){return a<b?a:b;};
}using namespace AE86;
int n,s,l,r,mod,w[NN],ans;
vector<int> sca;
namespace GenHelper {
unsigned z1, z2, z3, z4, b;
unsigned rand_() {
b = ((z1 << 6) ^ z1) >> 13;
z1 = ((z1 & 4294967294U) << 18) ^ b;
b = ((z2 << 2) ^ z2) >> 27;
z2 = ((z2 & 4294967288U) << 2) ^ b;
b = ((z3 << 13) ^ z3) >> 21;
z3 = ((z3 & 4294967280U) << 7) ^ b;
b = ((z4 << 3) ^ z4) >> 12;
z4 = ((z4 & 4294967168U) << 13) ^ b;
return (z1 ^ z2 ^ z3 ^ z4);
}
}
vector<int> get (int n, unsigned s, int l, int r) {
vector<int> a;
using namespace GenHelper;
z1 = s;
z2 = unsigned((~s) ^ 0x233333333U);
z3 = unsigned(s ^ 0x1234598766U);
z4 = (~s) + 51;
for (int i = 1; i <= n; i ++) {
int x = rand_() & 32767;
int y = rand_() & 32767;
a.push_back(l + (x * 32768 + y) % (r - l + 1));
}
return a;
}
inline int qmo(int a,int b,int ans=1){
int c=mod;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;
return ans;
}
namespace TASK{
int pw[NN];
inline void task(){
int ans=0;pw[0]=1;for(int i=1;i<=n;++i)pw[i]=w[i]*pw[i-1]%mod;
for(int i=1;i<=n;++i)ans=(ans+pw[i]*w[1]%mod*(n-i+1)%mod)%mod;
write(ans);
}
}using namespace TASK;
namespace carisian_tree{
int son[NN][2],siz[NN],stk[NN],top;
inline void build(int *a){
for(int i=1;i<=n;i++){
while(top&&a[stk[top]]<a[i]) son[i][0]=stk[top--];
if(top) son[stk[top]][1]=i;
stk[++top]=i;
}
}
struct node{
int l,r,sum,mul;
node operator+(const node&x)const{
node ret;ret.l=ret.r=ret.sum=ret.mul=0;
ret.sum=(sum+x.sum+x.l*r%mod)%mod;
ret.l=(l+mul*x.l%mod)%mod;
ret.r=(x.r+x.mul*r%mod)%mod;
ret.mul=mul*x.mul%mod;
return ret;
}
}dp[NN<<2];
inline void Dfs(int x){
dp[x]=node{w[x],w[x],w[x],w[x]};
if(son[x][0]) Dfs(son[x][0]),dp[x]=dp[son[x][0]]+dp[x];
if(son[x][1]) Dfs(son[x][1]),dp[x]=dp[x]+dp[son[x][1]];
ans=(ans+(dp[x].sum-dp[son[x][0]].sum-dp[son[x][1]].sum+mod+mod)%mod*w[x]%mod)%mod;
}
}using namespace carisian_tree;
namespace WSN{
inline short main(){
FILE *wsn=freopen("tio.in","r",stdin);
wsn=freopen("tio.out","w",stdout);
n=read();s=read();l=read();r=read();mod=read();
sca=get(n,s,l,r); int sz=sca.size();
for(int i=0;i<sz;++i) w[i+1]=sca[i];
if(l==r) return task(),0; build(w);
Dfs(stk[1]);
write(ans);
return 0;
}
}
signed main(){return WSN::main();}
T4 肯德基
莫比乌斯大白板
考场上推杜教筛的部分分用时：\(\leq 1h\)
考场上推正解用时：\(\leq 15min\)
大雾
然而考试的时候不会解决等差数列的\(/2\)要特判的问题导致没有调出来正解代码，于是。。。
然后就gg。。。。。。
非常郁闷，啊啊啊啊啊！！！！
问题实际上是求范围在\([1,n]\)内的没有平方质因子的数的总和
考虑容斥
我们枚举平方因子是哪个，最后用\(sum(n)\)减去有平方因子的数的和就是答案
那么答案就是
\(\begin{matrix} & sum(n)-\sum\limits_{d=2}^{\sqrt{n}}\sum\limits_{i=1}^{\frac{n}{d^2}}id^2 \\ & =sum(n)-\sum\limits_{d=2}^{\sqrt{n}}d^2\sum\limits_{i=1}^{\frac{n}{d^2}}i \\ & =sum(n)-\sum\limits_{d=2}^{\sqrt{n}}d^2sum(\frac{n}{d^2}) \end{matrix}\)
但其实他是不对的！！！
为什么？因为会算重。
在哪里？在一个数有多个质因子的地方，于是我们加上容斥系数\(\mu\)，他就对了，即
\(=sum(n)-\sum\limits_{d=2}^{\sqrt{n}}\mu(d)d^2sum(\frac{n}{d^2})\)
然后发现\(sum(n)\)可以直接放进大循环里算，那么答案就是
\(ans=\sum\limits_{d=1}^{\sqrt{n}}\mu(d)d^2sum(\frac{n}{d^2})\)
然后直接筛出\(\mu(d)d^2\)的前缀和数论分块即可
可能是昨天学了一天的杜教筛和莫比乌斯反演，这题确实比较白板
\(\huge{另外，如果有路过的大佬会杜教筛的部分分，请疯狂在评论区D我}\)
kfc
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int NN=10000001;
namespace AE86{
auto 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;
};
auto write=[](int x,char opt='\n'){
char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');
do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
for(short i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);
};
}using namespace AE86;
int T,n;
signed prime[NN],len;
signed mu[NN];
bool vis[NN];
int F[NN],S[NN];
inline void getprime(){
mu[1]=1; F[1]=1; S[1]=1;
for(int i=2;i<NN;++i){
if(!vis[i]) prime[++len]=i,mu[i]=-1;
for(int j=1;j<=len&&prime[j]*i<NN;++j){
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
mu[i*prime[j]]=-mu[i];
}
F[i]=(F[i-1]+mu[i]*mu[i]*i);
S[i]=(S[i-1]+i*i*mu[i]);
}
}
int ans,m;
auto id=[](int x){return n/x;};
inline int sig(int n){return ((n+1)&1) ? ((n/2)*(n+1)):((n+1)/2*n);}
auto solve=[](){
n=read();
if(n<=1e7) return write(F[n]),void();
ans=0; m=sqrt(n);
for(int l=1,r;l<=m;l=r+1){
r=max(l,(int)sqrt(n/(n/l/l)));
ans+=(S[r]-S[l-1])*sig(n/l/l);
}
write(ans);
};
namespace WSN{
inline short main(){
freopen("kfc.in","r",stdin);
freopen("kfc.out","w",stdout);
T=read(); getprime();
while(T--) solve();
return 0;
}
}
signed main(){return WSN::main();}