10.27上午解题报告

清北学堂 解题报告

---

各题状况

期望得分：$100+80+0$
实际得分：$100+30+0$

T1

推了半小时的因式分解，发现不会，又感觉暴力的复杂度没啥问题，就敲了个暴力扔那不管了
精度问题。。。不在考虑范围内
（虽然我交了两份代码一个$e$是小数点后$9$位一个$e$是小数点后$7$位）

T2

总共写了2小时，期间零零碎碎大概用了半小时写注释（毕竟自己记性差没法怪别人。。。）
最后居然写了$34$行还是第四第五种状况不想讨论了的结果
耶
然后就因为忘记讨论模数和分子分母的情况成功挂成暴力分
气到炸裂

T3

最后剩下$10$分钟的时候想到这题是线段树
然后就。。。放弃

题目及考场代码

T1

/*
 * ...
 * 推了半小时的公式转化
 * 然后TM。。。放弃了
 * 毕竟后面几个题都是数学题
 * 这个题。。。写个暴力滚粗
 * 反正N<=100
 * 精度误差。。。不在考虑范围内
 * (屡教不改.jpg)
 */
#include <cstdio>
#include <cmath>
const int N=101;
const long double e=2.7182818;
long double s[N],emp,pk;
int n,k;
int main()
{
    freopen("r.in","r",stdin);
    freopen("r.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)scanf("%Lf",&s[i]);
    for(int i=1;i<=n;++i)emp+=pow(e,s[i]);
    pk=pow(e,s[k])/emp;
    printf("%.5Lf",log(emp)-pk);
    fclose(stdin);fclose(stdout);
    return 0;
}

T2

/*
for(int i=1;i<=n;++i)
    for(int j=0;j<=k;++j)
        ans+=(n/i)*pow(i,j)%mod;
以上是直接通过题面得出的模拟代码，循环的嵌套顺序不影响结果
for(int j=0;j<=k;++j)
    for(int i=1;i<=n;++i)
        ans+=(n/i)*pow(i,j)%mod;
显然当k=0的时候，就是求个整除分块
for(int l=1,r;l<=n;l=r+1)
{   
    r=n/(n/l);
    ans+=(r-l+1)*(n/l);
}
对于n/l，有r-l+1次贡献
而推广到k=1，考虑到乘法分配律
对于连续的一块，(n/l)*(1+l)+(n/l)*(1+l+1)+...+(n/l)*(1+r)
也就是(n/l)*((1+l)+(1+l+1)+(1+l+2)+...+(1+r))
后面的式子可以变成((r-l+1)+r*(r+1)/2-(l-1)*l/2)
整理：(n/l)*((r-l+1)+(r*(r+1)/2-(l-1)*l/2))
再推广到k=2，考虑到乘法分配律和平方和公式。。。
(n/l)*(1+l+l*l)+(n/l)*(1+l+1+(l+1)*(l+1))+...+(n/l)*(1+r+r*r)
平方和公式：1*1+2*2+...+n*n=n*(n+1)(2*n+1)/6
那么也就是((r-l+1)+(r*(r+1)/2-(l-1)*l/2)+(r*(r+1)(2*r+1)/6-(l-1)*l*(2*(l-1)+1)/6)
整理：(n/l)*((r-l+1)+(r*(r+1)/2-(l-1)*l/2)+(r*(r+1)(2*r+1)/6-(l-1)*l*(2*l-1)/6)
然后是立方和公式。。。。
1^3+2^3+...+n^3=(n*n*(n+1)*(n+1))/4
4次方和公式
1^4+2^4+...+n^4=n*(n+1)*(2*n+1)*(3*n^2+3*n-1)/30
10:50调出来
爽翻
有点害怕会爆掉。
 */
#include <cstdio>
long long n,ans,emp,l,r,x,sum;
int m,k;
const int mod=1e9+7;
int main()
{
    freopen("q.in","r",stdin);
    freopen("q.out","w",stdout);
    int T;scanf("%d",&T);
    while(T--)
    {
        ans=0;
        scanf("%lld%d%d",&n,&m,&k);
//      m=1e9+7;
//      printf("%lld %d %d\n",n,m,k);
        for(l=1;l<=n;l=r+1)
        {
            x=n/l,r=n/x;x%=m;
//          ans+=(r-l+1)*(n/l);
            sum=(r-l+1);
//          printf("%lld ",sum);
            if(k<1)goto E;
            sum=(sum+r*(r+1)/2-(l-1)*l/2)%m;
            if(k<2)goto E;
            sum=(sum+r*(r+1)*(2*r+1)/6-(l-1)*l*(2*l-1)/6)%m;
            if(k<3)goto E;
            sum=(sum+((r*r*(r+1)*(r+1)/4)%m-((l-1)*(l-1)*l*l/4)%m))%m;
            if(k<4)goto E;
            sum=(sum+r*(r+1)*(2*r+1)*(3*r*r+3*r-1)/30-(l-1)*l*(2*l-1)*(3*(l-1)*(l-1)+3*(l-1)-1)/30)%m;
E:          emp=x*sum%m;
            ans=(ans+emp)%m;
//          printf("%lld\n",sum);
        }
        printf("%lld\n",ans);
    }
    fclose(stdin),fclose(stdout);
    return 0;
}

T3

/*
 * 线段树？
 * 还剩30分钟，自闭了
 * 耶
 */
#include <cstdio>
inline int read()
{
    int n=0,w=1;register char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n*w;
}
struct Segment_Tree{
};
int main()
{
    freopen("y.in","r",stdin);
    freopen("y.out","w",stdout);
    printf("26\n16");
    fclose(stdin);fclose(stdout);
    return 0;
}

正解及代码

T1

暴力算就行了

随便做，送分题

这里给出正解的思路：

cmath库中有三个函数，pow(x,y)，log(x)，exp(x)，第一个是求$x^y$，第二个是求$\ln x$，第三个是求$e^x$

三个函数按照题目模拟求出$p^k$以及$\sum_{i=1}^{n}e^{s[i]}$即可

#include <cstdio>
#include <cmath>
const int N=101;
const long double e=2.7182818;
long double s[N],emp,pk;
int n,k;
int main()
{
    freopen("r.in","r",stdin);
    freopen("r.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)scanf("%Lf",&s[i]);
    for(int i=1;i<=n;++i)emp+=pow(e,s[i]);
    pk=pow(e,s[k])/emp;
    printf("%.5Lf",log(emp)-pk);
    fclose(stdin);fclose(stdout);
    return 0;
}

T2

给出的公式是这个样子

$$\sum_{i=1}^{N}\sum_{j=0}^{K} i^j\times \lfloor\frac{N}{i}\rfloor$$
考虑当$k=0$的时候是一个经典的问题：整除分块

这里仅仅简单提一下这个东西：

考虑$\lfloor\frac{N}{i}\rfloor$会在$i=1\sim N$中出现$\lfloor\frac{N}{\lfloor\frac{N}{i}\rfloor}\rfloor$次，所以会对$\lfloor\frac{N}{i}\rfloor$对答案有$\lfloor\frac{N}{\lfloor\frac{N}{i}\rfloor}\rfloor$的贡献

假设$\lfloor\frac{N}{l}\rfloor=\lfloor\frac{N}{r}\rfloor \;and\; \lfloor\frac{N}{r+1}\rfloor\ne \lfloor\frac{N}{l}\rfloor$，那么for的时候直接算出来$ans+=(r-l+1)\times \lfloor\frac{N}{i}\rfloor$然后迭代器直接从$l$跳到$r$就行了

以上就是整除分块的内容。。。

代码非常好实现，看我考场T2注释就行了

考虑对公式的转化：

对于分的$\lfloor\frac{N}{i}\rfloor$相同的每一块考虑计算$\sum_{i=l}^r\sum_{j=0}^k \lfloor\frac{N}{i}\rfloor\times i^j$

假设$x=\lfloor\frac{N}{i}\rfloor$，那么就有

$$x\sum_{i=l}^r\sum_{j=0}^k i^j$$

展开变成：

$$x\sum_{i=l}^r(1+i+i^2+\cdots+i^k)\\ x(r-l+1)\left(\sum_{i=l}^r i\right)\left(\sum_{i=l}^ri^2\right)\left(\sum_{i=l}^ri^3\right)\left(\sum_{i=l}^ri^4\right)$$
对于后面的四个sigma，这样写看起来不是很方便，我们可以拆开
$$\sum_{i=l}^r i=\sum_{i=1}^r i -\sum_{i=1}^{l-1} i\\ \sum_{i=l}^r i=\sum_{i=1}^r i^2-\sum_{i=1}^{l-1} i^2$$
其他同理

也就是说，我们需要平方和公式，立方和公式以及四次方和公式

**baidu**可以知道

$$1+2+\cdots +n=\frac{n(n+1)}{2}\\ 1^2+2^2+\cdots +n^2=\frac{n(n+1)(2n+1)}{6}\\ 1^3+2^3+\cdots +n^3=\left(\frac{n(n+1)}{2}\right)^2=\frac{n^2 (n+1)^2}{4}\\ 1^4+2^4+\cdots +n^4=\frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}$$

在清北的考试是不断网的。
就算平方和的背过了，那考场上应该怎么推立方和、四次方和的公式呢？

已知有这样一个公式
$1^k+2^k+\cdots +n^k=a_{k+1}n^{k+1}+a_{k}n^{k}+\cdots +a_{1}n^{1}+a_0$

也就是说$k$方和的公式是一个有$k+2$个未知数的多项式方程

所以我们考虑写出来$k+2$个不同的多项式方程然后高斯消元求解

考场上可以这么暴力地求，毕竟手推公式不是所有人都能做到

但是还有一件要考虑的事情。。。

$N\le 10^{10}$长者本来是想开$10^{18}$的

也就是说，在上面的某个过程会爆long long

一个显然的想法是在各种乘法都加一个$mod$

但是很不幸$m$不一定是质数并且$mod$不具有同除性

回顾上面几个公式

可以发现，前三个是一定可以把分子分母约掉的（$n$和$n+1$一定有一个是偶数，$n,n+1$和$2n+1$里面一定有一个是$3$的倍数，不能保证$3n^2+3n-1$有$6$的因子）

所以前三个公式可以通过讨论将分母先处理掉然后再$mod$

而对于第四个公式$/30$，可以考虑对模数$m$进行某种操作使得$mod$之后依然能够整除$30$

这时一个$dalao$给出了一个思路：把模数乘以$30$！

这样确实是可以的，因为这样操作之后我们可以保证$mod$之后的值至少对$2,3,5$这几个质因子

那么本题的细节就愉快地讨论完了

#include <cstdio>
long long n,ans,emp,l,r,x,sum;
int m,k;
const int mod=1e9+7;
long long calc1(long long x)
{
    long long y=x+1;
    if(x&1)y>>=1;
    else    x>>=1;
    return x*y;
}
long long calc2(long long x)
{
    long long y=x+1,z=2*x+1;
    if(x%3==0)x/=3;
    else
    {
        if(y%3==0)y/=3;
        else    z/=3;
    }
    if(x&1)y>>=1;
    else    x>>=1;
    return x*y*z;
}
int main()
{
    freopen("q.in","r",stdin);
    freopen("q.out","w",stdout);
    int T;scanf("%d",&T);
    while(T--)
    {
        ans=0;
        scanf("%lld%d%d",&n,&m,&k);
//      m=1e9+7;
//      printf("%lld %d %d\n",n,m,k);
        for(l=1;l<=n;l=r+1)
        {
            x=n/l,r=n/x;x%=m;
//          ans+=(r-l+1)*(n/l);
            sum=(r-l+1);
//          printf("%lld ",sum);
            if(k<1)goto E;
            sum=(sum+calc1(r)%m-calc1(l-1)%m+m)%m;
            if(k<2)goto E;
            sum=(sum+calc2(r)%m-calc2(l-1)%m+m)%m;
            if(k<3)goto E;
            sum=(sum+(calc1(r)%m*calc1(r)%m-calc1(l-1)%m*calc1(l-1)%m)+m)%m;
            if(k<4)goto E;
            m*=30;
            sum=(sum+calc2(r)%m*(3*r*r+3*r-1)%m/30-calc2(l)%m*(3*(l-1)*(l-1)+3*(l-1)-1)%m/30+m)%m;
E:          emp=x*sum%m;
            ans=(ans+emp)%m;
//          printf("%lld\n",sum);
        }
        printf("%lld\n",ans);
    }
    fclose(stdin),fclose(stdout);
    return 0;
}

T3

对于操作二、三可以看做是线段树维护区间加一个等差数列以及求区间和
换句话说，可以把每次操作看做往一段区间上面扔这样的线段

假设每次放上去的等差数列看成线段，那么图上表现得更高的线段会覆盖低的线段（高低反映相对大小）
那么操作四就是对每个点维护已经覆盖过当前点的最高值是多少
考虑可能出现三种更新情况

这两种情况可以直接对覆盖的区间全部选择丢掉小的，留下大的

但是对于上面这种情况就无法全部舍弃或者保留了
考虑像线段树的下传一样分区间进行操作，考虑对于分出来的区间能否直接判断

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
const int BUF_SIZE = 30;
char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1;
#define PTR_NEXT() \
    { \
        buf_s ++; \
        if (buf_s == buf_t) \
        { \
            buf_s = buf; \
            buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); \
        } \
    }
#define readint(_n_) \
    { \
        while (*buf_s != '-' && !isdigit(*buf_s)) \
            PTR_NEXT(); \
        bool register _nega_ = false; \
        if (*buf_s == '-') \
        { \
            _nega_ = true; \
            PTR_NEXT(); \
        } \
        int register _x_ = 0; \
        while (isdigit(*buf_s)) \
        { \
            _x_ = _x_ * 10 + *buf_s - '0'; \
            PTR_NEXT(); \
        } \
        if (_nega_) \
            _x_ = -_x_; \
        (_n_) = (_x_); \
    }
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=100010;
const int mo=1000000007;
int n,m;
struct node
{
    int l,r;
    int v1;
    int col1_a,col1_b;
    int v2;
    int col2_a,col2_b;
    node(){
        v1=v2=0;
        col1_a=col1_b=0;
        col2_a=col2_b=0;
    }
}z[maxn<<2|1];
void build(int l,int r,int rt)
{
    z[rt].l=l;z[rt].r=r;
    if (l==r) return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
void modify1(int l,int r,int rt,int nowl,int nowr,int A,int B);
void col1(int rt,int A,int B)
{
    if (z[rt].col1_a || z[rt].col1_b)
    {
        int a1=A,b1=B;
        int a2=z[rt].col1_a,b2=z[rt].col1_b;
        if (a1<a2) swap(a1,a2),swap(b1,b2);
        int s=z[rt].r-z[rt].l;
        int r1=a1+b1*s;
        int r2=a2+b2*s;
        if (r1>=r2)
        {
            z[rt].col1_a=a1;
            z[rt].col1_b=b1;
        }
        else
        {
            int p=(a1-a2)/(b2-b1);
            while (a1+b1*p>=a2+b2*p)
                p++;
            //printf("%d %d %d\n",z[rt].l,z[rt].r,p);
            modify1(z[rt].l,z[rt].r,rt,z[rt].l,z[rt].l+p-1,a1,b1);
            modify1(z[rt].l,z[rt].r,rt,z[rt].l+p,z[rt].r,a2+p*b2,b2);
        }
    }
    else
    {
        z[rt].col1_a=A;
        z[rt].col1_b=B;
    }
}
void col2(int rt,int A,int B)
{
    int s = z[rt].r-z[rt].l+1;
    z[rt].v2 = (z[rt].v2 + (long long)s*A + (long long)s*(s-1)/2%mo*B)%mo;
    z[rt].col2_a += A;
    if (z[rt].col2_a>=mo) z[rt].col2_a -= mo;
    z[rt].col2_b += B;
    if (z[rt].col2_b>=mo) z[rt].col2_b -= mo;
}
void push_col(int rt)
{
    if (z[rt].col2_a || z[rt].col2_b)
    {
        int m=(z[rt].l+z[rt].r)>>1;
        int A=z[rt].col2_a;
        int B=z[rt].col2_b;
        col2(rt<<1,A,B);
        col2(rt<<1|1,(A+(long long)B*(m+1-z[rt].l))%mo,B);
        z[rt].col2_a=0;
        z[rt].col2_b=0;
    }
}
void modify1(int l,int r,int rt,int nowl,int nowr,int A,int B)
{
    if (nowl<=l && r<=nowr)
    {
        col1(rt,(l-nowl)*B+A,B);
        return;
    }
    int m=(l+r)>>1;
    if (nowl<=m) modify1(lson,nowl,nowr,A,B);
    if (m<nowr) modify1(rson,nowl,nowr,A,B);
}
void modify2(int l,int r,int rt,int nowl,int nowr,int A,int B)
{
    if (nowl<=l && r<=nowr)
    {
        col2(rt,((l-nowl)*B+A)%mo,B);
        return;
    }
    push_col(rt);
    int m=(l+r)>>1;
    if (nowl<=m) modify2(lson,nowl,nowr,A,B);
    if (m<nowr) modify2(rson,nowl,nowr,A,B);
    z[rt].v2=z[rt<<1].v2+z[rt<<1|1].v2;
    if (z[rt].v2>=mo) z[rt].v2-=mo;
}
int query2(int l,int r,int rt,int p,int nowv=0)
{
    nowv=max(nowv,(p-z[rt].l)*z[rt].col1_b+z[rt].col1_a);
    if (l==r) return (nowv+z[rt].v2)%mo;
    push_col(rt);
    int m=(l+r)>>1;
    if (p<=m) return query2(lson,p,nowv);
    else return query2(rson,p,nowv);
}
int query1(int l,int r,int rt,int nowl,int nowr)
{
    if (nowl<=l && r<=nowr) return z[rt].v2;
    push_col(rt);
    int m=(l+r)>>1;
    int ans=0;
    if (nowl<=m) ans=query1(lson,nowl,nowr);
    if (m<nowr) ans+=query1(rson,nowl,nowr);
    if (ans>=mo) ans-=mo;
    return ans;
}
int main()
{
    readint(n);
    readint(m);
    build(root);
    for (int a=1;a<=m;a++)
    {
        //printf("%d\n",a);
        int opt;
        readint(opt);
        if (opt==1)
        {
            int l,r,A,B;
            readint(l);
            readint(r);
            readint(A);
            readint(B);
            modify1(root,l,r,A,B);
        }
        if (opt==2)
        {
            int l,r,A,B;
            readint(l);
            readint(r);
            readint(A);
            readint(B);
            modify2(root,l,r,A,B);
        }
        if (opt==3)
        {
            int l,r;
            readint(l);
            readint(r);
            printf("%d\n",query1(root,l,r));
        }
        if (opt==4)
        {
            int p;
            readint(p);
            printf("%d\n",query2(root,p));
        }
    }
    return 0;
}

讲烂了的一些东西

1. Dev自动补全库，本地AC提交CE

   1. 可以先把平时常用的库全写上（反正编译时间不算在运行时间内），你写五十行的include也不会有人管你
   2. bits/stdc++.h尽量不要用，因为NOIP一直没有明确说明能不能用
   3. 放弃Dev，或者至少在最后要脱离Dev编译一次代码（注意如果机器上其他地方有MinGW就不要用Dev里面的）

2. 几个变量名，是雷区

   1. x1,x2,y1,y2,next是algorithm(cmath)库里面已经定义过了的
   2. 解决方法：大写或在所有用到的变量名后面都加个下划线或随机字符（对象的名字或自己的名字）

3. long double

   1. 读入时应当声明一个double类型，scanf("%lf",&);然后把这个读入的值赋给long double的变量；输出时则是先把long double赋给一个double然后printf("%lf",);

      这样根本不会有什么问题因为输入输出的时候不会对原值做任何操作导致爆double，该爆只会在中间操作的时候爆

   2. cmath里面的pow是double类型的，exp也是；想用long double的函数一般可以在后面加个$l$，比如powl,expl之类

4. 暴力写对啊。。。。提升代码能力