Simulation 87 Exam Summary

Recommended Rennames: Tlecoders

Test

Let’s look at it, four questions, three questions, 淦
In explosion$$998244353$$After the game, I finally saw the linearity of the expectations, so 15 minutes took T1 seconds, followed by T2, I found it very water after I found out, just in seconds, then just an hour, feel To take off, then T3 is not found. . .
Fortunately, the data is random, so I started a chaotic, I judged a special nature, I feel that the guarantee 60 does not panic, open T4 is a number, first half an hour, YY, linear screen, suddenly discovered that this is the previous one The title is very similar, so I want to enumerate the square factor, and then a wave of surrogate, the same example! ! ! Holding, 80
So expected to score 100 + 100 + [60-80] + 80 = [340-360], the remaining basic inspection
Silver, T1#define int long longThat is often 60, T2 accuracy is cardd 75 …
In short, the participating experience is very poor

T1.Collection meanCard regular

Directly expand, equivalent to putting the average number of the right side to the left, set average$$p$$. The answer is

$ans=\sum_{i=1}^{n\times m}\frac{i\times p}{i+1}$

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int N=100050;
int a[N],m,n,inv[200*N];
signed main()
{
freopen("mos.in","r",stdin);
freopen("mos.out","w",stdout);
cin>>n>>m;int sum=0;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)sum=(1ll*sum+a[i])%mod;
inv=1;for(int i=2;i<=n*m+10;i++)inv[i]=(1ll*mod-mod/i)*inv[mod%i]%mod;
sum=1ll*sum*inv[n]%mod;int ans=0;
for(int i=1;i<=n*m;i++)ans=(1ll*ans+1ll*sum*i%mod*inv[i+1]%mod)%mod;
cout<<ans<<endl;
return 0;
}

T2.Polyalkylene glycolFrying

Simulation from the post, set$$ans$$Initial 0
For current random number generators$$i$$Substitution discussion
If there is no current excellent, that is,$$ans<=l_i$$If you want to be the current,$$ans=(l_i+r_i)/2$$
If the back is completely excellent,$$ans>=r_i$$No matter the current, directcontinue
Otherwise, be sure to be in the current interval, then the strategy is if the number behind this selection will go back later, otherwise, the current, then the answer is

$ans=\frac{ans-l_i}{2}\times \frac{ans-l_i}{r_i-l_i}+\frac{ans+r_i}{2}\times \frac{r_i-ans}{r_i-l_i}$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
const int N=1000050;
const double exs=1e-15;
inline bool pd(double x,double y)
{
if(x<y)swap(x,y);
if(x-y<exs)return 1;
return 0;
}
int l[N],r[N],n;
signed main()
{
freopen("pag.in","r",stdin);
freopen("pag.out","w",stdout);
double ans=0.0;
for(int i=n;i>=1;i--)
{
if(ans<l[i]||pd(ans,l[i])){ans=(1.0*l[i]+r[i])/2.0;continue;}
if(ans>r[i]||pd(ans,r[i]))continue;
double p=(ans-l[i])/(1.0*r[i]-l[i]);
ans=ans*p+(1.0-p)*((1.0*r[i]+ans)/2.0);
}
printf("%.5Lf",ans);
return 0;
}

t3. Technical Information Bureau

I really don’t know how this is coming.
Building a big rootcindler tree, each node maintained the product of the current interval prefix, the sum of the suffixes, the area, then DFS over again and again

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+10;
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);
}
}
int a[N],ls[N],rs[N],root;
void get(int n,unsigned s,int l,int r)
{
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[i]=l+(x*32768+y)%(r-l+1);
}
}
int n,s,l,r,mod,ans;stack <int> st;
int sum[N],p1[N],p2[N];
void dfs(int x)
{
if(ls[x])dfs(ls[x]);
if(rs[x])dfs(rs[x]);
ans=(ans+(p2[ls[x]]*p1[rs[x]]%mod*a[x]%mod+(p1[rs[x]]+p2[ls[x]])%mod*a[x]%mod+a[x])%mod*a[x]%mod)%mod;
p1[x]=(p1[ls[x]]+(p1[rs[x]]+1)*((ls[x]?sum[ls[x]]:1ll)*a[x]%mod)%mod)%mod;
p2[x]=(p2[rs[x]]+(p2[ls[x]]+1)*((rs[x]?sum[rs[x]]:1ll)*a[x]%mod)%mod)%mod;
sum[x]=(ls[x]?sum[ls[x]]:1)*(rs[x]?sum[rs[x]]:1)%mod*a[x]%mod;
}
signed main()
{
freopen("tio.out","w",stdout);
freopen("tio.in","r",stdin);
cin>>n>>s>>l>>r>>mod;
get(n,s,l,r);
for(int i=1;i<=n;i++)
{
int p=0;
while(st.size()&&a[st.top()]<a[i])p=st.top(),st.pop();
if(st.size())rs[st.top()]=i;
if(p)ls[i]=p;st.push(i);
}
while(st.size()>1)st.pop();root=st.top();
dfs(root);cout<<ans<<endl;
return 0;
}

T4. KFC

When do you have not contributed, it is a number of square factors.
So we want to remove the square factors, because the upper industry is$$\sqrt n$$So, you can, because it is necessary to rendezon, thinking that the practical significance of the Mobius function will find that the retention coefficient is$$\mu$$$$g(x)=\sum_{i=1}^x i$$Then the answer is

$\sum_{i=1}^{\sqrt n}i^2\times \mu(i)\times g(\lfloor \frac{n}{i^2}\rfloor)$

In fact, it can be divided into the number of blocks, only about three roots.$$n$$Value, so

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N=10000050;
int p[N],tot,mu[N],f[N];bool v[N];
inline int get(int x)
{
if(x&1)return ((x+1)>>1)*x;
else return (x>>1)*(x+1);
}
signed main()
{
freopen("kfc.in","r",stdin);
freopen("kfc.out","w",stdout);
mu=1;
for(signed i=2;i<=1e7+10;i++)
{
if(!v[i]){p[++tot]=i;mu[i]=-1;}
for(signed j=1;j<=tot&&p[j]*i<=1e7+10;j++)
{
v[i*p[j]]=1;
if(i%p[j]==0){mu[p[j]*i]=0;break;}
else mu[p[j]*i]=-mu[i];
}
}
for(int i=1;i<=1e7+10;i++)f[i]=f[i-1]+mu[i]*i*i;
int t;cin>>t;
for(int i=1;i<=t;i++)
{
int x;scanf("%llu",&x);
int ans=0,lim=sqrt(x);
for(int l=1,r;l<=lim;l=r+1)
{
r=min((int)sqrt(x/(x/(l*l))),lim);
ans+=(f[r]-f[l-1])*get(x/(l*l));
}
printf("%llu\n",ans);
}
return 0;
}

Summary of the exam

Retreat the problem of small details again, if you think that it is best to let the influence data
The foundation is still a prison, the board will not write, the problem has not been thinking
So should be stable, don’t lose every point

• Top