2018.6.6清北学堂学习笔记

清北学堂 数论

Day1

---

本人博客

上午考试。。

T1

给一个数字串S,如果可以划分成两个部分使得且是完全立方数,则称该划分是一个好划分。
若一个数字串有至少两个好划分,则称为膜法串,输出一个N位的膜法串

写了 2.5 h,期间无数次推翻自己先前的结论,感觉自己这波操作真的炸裂。。
最后写出来了30%的$n\le10$跟50%的$n\le50$中的……一部分

好像找到个规律?
$S_{n+3} = S_n+"000"$

我打的表能过$n \le 20$QwQ
其他的只能听天由命了。。

T3

若一个数的奇数位之和与偶数位之和的最大公约数均大于0且不超过K,则称其为幸运数。求在L~R有多少幸运数。
$L,R \le 10^{18}$

写完T1之后,听wby说T3好像暴力很好写的样子,于是先看了T3
。。
暴力敲完滚去看T2

T2

把1~n共n个数分为$\frac{n}{2}$组，每组两个元素,定义每组的权值为所选取的两个元素之和,求划分的最大权值的期望。
$N\le 5 \times 10^5$

数学期望啊…………
并不会
但是看了老师在群里面的讲解,感觉这题一脸可做啊qwq
emmmmmm
最后剩下的50 min把T2敲出来了
感觉还行。

但是wby这货最后奶了我一口mmp
更加怀疑自己能不能A了

----------

下午

• 中午去吃饭的时候晚了会儿,被讲课老师拉着查了一波户口。
• 具体就是问了下这两天的授课内容听过多少,目前会多少,感觉今天上午的题目怎么样等等
• 最后他一脸绝望地说:"完了我准备下午讲的内容好像太简单了"
• qwq老师您真的想多了[1]

题目讲解

T1

100分,规律蒙对了
那这几天就不宜开卡包开补给了qwq

$n\le4$时无解
如果S是一个魔法串,那么S后面坠3个0也是一个魔法串(原来的B后面多三个0,B/A后面也多三个0,再开立方根后面就多一个0)
所以只需要求出来5,6,7时的S,后面输出的时候在后面多坠0就好了
这样可以拿50左右
100%的话就先打个表,然后输出

T2

WA 0
果然被wby给奶死了QAQ 下回坑他顿饭

考虑枚举答案是否$\ge v$
转化成答案是否$\le v$

$$\sum_{v}(p_v-p_{v-1})v$$
把$1-n$分成两部分,一部分是$>\frac{v}{2}$的,一部分是$\le \frac{v}{2}$的
显然$>\frac{v}{2}$的只能和$\le\frac{v}{2}$的匹配
我们从大到小枚举$>\frac{v}{2}$的部分,每次都有$v-n$种选择,故方案数为
$$(v-n)^{n-\frac{v}{2}}$$
剩下的部分是一个完全图,令$f(x)$为$x$个点的方案数,$f(x)$为$1 \times 3 \times 5 \times \cdots \times (x-1)$
预处理阶乘后可以$O(nlogn)$进行计算。

T3

10分
写的第一个10%的部分分
分块打表可以拿30(吕老师跟我说他分块打表能拿60)[2]
对于$k==1$的显然
然而考试的时候太急了没看到有k==1的部分分,┭┮﹏┭┮

这类数位统计的题目做法是很典型的
首先,计算$l \le x \le r$的答案可以换成计算$1 \le x \le r$的答案,然后做差
统计:将不超过N的数按与N的公共前缀长度分类
比如N = 1234,分成0xxx,10xx,11xx,120x,121x,122x,1230,1231,1232,1233,1234
这样,不超过 N 的数被分成约 9*logN 类
对每类数***xxx,前缀部分的奇数,偶数位的和已知,而后面的各数位可以任意填写
可以枚举后面的奇数,偶数位的和,直接计算
需要一遍背包预处理F[i][s]表示i个数字和等于s的方案数
复杂度$O(T*9^3*log^4R)$能得60分
结合题目多组数据的特点,需要要进一步压缩重复计算
设状态DP(i,k,s0,s1)表示还有i个数位没有填写,已填写的与i同奇偶的数位和等于s0,不同奇偶的数位和等于s1,K=k时的方案数
转移

$$DP[i][k][s0][s1]=\sum_{d=0}^9 DP[i-1][k][s1-d][s0]$$
预处理以后,每组数据只需枚举一遍每类前缀的数,O(1)计算答案
总复杂度为$O(9^4*log^4R+T*9*logR)$。

---

讲课内容

首先是几个数学问题
1.汉诺塔
$T_1 = 1$
$T_2 = 3$
$T_3 = 7$

$T_n = 2*T_{n-1}+1$
$T_k = 2^k-1$
运用数学归纳法写成封闭式[3]:
$T_{k+1} = 2*T_k+1=2*(2^k-1)+1=2^{k+1}-1$
$Tn = 2^n-1$

• 找规律是不完全归纳法

变形1:假设只能在相邻的两根柱子移动,不能在A,C之间移动
$T_1=2$(A->B,B->C)
$T_2=8$(A->B,B->C,A->B,C->B,B->A,B->C,A->B,B->C)
$T_k=3*T_{k-1}+2$
$T_k=3^k-1$
运用数学归纳法:
$T_{k+1}=3*T_k+2=3*(3^k-1)+2=3^{k+1}-1$

变形2:
Alice和Bob玩汉诺塔,Alice希望Bob从初始状态到末状态的挪动次数最大,求最大挪动次数时的初状态和末状态

定义初始状态为a,末状态为b,原始的汉诺塔问题初始状态为A,末状态为B
若b==B,那么只有当a==A的时候,挪动次数最大
(因为此时的ans= A->a->b = A到B的次数减去A到a的次数)

考虑如果b!=B
那么ans=A->a->b->B
所以无论如何最原始的都是最大挪动

2.线分面
有n条直线,最多可以将平面分成多少个区域

每加一条直线最多会将所经过的每个平面分成两个部分[4]
可以发现如果加直线的时候经过之前已经存在的某个交点,答案不会比不经过交点更优
所以加第n条直线时会多加n个面
即:f(n)=f(n-1)+n [5]
运用数学归纳法:
f(n+1)=n*(n+1)/2
f(n)=1+2+...+n

变形:有一个只有一个折点的线折线与其他只有一个折点的折线相交,最多有多少面?

考虑每个折线都与其他的折线有两个交点
$F_n=F_{n-1}+4\times n$
也可以考虑亏损:$F_n=F_{2n}-2\times n$

然后老师就去讲课表内容了qwq

3.课表内容
快速幂
二进制分解求$a^b \mod p$
若$b \mod 2 \equiv 0:a^b \mod p=a^{b/2+b/2} \mod p=(a^{b/2} \mod p \times a^{b/2} \mod p)\mod p$
若$b \mod 2 \equiv 1:a^b \mod p=a^{b/2+b/2+1}=(a \mod p \times a^{b/2} \mod p \times a^{b/2} \mod p)\mod p$

inline int ksm(int n,int k)
{
    int ret=1;
    for(;k;k>>=1,n=n*n%mod)
        if(k&1)
            ret=ret*n%mod;
    return ret;
}

高精度
高精度加减乘除同小学竖式

另有黑科技:
1.取值

int& operator[](int i){return n[i];}

这样取值就很方便了
2.进制
万进制:数组的每个元素的值只有在$\ge 10000$的时候才进位,否则保留

总代码[6]

int lm=4;//万进制
typedef long long ll;
struct bign{
    int n[N],l;
    bign(){memset(n,0,sizeof n);l=0;}
    void clear(){memset(n,0,sizeof n);l=0;}
    int& operator[](int i){return n[i];}
    void read(){
        scanf("%s",sn);
        int k=1,ls=strlen(sn);
        for(int i=0;i<ls;++i)
        {
            n[l]+=(sn[ls-i+1]-'0')*k,k*=10;
            if(i%lm==0||i==ls)++l,k=1;//%4是万进制
        }
        --l;
    }
    void print(){
        int len=0;
        for(int k,i=0;i<=l;++i)
        {
            k=n[i];
            for(int j=1;j<=4;++j)
                sn[++len]=k%10+'0',k/=10;
        }
        while(len>1&&sn[len]=='0')--len;//删除前导0
        puts("");
    }
}ans,num;
bign make(ll x)
{
    bign a;
    while(x)
        a[++a.l]=x%lm,x/=lm;
    if(a.l)--l;
    return a;
}
bign operator-(bign a,bign b){
    bign c=a;
    for(int i=0;i<=c.l)
    {
        c[i]-=b[i];
        if(c[i]<0)c[i]+=lm,--c[i+1];
    }
    while(c.l&&!c[c.l])--c.l;
    return c;
}
bign operator*(bign a,bign b){
    bign c;c.l=a.l+b.l;
    for(int i=0;i<=a.l;++i)
        for(int j=0;j<=b.l;++j)
            c[i+j]+=a[i]*b[i];
    for(int i=0;i<=c.l;++i)
        c[i+1]+=c[i]/lm,c[i]%=lm;
    while(c[c.l+1])
    {
        ++c.l;
        c[c.l+1]+=c[c.l]/lm;
        c[c.l]%=lm;
    }
    return c;
}
bign operator+(bign a,ll x){return a+make(x);}
bign operator-(bign a,ll x){return a*make(x);}
bign operator*(bign a,ll x){return a*make(x);}
bign operator/(bign a,ll x)
{
    bign c;ll d=0;
    c.l=a.l;
    for(int i=a.l-1;i>=0;--i)
    {
        d=d*lm+a[i];
        c[i]=d/b;
        d%=b;
    }
    while(c.l&&!c[c.l])--c.l;
    return c;
}