省常中联测题选VIII HGOI1027【转自xrr】

T1 fht

给出N和M,求出$$\sum_{i=1}^{N}\sum_{j=1}^{M} (N Mod i)\ast(M Mod i)$$

我们可以发现首先这个公式可以变形成$$(\sum_{i=1}^{N} N Mod i)\ast(\sum_{j=1}^{M} M Mod j)$$

然后就变成了求余数的和

然后,我们将$$N Mod i$$写成$$N-\lfloor\frac{n}{i}\rfloor \ast i$$

再之后,我们将这个变形的模式写进求和式就变成了

$$(\sum_{i=1}^{N}N-\lfloor\frac{n}{i}\rfloor \ast i)\ast(\sum_{j=1}^{M}M-\lfloor\frac{n}{i}\rfloor \ast i)$$

然后改变一下求和式的求和内外符号,就可以变成

$$(N^{2}-\sum_{\lfloor \frac{n}{i} \rfloor=1}^{n}(\lfloor \frac{n}{i} \rfloor \ast\sum_{i=n/(\lfloor \frac{n}{i} \rfloor-1)+1)}^{n/\lfloor \frac{n}{i} \rfloor}i) )$$

$$M$$的就不说了,和$$N$$一样,虽然这个式子变成了一个可以等差数列求和的式子

但我们如果枚举$$\lfloor \frac{n}{i} \rfloor$$,那么有是一个$$O(n)$$算法

仔细的看看,会发现,当$$\lfloor \frac{n}{i} \rfloor$$大于$$\sqrt{n}$$是很多时候是没有值的,所以我们将这些值分开

当$$\lfloor \frac{n}{i} \rfloor$$大于$$\sqrt{n}$$时,$$i$$会小于$$\sqrt{n}$$,这时候明显暴力枚举更优

这样子能把$$O(n)$$优化为$$O(\sqrt{n})$$

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,m;
long long sumn,summ;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=sqrt(n);i++){
        int st=n%(n/i),en=n%(n/(i+1)+1);
        sumn=(sumn+1ll*(st+en)*((en-st)/i+1)/2)%mod;
    }
    for(int i=1;i<=(n/(int)(sqrt(n)+1));i++) sumn=(sumn+n%i)%mod;
    for(int i=1;i<=sqrt(m);i++){
        int st=m%(m/i),en=m%(m/(i+1)+1);
        summ=(summ+1ll*(st+en)*((en-st)/i+1)/2)%mod;
    }
    for(int i=1;i<=(m/(int)(sqrt(m)+1));i++) summ=(summ+m%i)%mod;
    printf("%d",summ*sumn%mod);
}

T2 phantom

给出n个点,每个点都有一定概率出现,连在一起的x个点会有x^2的得分,求出最终的得分期望

emmm,这道题被我乱搞搞过了。。。

因为$$n\leqslant1000000$$ 所以当连在一起的概率乘上得分小于一定值时基本可以忽略,即$$dp[i]\leqslant1e-12$$即以上是就可以忽略

为了保证算法正确性(这种卡精度的东西本来就没什么正确性),可以将$$1e-12$$缩小到$$1e-16$$,就可以完美的完爆这道题

好,下面讲一下正解

我们加上一个辅助数组$$g[i]$$表示期望长度,然后直接做就行了

这里放上乱搞搞的暴力代码

#include<bits/stdc++.h>
using namespace std;
int n,a[1000010],maxl;
double dp[1000010],sum[1000010];

int read(){
    int u=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') u=(u<<1)+(u<<3)+c-'0',c=getchar();
    return u;
}

int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    dp[0]=1.0;
    for(int i=1;i<=n;i++){
        ++maxl;
        for(int j=maxl;j>=1;j--)
            dp[j]=dp[j-1]*a[i]/100,sum[i]+=dp[j]*(sum[i-j-1]+j*j);
        dp[0]=(double)(100-a[i])/100;
        sum[i]+=sum[i-1]*dp[0];
        while(dp[maxl]<=1e-15) maxl--;
    }
    printf("%.1lf",sum[n]);
}

T3 sherco

给出一棵树,问有多少种方法将它分成多个节点数相等的子树

emm,易证,当子树的孩子数是子树节点数的倍数的个数和分开后子树的数量相等时就能成立。

所以我们就先大法师一遍做出所有的孩子数,然后枚举所有$n$的因子

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int n,x,y,sum[1000010],cnt,fa[1000010],cc,p[2000],cccc;
int hed[2000010],nex[2000010],vt[2000010],pre[2000010],ccc;
int read(){
    int u=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') u=(u<<1)+(u<<3)+c-'0',c=getchar();
    return u;
}

void add(int x,int y){
    vt[++ccc]=y,nex[ccc]=hed[x],pre[hed[x]]=ccc,hed[x]=ccc;
    vt[++ccc]=x,nex[ccc]=hed[y],pre[hed[x]]=ccc,hed[y]=ccc;
}

void dfs(int u){
    for(int i=hed[u];i!=0;i=nex[i]){
        if(vt[i]==fa[u]) continue;
        fa[vt[i]]=u,dfs(vt[i]),sum[u]+=sum[vt[i]];
    }
    sum[u]++;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y);
    for(int i=2;i<=sqrt(n);i++)
        if(n%i==0){
            if(i!=n/i) p[cccc++]=(n/i);
            p[cccc++]=i;
        }
    p[cccc++]=1;
    if(n!=1) p[cccc++]=n;
    int cntt=0;
    dfs(1);
    for(int j=0;j<cccc;j++){
        cnt=0;
        for(int i=1;i<=n;i++) if(sum[i]%p[j]==0) cnt++;
        cntt+=(cnt==n/p[j]);
    }
    printf("%d",cntt);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注