“少壮不努力,AK IOI。”——RLD

2018/8/10

Prime Distance On Tree

聪聪可可一样是点分治的计数题

但是合并信息是$O(n^2)$的,会炸,FFT可以加速。

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long
#define db double
#define fr friend
#define op operator

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=100005;


struct cmx{
    db r,i;
    cmx(){}
    cmx(db _r,db _i){r=_r;i=_i;}
    fr cmx op+(const cmx&x,const cmx&y){return cmx(x.r+y.r,x.i+y.i);}
    fr cmx op-(const cmx&x,const cmx&y){return cmx(x.r-y.r,x.i-y.i);}
    fr cmx op*(const cmx&x,const cmx&y){return cmx(x.r*y.r-x.i*y.i,x.r*y.i+x.i*y.r);}
    fr cmx op/(const cmx&x,const db&y){return cmx(x.r/y,x.i/y);}
}a[N<<2],b[N<<2];

int r[N<<2];
const db pi=acos(-1.0);

inline void fft(cmx *t,int len,int on){
    for(int i=0;i<len;++i)if(i<r[i])swap(t[i],t[r[i]]);
    for(int i=1;i<len;i<<=1){
        cmx wn(cos(pi/i),on*sin(pi/i));
        for(int j=0;j<len;j+=(i<<1)){
            cmx w(1,0);
            for(int k=0;k<i;++k,w=w*wn){
                cmx u=t[j+k];
                cmx v=w*t[j+k+i];
                t[j+k]=u+v;
                t[j+k+i]=u-v;
            }
        }
    }
    if(on==-1)for(int i=0;i<len;++i)t[i]=t[i]/len;
}
#define DFT(x,y) fft(x,y,1)
#define IDFT(x,y) fft(x,y,-1)

int rt,n,cnt,ecnt;
int fir[N],nex[N<<1],to[N<<1],val[N<<1],s[N],siz[N],dis[N];
bool vis[N];

inline void add(int u,int v){
    nex[++ecnt]=fir[u];fir[u]=ecnt;to[ecnt]=v;
    nex[++ecnt]=fir[v];fir[v]=ecnt;to[ecnt]=u;
}

bool isnp[N<<1];
inline void getprime(int maxn){
    for(int i=2;i<=maxn;++i)
        if(!isnp[i])for(int j=(i<<1);j<=maxn;j+=i)isnp[j]=1;
}

inline void init(){
    r(n);
    getprime(n<<1);
    for(int i=1,u,v;i<n;++i)r(u),r(v),add(u,v);
}

inline void getroot(int x,int f){
    siz[x]=1;
    s[x]=0;
    for(int i=fir[x],v;i;i=nex[i]){
        v=to[i];
        if(v==f||vis[v])continue;
        getroot(v,x);
        siz[x]+=siz[v];
        s[x]=max(s[x],siz[v]);
    }
    s[x]=max(s[x],cnt-siz[x]);
    if(s[x]<s[rt])rt=x;
}

int mxd;
inline void dfs1(int x,int f){
    if(dis[x]>mxd)mxd=dis[x];
    for(int i=fir[x],v;i;i=nex[i]){
        v=to[i];
        if(v==f||vis[v])continue;
        dis[v]=dis[x]+1;
        dfs1(v,x);
    }
}

int num1[N],num2[N];
inline void dfs2(int x,int f,int opt){
    num1[dis[x]]+=opt;
    if(opt==-1)num2[dis[x]]++;
    for(int i=fir[x],v;i;i=nex[i]){
        v=to[i];
        if(v==f||vis[v])continue;
        dfs2(v,x,opt);
    }
}

inline ll clac(int x){
    ll ret=0;
    memset(num2+1,0,n<<3);
//  memset(num2,0,sizeof(num2));
    num2[0]=1;
    dis[x]=mxd=0;
    dfs1(x,0);
    int len=1;
    while(len<=(mxd<<1))len<<=1;
    for(int i=0;i<len;++i)r[i]=(r[i>>1]>>1)|((i&1)*(len>>1));
    for(int i=fir[x],v;i;i=nex[i]){
        v=to[i];
        if(vis[v])continue;
        dfs2(v,x,1);
        for(int j=0;j<len;++j)a[j]=cmx(num1[j],0);
        for(int j=0;j<len;++j)b[j]=cmx(num2[j],0);
        DFT(a,len);
        DFT(b,len);
        for(int j=0;j<len;++j)a[j]=a[j]*b[j];
        IDFT(a,len);
        for(int j=2;j<len;++j)
            if(!isnp[j])
                ret+=(ll)(a[j].r+0.5);
        dfs2(v,x,-1);
    }
    return ret;
}

ll ans;
inline void slove(int x){
    vis[x]=1;
    ans+=clac(x);
    for(int i=fir[x],v;i;i=nex[i]){
        v=to[i];
        if(vis[v])continue;
        rt=0;
        cnt=siz[v];
        getroot(v,0);
        slove(rt);
    }
}

inline void work(){
    s[rt]=cnt=n;
    getroot(1,0);
    slove(rt);
}

int main(){
    init();
    work();
    printf("%.6lf",(db)ans/((db)n*(n-1)/2));
}

一开始数组开小WA了好几次。

3-idiots

给出n根木棍,求任选三根构成三角形的概率。

实际上还是计数,对每种长度木棍进行统计,考虑两根拼出的长度方案,FFT加速可以求出最后讨论判重,判不合法即可。

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long
#define db double
#define fr friend
#define op operator

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e5+7;


struct cmx{
    db r,i;
    cmx(){}
    cmx(db _r,db _i){r=_r;i=_i;}
    fr cmx op+(const cmx&x,const cmx&y){return cmx(x.r+y.r,x.i+y.i);}
    fr cmx op-(const cmx&x,const cmx&y){return cmx(x.r-y.r,x.i-y.i);}
    fr cmx op*(const cmx&x,const cmx&y){return cmx(x.r*y.r-x.i*y.i,x.r*y.i+x.i*y.r);}
    fr cmx op/(const cmx&x,const db&y){return cmx(x.r/y,x.i/y);}
}A[N<<2];

int r[N<<2];
const db pi=acos(-1.0);

inline void fft(cmx *t,int len,int on){
    for(int i=0;i<len;++i)if(i<r[i])swap(t[i],t[r[i]]);
    for(int i=1;i<len;i<<=1){
        cmx wn(cos(pi/i),on*sin(pi/i));
        for(int j=0;j<len;j+=(i<<1)){
            cmx w(1,0);
            for(int k=0;k<i;++k,w=w*wn){
                cmx u=t[j+k];
                cmx v=w*t[j+k+i];
                t[j+k]=u+v;
                t[j+k+i]=u-v;
            }
        }
    }
    if(on==-1)for(int i=0;i<len;++i)t[i]=t[i]/len;
}
#define DFT(x,y) fft(x,y,1)
#define IDFT(x,y) fft(x,y,-1)

int a[N];
ll c[N<<2];
int main(){
    int T;r(T);
    while(T--){

        int n;r(n);
        for(int i=0;i<n;++i)r(a[i]),++c[a[i]];

        sort(a,a+n);
        int v=a[n-1]*2+1;

        int len=1,l=-1;
        while(len<v)len<<=1,++l;
        for(int i=0;i<len;++i)r[i]=(r[i>>1]>>1)|((i&1)<<l);

        for(int i=0;i<v;++i)A[i]=cmx(c[i],0);
        for(int i=v;i<len;++i)A[i]=cmx(0,0);

        DFT(A,len);
        for(int i=0;i<len;++i)A[i]=A[i]*A[i];
        IDFT(A,len);

        for(int i=0;i<v;++i)c[i]=(ll)(A[i].r+0.5);

        for(int i=0;i<n;++i)c[a[i]<<1]--;//同一根选两次
        for(int i=0;i<v;++i)c[i]>>=1;//消序,除以2的阶乘

        for(int i=1;i<v;++i)c[i]+=c[i-1];

        ll cnt=0,sum=c[v-1];
        for(int i=0;i<n;++i){//枚举最长木棍长度
            cnt+=sum-c[a[i]];
            cnt-=(ll)(n-i-1)*i;//本来应该更小的有一根比i长
            cnt-=n-1;//取到本身
            cnt-=(ll)(n-i-1)*(n-i-2)>>1;//都比i长(除以2消序)
        }
        printf("%.7lfn",6.0*cnt/((ll)n*(n-1)*(n-2)));//除以总情况数
        memset(c,0,len<<3);
    }
}

2018/8/11

序列统计

乘法的情况我不会,但是我会加法,和Prime Distance On Tree3-idiots是一样的。
于是我们想把它转化为加法。
$x^a+x^b=x^{a+b}$
注意到m是质数,令x为m原根,多项式快速幂即可,问题在于怎么求原根。
枚举,依次检验 $i^j$ 是否等于1,其中j是m-1的约数。
求原根 模板题
然后就可以NTT做了

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=40010;
const int p=1004535809;
const int g=3;

inline int qpow(int a,int b,int mod=p){
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
    }
    return ans;
}

int r[N];
inline void ntt(int *A,int len,bool opt=1) {
    for(int i=0;i<len;++i)if(i<r[i])swap(A[i],A[r[i]]);
    for(int i=2;i<=len;i<<=1){
        int n=i>>1,wn=qpow(g,(p-1)/i);
        if(!opt)wn=qpow(wn,p-2);
        for(int j=0;j<len;j+=i){
            int w=1;
            for(int k=0;k<n;++k,w=1ll*w*wn%p){
                int u=1ll*A[j+k+n]*w%p;
                A[j+k+n]=(A[j+k]-u+p)%p;
                A[j+k]=(A[j+k]+u)%p;
            }
        }
    }
    if(!opt){
        int inv=qpow(len,p-2);
        for(int i=0;i<len;++i)A[i]=1ll*A[i]*inv%p;
    }
}

int n,m,x,s,len=1;

int t1[N],t2[N];
inline void mul(int *A,int *B,int *C){
    memcpy(t1,A,len<<2);
    memcpy(t2,B,len<<2);
    ntt(t1,len);ntt(t2,len);
    for(int i=0;i<len;++i)C[i]=1ll*t1[i]*t2[i]%p;
    ntt(C,len,0);
    for(int i=len-1;i>=m-1;--i)(C[i-m+1]+=C[i])%=p,C[i]=0;
}   

int rt[2000];
inline int get_root(int m){
    for(int i=2;i<m-1;++i)if((m-1)%i==0)rt[++rt[0]]=i;
    for(int i=2;;++i){
        bool flag=1;
        for(int j=1;flag&&j<=rt[0];++j)if(qpow(i,rt[j],m)==1)flag=0;
        if(flag)return i;
    }
}

int mi[8005];
int c[N];
int f[N];

int main(){
    r(n);r(m);r(x);r(s);
    int root=get_root(m),tmp=1;
    for(int i=0;i<m-1;++i,tmp=1ll*tmp*root%m)mi[tmp]=i;
    for(int i=0;i<s;++i)r(tmp),c[mi[tmp%m]]=(tmp!=0);
    while(len<(m<<1))len<<=1;
    for(int i=1;i<len;++i)r[i]=(r[i>>1]>>1)|((i&1)*(len>>1));
    f[0]=1;
    for(;n;n>>=1){//因为超出m的要贡献到它%m去,所以不能求ln再exp
        if(n&1)mul(f,c,f);
        mul(c,c,c);
    }
    printf("%d",f[mi[x]]);
}

2018/8/13

tset49

T1

还以为是polya定理,结果还是推式子。

设$f_n$表示最小正周期为𝑛的涂色方案数,$g_n$表示周期为𝑛的涂色方案数
$g_n=\sum_{d|n}{f_d}$

$f_n=\sum_{d|n}{g_d * mu(frac{n}{d})}$

𝑛个点选择𝑚个涂黑,则有𝑛−𝑚个白点,设第𝑖个白点后的黑点数目为$x_i$,前缀的黑点数目为 $x_0$
问题转化为求下面方程的解的个数

$\sum_{i=0}^{n-m}{x_i}=m$

其中 $x _ i,x _ 0+x _ {n-m} \leq k $

由生成函数我们可以得到

$g(x)=(\sum_{i=0}^{k}{x^i})^{n-m-1} ((\sum_{i=0}^{k}{x^i})^2 \mod x^{k+1})$

其实这里多项式快速幂就可以过了
但是还可以更优

$\sum_{i=0}^{k}{x^i}= \frac{1-x^{k+1}}{x-1}$

$( \sum_{i=0}^{k}{x^i})^2 \mod x^{k+1}= \frac{1}{{(1-x)}^2} \mod x^{k+1}$ (分子其它项$ \mod x^{k+1}=0$ )

$= \sum_{i=0}^{k}{(i+1)x^i}$ (直接展开,也可以记结论)

然后

我们得到一个等差乘等比,是不是~
怎么办嘛,同~学~们~
但是吴老师对不起,我们决定积分

设$S(x)= \sum_{i=0}^{k}{(i+1)x^i}$

$ \int S(x)dx= \sum_{i=0}^{k}{x^{i+1}}= \frac{x(1-x^{k+1})}{1-x}$

然后再求个导

$S(x)= \frac{1-(k-2)x^{k+1}+(k+1)x^{k+2}}{(1-x)^2}$

$f(x)={( \frac{1-x^{k+1}}{x-1})}^{n-m-1} ( \frac{1-(k-2)x^{k+1}+(k+1)x^{k+2}}{(1-x)^2})$

$= \frac{{(1-x^{k+1})}^{n-m-1}}{{(x-1)}^{n-m+1}} (1-(k-2)x^{k+1}+(k+1)x^{k+2})$

将分子分母展开,可求出$g_n$
进而可求得$f_n$

代码待补充。

T3

看着就像 TJOI概率论,确实一个套路。

令 $C_n$ 表示卡特兰数(n个点二叉树个数)

$S_n$表示n个点所有二叉树子树大小

写出递推式 $O(n^2)$ $60 point$

使用生成函数+多项式算法 $O(nlogn)$ $80 ~100 point$(多项式求逆+卡常实测能过)

展开化简 $O(n)$ $100 point$

考场上推出式子,不会化简,80分算法,但是不知道为什么炸了,重测$80$分。

本来只要求逆就好了,我居然还写了开根,T3推了半天结果T1都没时间推式子了。(还是不够熟练)

推导过程:

$C_n=nC_n+2 \sum_{i=0}^{n-1}S_iC_{n-i-1}$ //60point

$ S(x)=xC'(x)+2xS(x)C(x)$ //80point

$S(x)= \frac{xC'(x)}{(1-2x)C(x)}$

带入$C(x)= \frac{1- \sqrt{1-4x}}{2x}$

$= \frac{1-2x- \sqrt{1-4x}}{2x(1-4x)}$

$= \frac{1}{2x}( \frac{1-2x}{1-4x}- \frac{1}{ \sqrt{1-4x}})$

展开$ \frac{1-2x}{1-4x}=(1-2x) \sum _ {n=0}^{ \infty}{(4x)^n}$

$ \frac{1}{ \sqrt{1-4x}}= \sum _ {n=0}^{ \infty}{( _ {n}^{- \frac{1}{2}})(-4x)^n}$
$( _ n^{ – \frac{1}{2} } ) = \frac{1}{n!} \prod _ {i=0}^{n-1}{ (- \frac{1}{2}-i) }$
$= \frac{1}{n!}(-1)^n \frac{1}{2^n} \prod_{i=0}^{n}{(2i+1)}$

$= \frac{1}{(-4)^n}(_n^{2n})$

带入算出$S(x)= \sum_{n=0}^{ \infty}{(2^{2n}- \frac{1}{2}(_{n+1}^{2n+2})x^n)}$

$S_n=2^{2n}- \frac{1}{2}(_{n+1}^{2n+2})$

然后$O(n)$就可以做了,代码就不放了。

其它

广义二项式系数

$C(n,m)= \frac { \prod_{i=0}^{m-1}(n-i)} {m!}$

2018/8/14

Test50

期望得分$70+70+60=220$
实际得分$35+70+0=105$
为什么T3炸了?因为我居然把输入写反了,改过来70分,无话可说。
T1也是非常蠢,送的70分只拿了35。
其实T3我写矩阵树定理是复的以前的板子,就当是没写出来吧,也没什么。

这两天考的真难受,昨天可以进rank5,今天可以rank2
结果昨天因为评测机,炸了80分,今天自己傻了,丢了105分
结果都rank10开外去了

T1

考试的时候我是按照应该剩下钱数来推的
即$m_{i,j}= \frac{m_{i+1,j}+m_{i,j+1}}{2}$
$m_{n,x}=2^{2n-1}$
$m_{x,n}=-2^{2n-1}$
答案为$m_{i+1,j}-m_{i,j}$

本来已经是一个$O(n^2)$的70分dp,居然被我硬生生的写成了35分
我也不知道当时是怎么想的,居然已经记忆化了都忘了返回答案
我还在纳闷为什么复杂度是$O(n^2)$还跑不过20的数据

应该还可以用这个推出100分答案,但是我太懒,不想推

下面说正解

正解是考虑胜率,递推公式和上面一样,只是边界条件有改变,但是就转变为熟悉的类容,有套路可用
假设当前胜率为$ \frac{1}{2}+p$,则剩余钱数为$p*2^n$
然后考虑不提前结束比赛的使用情况,则还要比$t=2n-1-i-j$场
可以计算出胜率是$ \frac{ \sum_{k=n-i}^{t}{(_k^{t})}}{2^{t}}$
答案是钱数之差,求出胜率之差即可
最后可以算出答案是$2^{i+j+1}(_{n-i-1}^{2n-i-j-2})$
时间复杂度$O(n)$

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

typedef long long ll;

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=100005;
const int p=1e9+7;

int inv[N<<1];

inline int C(int n,int m){
    ll ret=1;
    for(int i=1;i<=m;++i)ret=ret*inv[i]%p;
    for(int i=n-m+1;i<=n;++i)ret=ret*i%p;
    return ret;
}

int main(){
    freopen("beijing.in","r",stdin);
    freopen("beijing.out","w",stdout);
    int n;r(n);
    inv[1]=1;
    for(int i=2;i<=(n<<1);++i)inv[i]=(ll)(p-p/i)*inv[p%i]%p;
    ll c=C(2*n-2,n-1)*2%p;
    for(int a=0,b=0,x;a<n&&b<n;b+=x,a+=(x^1)){
        printf("%lldn",c);
        r(x);
        c=c*inv[2*n-2-a-b]%p*2%p;
        if(x)c=c*(n-b-1)%p;
        else c=c*(n-a-1)%p;
    }
}

T2

其实我想的暴力再多推一推就出正解了
看到这题就想起了洛谷月赛题
于是推了一会发现答案是 $ \sum_{i=1}^{x}{(_k^{x+k-i})}a[i]$
然后k==1时是单点修改,区间求值
K==2是区间修改,区间求值
于是就有$30+40=70$分了

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ls (rt<<1)
#define rs (rt<<1|1)

typedef long long ll;

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e5+7;
const int p=1e9+7;

int n,m,k;
int a[N];

namespace work1{
    int c[N];

    inline int lowbit(int x){return x&(-x);}
    inline void add(int x,int v){for(;x<=n;x+=lowbit(x))(c[x]+=v)%=p;}
    inline int sum(int x){int ans=0;for(;x;x^=lowbit(x))(ans+=c[x])%=p;return ans;}
//  inline int query(int l,int r){return sum(r)-sum(l);}


    inline void solve(){
//      for(int i=1;i<=n;++i)add(i,a[i]);
        for(int opt,x;m;--m){
            r(opt);
            r(x);
            if(opt)printf("%dn",sum(x));
            else r(opt),add(x,opt);
        }
    }
}

namespace work2{
//  int c[N];

    ll sum[N<<2],tag[N<<2];

    inline void update(int rt){sum[rt]=(sum[ls]+sum[rs])%p;}

    inline void pushdown(int rt,int l,int r){
        if(tag[rt]){
            int mid=(l+r)>>1,l1=mid-l+1,l2=r-mid;
            (sum[ls]+=tag[rt]*l1)%=p;
            (sum[rs]+=tag[rt]*l2)%=p;
            (tag[ls]+=tag[rt])%=p;
            (tag[rs]+=tag[rt])%=p;
            tag[rt]=0;
        }
    }

//  void build(int rt,int l,int r){
//      if(l==r){
//          sum[rt]=c[l];
//          return;
//      }
//      int mid=(l+r)>>1;
//      build(ls,l,mid);
//      build(rs,mid+1,r);
//      update(rt);
//  }

    void add(int rt,int l,int r,int x,int y,int v){
        if(r<x||l>y)return;
        if(x<=l&&r<=y){
            (sum[rt]+=1ll*v*(r-l+1))%=p;
            (tag[rt]+=v)%=p;
            return;
        }
        pushdown(rt,l,r);
        int mid=(l+r)>>1;
        add(ls,l,mid,x,y,v);
        add(rs,mid+1,r,x,y,v);
        update(rt);
    }

    int query(int rt,int l,int r,int x,int y){
        if(r<x||l>y)return 0;
        if(x<=l&&r<=y)return sum[rt];
        pushdown(rt,l,r);
        int mid=(l+r)>>1;
        return (query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y))%p;
    }

    inline void solve(){
//      for(int i=1;i<=n;++i)c[i]=(c[i-1]+a[i])%p;
//      build(1,1,n);
        for(int opt,x;m;--m){
            r(opt);
            r(x);
            if(opt)printf("%dn",query(1,1,n,1,x));
            else r(opt),add(1,1,n,x,n,opt);
        }
    }
}

namespace work3{
    int fac[N<<1],facinv[N<<1];

    inline int qpow(ll a,int b){
        ll ans=1;
        for(;b;b>>=1){
            if(b&1)ans=ans*a%p;
            a=a*a%p;
        }
        return ans;
    }

    inline int C(const int& n,const int& m){
        return (ll)fac[n]*facinv[m]%p*facinv[n-m]%p;
    }

    int b[N];

    inline void Query(int x){
        ll ret=0;
        for(int i=1;i<=x;++i)(ret+=(ll)a[i]*b[x-i+1])%=p;
        printf("%lldn",ret);
    }

    inline void solve(){
        int tmp=n<<1,i;
        for(fac[0]=i=1;i<=tmp;++i)fac[i]=fac[i-1]*(ll)i%p;
        for(facinv[tmp]=qpow(fac[tmp],p-2),i=(tmp);i;--i)facinv[i-1]=facinv[i]*(ll)i%p;
        for(i=1;i<=n;++i)b[i]=C(i+k-2,i-1);
        for(int opt,x;m;--m){
            r(opt);
            r(x);
            if(opt)Query(x);
            else r(opt),(a[x]+=opt)%=p;
        }
    }
}

int main(){
    freopen("hongkong.in","r",stdin);
    freopen("hongkong.out","w",stdout);

    r(n);r(m);r(k);

    if(k==1){work1::solve();return 0;}
    if(k==2){work2::solve();return 0;}
    work3::solve();return 0;        
}

正解认为 $( _ k^{x+k-i})$ 不好维护,利用组合恒等式

$( _ k ^ {x+k-i})= \sum _ {j=0} ^ {k}{( _ j ^ x)( _ {k-j} ^ {k-i})}$

因为从 $x+k-i$ 个中选 $k$ 个相当于先从 $x$ 个中选 $j$ 个,再从剩下 $k-i$ 个中选剩下的 $k-j$ 个

实际上 $k-i$ 可能是负数,但是从公式角度来说是没有问题的

于是我们用 $k+1$ 个树状数组 ${T _ 0,T _ 1,…,T _ k}$

每个树状数组对应$j$的一个取值

维护数列 $T _ {ji} = ( _ j ^ i)( _ {k-j} ^ {k-i})a _ i$

支持单点修改(加的值乘上系数 $( _ j^x)( _ {k-j}^{k-x})$ 即可)

支持求前缀和,即 $ \sum _ {j=0} ^ {k}{( _ j ^ x)( _ {k-j} ^ {k-i})=( _ k ^ {x+k-i})}$

每次修改$k+1$个树状数组$O(klog(n))$

每次查询$k+1$个树状数组$O(klog(n))$

总复杂度$O(mklog(n))$
代码如下

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

typedef long long ll;

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e5+7;
const int p=1e9+7;

inline ll qpow(ll a,int b){
    ll ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
    }
    return ans;
}

int n,m,k;

struct BIT{
    int a[N];

    inline int lowbit(int x){return x&(-x);}
    inline void add(int x,int v){for(;x<=n;x+=lowbit(x))(a[x]+=v)%=p;}
    inline int sum(int x){int ans=0;for(;x;x^=lowbit(x))(ans+=a[x])%=p;return ans;}

}tr[11];

int inv[15];
int main(){
    freopen("hongkong.in","r",stdin);
    freopen("hongkong.out","w",stdout);

    r(n);r(m);r(k);
    inv[1]=1;
    for(int i=2;i<=k;++i)inv[i]=(ll)(p-p/i)*inv[p%i]%p;
    --k;
    for(int opt,x;m;--m){
        r(opt);r(x);
        if(opt){
            ll ret=0,c=1;
            for(int i=0;i<=k;c=c*inv[i+1]%p*(x-i)%p,++i)(ret+=tr[i].sum(x)*c)%=p;
            printf("%lldn",ret);
        }
        else {
            r(opt);
            ll c=1;
            for(int i=k;i>=0;c=c*inv[k-i+1]%p*(i-x+p)%p,--i)tr[i].add(x,c*opt%p);
        }
    }       
}

T3

70分其实就是裸的矩阵树定理
正解好像是叫Berlekamp-Massey算法的黑科技,以后再说吧

2018/8/15

Test51

期望得分$60+100+30=190$
实际得分$60+100+30=190$
终于没有奇葩错误了,rank3

多亏了我学过burnside引理和polya定理,T2只有我一个AC,其他人最多的都只有30分
但是这样都没有rank1,可见我的T1和T3写得有多烂

T1

实际上就是NOIP2017 宝藏 改成了计数题,目的是卡随机之类的玄学算法,只能写正解
然而我还是不会,写了60分部分分

最后改的代码,复杂度$O(m*4^n)$
一中的大佬的复杂度更优,看懂后再说吧

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

typedef long long ll; 

const int N=11;
const int M=1005;
const int p=1e9+7;

inline ll qpow(ll a,int b){
    ll ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
    }
    return ans;
}

int n,m;
int x[M<<1],y[M<<1],w[M<<1];
int ts[N],tc[N];
int s[1<<N][1<<N],c[1<<N][1<<N];
int sum[N][1<<N][1<<N],cnt[N][1<<N][1<<N];

int main(){
    freopen("berlin.in","r",stdin);
    freopen("berlin.out","w",stdout);
    r(n);r(m);
    for(int i=1;i<=m;++i){
        r(x[i]);
        r(y[i]);
        r(w[i]);
        --x[i];
        --y[i];
        x[i+m]=y[i];
        y[i+m]=x[i];
        w[i+m]=w[i];
    }
    m<<=1;

    int S=(1<<n)-1;
    for(int i=0;i<=S;++i){
        for(int j=0;j<=S;++j){
            if(i&j)continue;

            memset(ts,0,n<<2);
            memset(tc,0,n<<2);
            for(int k=1;k<=m;++k){
                if((i>>x[k]&1)&&(j>>y[k]&1)){
                    ts[y[k]]+=w[k];
                    ++tc[y[k]];
                }
            }

            bool flag=1;
            for(int k=0;flag&&k<n;++k)if((j>>k&1)&&(tc[k]==0))flag=0;
            if(!flag)continue;

            int &ss=s[i][j];
            int &cc=c[i][j];
            ss=0;
            cc=1;
            for(int k=0;k<n;++k)if(j>>k&1)cc=(ll)cc*tc[k]%p;
            for(int k=0;k<n;++k)if(j>>k&1)ss=(ss+(ll)cc*qpow(tc[k],p-2)%p*ts[k]%p)%p;

        }
    }

    for(int i=0;i<n;++i)sum[0][0][1<<i]=0,cnt[0][0][1<<i]=1;
    for(int d=0;d<n;++d){
        for(int i=0;i<=S;++i){
            for(int j=0;j<=S;++j){
                if(i&j)continue;

                int &ss=sum[d][i][j];
                int &cc=cnt[d][i][j];
                if(!cc)continue;

                int r=S^i^j;
                for(int k=r;;k=(k-1)&r){
                    int &sss=sum[d+1][i|j][k];
                    int &ccc=cnt[d+1][i|j][k];
                    ccc=(ccc+(ll)cc*c[j][k]%p)%p;
                    sss=(sss+(ll)ss*c[j][k]%p+(ll)cc*s[j][k]%p*(d+1)%p)%p;
                    if(!k)break;
                }
            }
        }
    }

    printf("%d",sum[n][S][0]);

}

T2

首先考虑没有异或和为零的限制

burnside引理可以得到答案为 $ \sum_{a|n,b|m}{ \varphi(a) \varphi(b) 2 ^ { \frac{nm}{ lcm(a,b) } } }$
学习burnside引理这里
毕老师讲的一种理解方法

问题求长度为n的01序列本质不同(循环同构为一种)的种数
比如 n=6
我们知道一共有64种
但是像
111110 011111 101111 110111 111011 111101
这六个序列只算一种
但是我们不能直接除以6
因为有些序列在某种“置换”下不变
比如000000“旋转”后还是000000
我们的64种就少了6种,那么我们只要把每种置换下不动点个数加上就可以了
移0位不变:64种
移1位不变:2种(000000 111111)
移2位不变:4种(000000 111111 101010 010101)
移3位不变:8种(000000 111111 110110 101101 011011 001001 010010 100100)
移4位不变:4种(000000 111111 101010 010101)
移5位不变:2种(000000 111111)
所以所有本质不同的序列有$ \frac{64+2+4+8+4+2}{6}=14$种
即所有置换下不动点个数之和除以置换种数

回到这道题,我们首先考虑一维情况
假设当前置换是移$i$位,则$0,i,2i…$构成一个循环。
这个循环有$ \frac{lcm(i,n)}{i}= \frac{n}{ gcd(i,n)}$个元素,所以有$gcd(i,n)$个循环,可以理解为有$gcd(i,n)$个位置可以自由选择
所以不动点总数为$ \sum_{i=0}^{n-1}{2^{gcd(i,n)}}$
更进一步,我们枚举$d=gcd(i,n)$
不动点总数为$ \sum_{d|n}{2^dx}$
$x$表示d的出现次数,即有多少个小于$n$的$i$满足$gcd(i,n)=d$
即$gcd( \frac{i}{d}, \frac{n}{d})=1$
显然$x= \varphi( \frac{n}{d})$
所以答案是$ \sum_{d|n}{2^d \varphi( \frac{n}{d})}$
同理推广到二维,答案是$ \sum_{a|n,b|m}{ \varphi(a) \varphi(b) 2 ^ { \frac{nm}{ lcm(a,b) } } }$

至于加上异或限制,就是有一些位置本来可以随便填,现在必须“牺牲”自己。

然后画图讨论(结果与循环长度奇偶有关,指数部分有一些调整)一下就好了,最后的结论还是看题解吧,我太懒了,不想搬

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

typedef long long ll;

const int N=100;
const int p=1000000007;

inline ll qpow(ll a,int b){
    ll ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
    }
    return ans;
}

inline int getphi(int n){
    int m=(int)sqrt(n+0.5);
    int ans=n;
    for(int i=2;i<=m;i++){
        if(n%i==0){
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}

ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

inline void div(int x,int *a,int& c){
    int t=sqrt(x);
    for(int i=1;i<=t;++i)if(!(x%i))a[++c]=i,a[++c]=x/i;
    if(t*t==x)--c;
}

int A[N],B[N],phin[N],phim[N],cn,cm;

int main(){
    freopen("paris.in","r",stdin);
    freopen("paris.out","w",stdout);
    int n,m;
    r(n);
    r(m);
    ll ret=0;
    div(n,A,cn);//sqrt(n)
    div(m,B,cm);//sqrt(m)
    for(int i=1;i<=cn;++i)phin[i]=getphi(A[i]);//loglogn * sqrt(n)
    for(int i=1;i<=cm;++i)phim[i]=getphi(B[i]);//loglogm * sqrt(m)
    for(int i=1;i<=cn;++i){// loglogn * loglogm * logp
        int a=A[i];
        for(int j=1;j<=cm;++j){
            int b=B[j];
            ll x=lcm(a,b);
            ll t=1ll*n*m/x;
            if((x/a)&1)t-=n/a;
            if((x/b)&1)t-=m/b;
            if(((x/a)&1)&&((x/b)&1))t++;
            (ret+=1ll*phin[i]*phim[j]%p*qpow(2,t%(p-1))%p)%=p;
        }
    }
    printf("%lld",ret*qpow(1ll*n*m%p,p-2)%p);
}


一开始还写了个线性筛,纳闷了半天才发现每个每次求就好了。
老师说其实可以用反质数把我的程序卡掉,N应该开到$2000$的样子。
算了一下$1e9$内约数最多的数是$73513440$,它有$768$个约数。
关于反素数,可以做这两道题
51Nod 1060
51Nod 1061

T3

2018/8/16

并没有写新题,改了前两天的题,题解在上面。

2018/8/17

快速沃尔什变换

没什么好说的,背板子而已,居然洛谷rank1,简直有毒


\#include<bits/stdc++.h> using namespace std; #define gc c=getchar() #define r(x) read(x) #define ll long long template<typename T> inline void read(T&x){ x=0;T k=1;char gc; while(!isdigit(c)){if(c=='-')k=-1;gc;} while(isdigit(c)){x=x*10+c-'0';gc;}x*=k; } const int N=1<<17|7; const int p=998244353; const ll inv2=499122177; inline int add(int a,int b){ a+=b; if(a>=p)a-=p; return a; } inline int sub(int a,int b){ a-=b; if(a<0)a+=p; return a; } inline void FWT_or(int *A,int len,bool opt=1){ for(int i=1;i<len;i<<=1){ for(int j=0;j<len;j+=i<<1){ for(int k=0;k<i;++k){ A[j+k+i]=opt?add(A[j+k],A[j+k+i]):sub(A[j+k+i],A[j+k]); } } } } inline void FWT_and(int *A,int len,bool opt=1){ for(int i=1;i<len;i<<=1){ for(int j=0;j<len;j+=i<<1){ for(int k=0;k<i;++k){ A[j+k]=opt?add(A[j+k],A[j+k+i]):sub(A[j+k],A[j+k+i]); } } } } inline void FWT_xor(int *A,int len,bool opt=1){ for(int i=1;i<len;i<<=1){ for(int j=0;j<len;j+=i<<1){ for(int k=0;k<i;++k){ int u=A[j+k],v=A[j+k+i]; A[j+k]=add(u,v); A[j+k+i]=sub(u,v); if(!opt){ A[j+k]=A[j+k]*inv2%p; A[j+k+i]=A[j+k+i]*inv2%p; } } } } } int T1[N],T2[N]; inline void OR(int* A,int* B,int* C,int len){ memcpy(T1,A,len<<2); memcpy(T2,B,len<<2); FWT_or(T1,len); FWT_or(T2,len); for(int i=0;i<len;++i)C[i]=(ll)T1[i]*T2[i]%p; FWT_or(C,len,0); } inline void AND(int* A,int* B,int* C,int len){ memcpy(T1,A,len<<2); memcpy(T2,B,len<<2); FWT_and(T1,len); FWT_and(T2,len); for(int i=0;i<len;++i)C[i]=(ll)T1[i]*T2[i]%p; FWT_and(C,len,0); } inline void XOR(int* A,int* B,int* C,int len){ memcpy(T1,A,len<<2); memcpy(T2,B,len<<2); FWT_xor(T1,len); FWT_xor(T2,len); for(int i=0;i<len;++i)C[i]=(ll)T1[i]*T2[i]%p; FWT_xor(C,len,0); } int a[N],b[N],c[N]; int main(){ int n; r(n);n=1<<n; for(int i=0;i<n;++i)r(a[i]); for(int i=0;i<n;++i)r(b[i]); OR(a,b,c,n); for(int i=0;i<n;++i)printf("%d ",c[i]);puts(""); AND(a,b,c,n); for(int i=0;i<n;++i)printf("%d ",c[i]);puts(""); XOR(a,b,c,n); for(int i=0;i<n;++i)printf("%d ",c[i]);puts(""); }

如果我学会了推导过程会补在这里的。

Hard Nim

线性筛+FWT+生成函数
没什么好说的

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=50005;
const int p=1e9+7;
const ll inv2=500000004;

inline int add(int a,int b){a+=b;if(a>=p)a-=p;return a;}
inline int sub(int a,int b){a-=b;if(a<0)a+=p;return a;}
inline ll qpow(ll a,int b){ll ans=1;for(;b;b>>=1){if(b&1)ans=ans*a%p;a=a*a%p;}return ans;}

bool mark[N];
int prime[N],tot;
void getpri(int n){
    for(int i=2;i<=n;i++){
        if(!mark[i])prime[++tot]=i;
        for(int j=1;j<=tot;j++){
            if(i*prime[j]>n) break;
            mark[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}

inline void FWT_xor(int *A,int len,bool opt=1){
    for(int i=1;i<len;i<<=1){
        for(int j=0;j<len;j+=i<<1){
            for(int k=0;k<i;++k){
                int u=A[j+k],v=A[j+k+i];
                A[j+k]=add(u,v);
                A[j+k+i]=sub(u,v);
                if(!opt){
                    A[j+k]=A[j+k]*inv2%p;
                    A[j+k+i]=A[j+k+i]*inv2%p;
                }
            }
        }
    }
}

int a[N<<1],b[N<<1];

int main(){
    int n,m,len;
    getpri(50000);
    for(int i=1;i<=tot;++i)a[prime[i]]=1;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(len=1;len<=m;len<<=1);
        memcpy(b,a,m+1<<2);
        memset(b+m+1,0,(len-m-1)<<2);
        FWT_xor(b,len);
        for(int i=0;i<len;++i)b[i]=qpow(b[i],n);
        FWT_xor(b,len,0);
        printf("%dn",b[0]);
    }
}

2018/8/18

test51(百度之星)

只做了A题和C题,思路和题解一样,感觉没有什么问题
因为hdu上没有放题,所以也没有评测,不知道能不能AC
所以暂时不放代码了

已经有题了,都AC了
这两道都很水

A题

比较水,可以set水过,也可以$O(n)$做,没什么难度
然而它卡快读!简直恶心

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=1e5+5;

ll n,ans1=0,ans2=0;
int fa[N],a[N];
set<int>s[N];
set<int>::iterator it;

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        ans1=0,ans2=0;
        scanf("%lld",&n);
        for(int i=1;i<=n;++i)s[i].clear();
        for(int i=2;i<=n;++i)scanf("%d",&fa[i]);
        for(int i=1;i<=n;++i)scanf("%d",&a[i]),s[fa[i]].insert(a[i]);
        for(int i=0;i<=n;++i){
            if(!s[i].empty()){
                it=s[i].end();
                if((*(--it))>0)ans1+=(*it),s[i].erase(it);
            }
            if(!s[i].empty()){
                it=s[i].begin();
                if((*it)<0) ans2+=(*it),s[i].erase(it);
            }
        }
        int mx=0,mi=0;
        for(int i=0;i<=n;++i){
            if(s[i].empty())continue;
            it=s[i].begin();
            mi=min(mi,(*it));
            it=s[i].end();
            mx=max(mx,(*(--it)));
        }
        printf("%lld %lldn",ans1+mx,ans2+mi);
    }
    return 0;
}

C题

用并查集维护联通块,每块单独维护
因为有一个$max$函数,所以我们分别考虑每个数的贡献,先排个序
因为有位运算,所以每位单独考虑,做一个前缀和
具体看代码吧

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=100005;
const int p=1e9+7;

struct BIT{int a[35];};

struct data{
    vector<BIT>bit;
    vector<int>val;

    inline ll solve(){
        ll ret,sum=0;
        for(int i=1;i<val.size();++i){
            int x=val[i];
            ret=0;
            for(int j=0;(1<<j)<=x;++j){
                if(x&(1<<j))(ret+=bit[i-1].a[j]*(1ll<<j))%=p;
            }
            (sum+=ret*x)%=p;
        }
        return sum;
    }

};

vector<data>S;

int fa[N],id[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

int w[N];
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int T;r(T);
    while(T--){
        int n,m;
        r(n);r(m);
        for(int i=1;i<=n;++i)r(w[i]),fa[i]=i;
        for(int i=1,x,y;i<=m;++i){
            r(x);r(y);
            if(find(x)!=find(y))fa[find(x)]=y;
        }
        int cnt=0;
        for(int i=1;i<=n;++i)if(find(i)==i)id[i]=cnt++;
        S.resize(cnt);
        for(int i=1;i<=n;++i)S[id[fa[i]]].val.push_back(w[i]);
        for(int i=0;i<cnt;++i){
            if(S[i].val.size()<2)continue;
            sort(S.at(i).val.begin(),S[i].val.end());
            S[i].bit.resize(S[i].val.size());
            for(int j=0;j<S[i].val.size();++j){
                int x=S[i].val[j];
                for(int k=0;(1<<k)<=x;++k)S[i].bit[j].a[k]=bool(x&(1<<k));
                if(j)for(int k=0;k<32;++k)S[i].bit[j].a[k]+=S[i].bit[j-1].a[k];
            }
        }

        ll ans=0;
        for(int i=0;i<cnt;++i){
            if(S[i].val.size()<2)continue;
            (ans+=S[i].solve())%=p;
        }
        printf("%lldn",ans);

        S.clear();
    }
}

2018/8/19

圆的异或并

扫描线
要求的时面积异或并,显然答案是
最外层的圆的面积之和-次外层的圆的面积之和+第三层的圆的面积之和……
把圆拆成一上一下两个半圆
当遇到左端点时插入两个半圆,遇到右端点时删除
考虑某个上半圆时,找到它上面的第一个半圆(这里要求插入,删除,前驱(后继),用set维护即可)

如果同样是上半圆,说明它所在的圆包含当前圆,当前圆层数是它所在的圆的层数+1
否则说明这两个圆相离,层数相同
根据之前所述求出层数的奇偶性,计算即可

另外,虽然扫描线移动导致高度变化,但是因为圆不相交,不会影响大小关系
所以没有set找的时候出错的可能

#include<bits/stdc++.h>

using namespace std;

const int N=200005;
const double eps=1e-8;

#define ll long long

inline ll sqr(int a){return (ll)a*a;};

struct Cir{
    int x,y,r;
}cir[N];

int now;
struct Cur{
    int id,x,dir;//left->1,right->-1

    Cur(int id=0,int x=0,int dir=0):id(id),x(x),dir(dir){}

    inline double h(){
        return cir[id].y+dir*sqrt(sqr(cir[id].r)-sqr(now-cir[id].x));
    }


}cur[N<<1];

inline bool operator <(Cur a,Cur b){
    double h1=a.h();
    double h2=b.h();
    if(fabs(h1-h2)>=eps)return h1<h2;//如果直接返回,insert时上下h值相同,会被去重
    return a.dir<b.dir;//这样就可以区分不同元素了
}

inline bool cmp(Cur a,Cur b){return a.x<b.x;}

set<Cur>S;//在set中的圆弧的x大小也不重要
set<Cur>::iterator it;

int f[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d%d%d",&cir[i].x,&cir[i].y,&cir[i].r);
        cur[i<<1].id=i;
        cur[i<<1].x=cir[i].x-cir[i].r;
        cur[i<<1].dir=1;
        cur[i<<1|1].id=i;
        cur[i<<1|1].x=cir[i].x+cir[i].r;
        cur[i<<1|1].dir=-1;
    }
    sort(cur,cur+(n<<1),cmp);

    for(int i=0;i<(n<<1);++i){
        now=cur[i].x;
        if(cur[i].dir==1){
            it=S.upper_bound(Cur(cur[i].id,0,-1));//这里是-1还是1也不重要(算出来高度都一样)
            if(it==S.end())f[cur[i].id]=1;
            else{
                if((*it).dir==-1)f[cur[i].id]=f[(*it).id];
                else f[cur[i].id]=-f[(*it).id];
            }
            S.insert(Cur(cur[i].id,0,1));
            S.insert(Cur(cur[i].id,0,-1));
        }
        else {
            S.erase(Cur(cur[i].id,0,1));
            S.erase(Cur(cur[i].id,0,-1));
        }
    }

    ll ans=0;
    for(int i=0;i<n;++i)ans+=sqr(cir[i].r)*f[i];

    printf("%lld",ans);
}

【模板】自适应辛普森法1

#include<bits/stdc++.h>

using namespace std;

typedef double db;

const db Eps=1e-6;

db a,b,c,d;
inline db f(db x){return (c*x+d)/(a*x+b);}

inline db simpson(db l,db r){return (r-l)*(f(l)+f(r)+4*f((l+r)*0.5))/6;}

inline db asr(db l,db r,db ans,db eps){
    db mid=(l+r)*0.5;
    db v1=simpson(l,mid);
    db v2=simpson(mid,r);
    db t=v1+v2-ans;
    return (fabs(t)<15*eps)?(v1+v2+t/15):(asr(l,mid,v1,eps*0.5)+asr(mid,r,v2,eps*0.5));
}

int main(){
    db l,r;
    scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&l,&r);
    printf("%.6lf",asr(l,r,simpson(l,r),Eps));
}

【模板】自适应辛普森法2

#include<bits/stdc++.h>

using namespace std;

typedef double db;

const db Eps=1e-8;

db a;
inline db f(db x){return pow(x,a/x-x);}

inline db simpson(db l,db r){return (r-l)*(f(l)+f(r)+4*f((l+r)*0.5))/6;}

inline db asr(db l,db r,db ans,db eps){
    db mid=(l+r)*0.5;
    db v1=simpson(l,mid);
    db v2=simpson(mid,r);
    db t=v1+v2-ans;
    return (fabs(t)<15*eps)?(v1+v2+t/15):(asr(l,mid,v1,eps*0.5)+asr(mid,r,v2,eps*0.5));
}

int main(){
    scanf("%lf",&a);
    if(a<0)return puts("orz"),0;
    db l=1e-9,r=20;
    printf("%.5lf",asr(l,r,simpson(l,r),Eps));
}

为什么别人的程序跑得那么快……

[NOI2005]月下柠檬树

假设树干投影后为x轴,x轴坐标是高度乘$\frac{1}{tan(\alpha)}$,y轴坐标不变
投影后得到一些圆,所求即为它们及公切线覆盖的部分
simpson计算即可

#include<bits/stdc++.h>

using namespace std;

typedef double db;

const db Eps=1e-3;
const int N=505;

inline db sqr(db x){
    return x*x;
}

db x[N],r[N],x_1[N],y_1[N],x_2[N],y_2[N];

int n;

inline db f(db X){
    db ret=0;
    for(int i=1;i<=n;++i){
        if(fabs(x[i]-X)<r[i])ret=max(ret,sqrt(sqr(r[i])-sqr(X-x[i])));
        if(x_1[i]<X&&x_2[i]>X){
            ret=max(ret,y_2[i]+(y_1[i]-y_2[i])*((x_2[i]-X)/(x_2[i]-x_1[i])));
        }
    }
    return ret;
}

inline db simpson(db l,db r){return (r-l)*(f(l)+f(r)+4*f((l+r)*0.5))/6;}

inline db asr(db l,db r,db ans,db eps){
    db mid=(l+r)*0.5;
    db v1=simpson(l,mid);
    db v2=simpson(mid,r);
    db t=v1+v2-ans;
    return (fabs(t)<15*eps)?(v1+v2+t/15):(asr(l,mid,v1,eps*0.5)+asr(mid,r,v2,eps*0.5));
}

int main(){
    db alp,h;
    scanf("%d%lf",&n,&alp);
    alp=1/tan(alp);
    for(int i=1;i<=n+1;++i){
        scanf("%lf",&h);
        x[i]=x[i-1]+h*alp;
    }
    db L=x[n+1],R=L;
    for(int i=1;i<=n;++i){
        scanf("%lf",&r[i]);
        L=min(x[i]-r[i],L);
        R=max(x[i]+r[i],R);
    }
    db Sin,Cos;
    for(int i=1;i<=n;++i){
        Sin=(r[i]-r[i+1])/(x[i+1]-x[i]);
        Cos=sqrt(1-sqr(Sin));
        x_1[i]=x[i]+r[i]*Sin;
        y_1[i]=r[i]*Cos;
        x_2[i]=x[i+1]+r[i+1]*Sin;
        y_2[i]=r[i+1]*Cos;
    }
    printf("%.2lf",2*asr(L,R,simpson(L,R),Eps));

}

2018/8/20

[WC2008]游览计划

这是一个斯坦纳树的题
带边权无向图上有几个关键点,要求选择一些边使这些点在同一个联通块内,同时要求所选的边的边权和最小

令$dp[i][s]$表示以$i$为根,包含集合$s$的状态,
有两种转移

$1. dp[i][s]=min(dp[i][x]+dp[i][s-x]-val[i])$条件是$x$是$s$的子集
$2.dp[i][s]=min(dp[j][s]+val[i])$条件是$i$与$j$相邻

第一种枚举子集转移
第二种跑$SPFA$

要记忆路径,可以写结构体,也可以写$Hash$表,然后储存
最后输出即可

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=11;
const int M=2050;
const int INF=1e9;
const int Hash1=1024;
const int Hash2=102501;
const int MaxHash=N*(Hash1+Hash2)+M+5;

int n,m,k;
int a[N][N];
int f[N][N][M];
int pre[N][N][M];
bool vis[MaxHash];

inline int Hash(int x,int y,int s){
    return x*Hash2+y*Hash1+s;
}

queue<int>Q;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int id;
inline void spfa(int s){
    while(!Q.empty()){
        int h=Q.front();Q.pop();
        int x=h/Hash2;
        int y=h%Hash2/Hash1;
        for(int i=0;i<4;++i){
            int xx=x+dx[i],yy=y+dy[i];
            if(xx<1||yy<1||xx>n||yy>m)continue;
            int ss=s|a[xx][yy];
            int t=f[x][y][s]+f[xx][yy][0];
            if(f[xx][yy][ss]>t){
                f[xx][yy][ss]=t;
                pre[xx][yy][ss]=h;
                int hh=Hash(xx,yy,ss);
                if(!vis[hh]&&s==ss){
                    vis[hh]=1;
                    Q.push(hh);
                }
            }
        }
        vis[h]=0;
    }
}

bool ans[N][N];
inline void dfs(int x,int y,int s){
    ans[x][y]=1;
    int hh=pre[x][y][s];
    if(!hh)return;
    int xx=hh/Hash2;
    int yy=hh%Hash2/Hash1;
    int ss=hh%Hash2%Hash1;
    dfs(xx,yy,ss);
    if(xx==x&&yy==y)dfs(xx,yy,s-ss);
}

inline void print(){
    for(int i=1;i<=n;++i,puts("")){
        for(int j=1;j<=m;++j){
            if(ans[i][j]){
                if(f[i][j][0])putchar('o');
                else putchar('x');
            }
            else putchar('_');
        }
    }
}

int main(){
    r(n);r(m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            r(f[i][j][0]);
            fill(f[i][j]+1,f[i][j]+(1<<(n+1)),INF);
            if(!f[i][j][0])a[i][j]=1<<k,f[i][j][1<<(k++)]=0;
        }
    }

    int S=(1<<k)-1;
    for(int s=1;s<=S;++s){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                for(int x=s&(s-1),t;x;x=s&(x-1)){
                    t=f[i][j][x]+f[i][j][s^x]-f[i][j][0];
                    if(f[i][j][s]>t){
                        f[i][j][s]=t;
                        pre[i][j][s]=Hash(i,j,x);
                    }
                }
                if(f[i][j][s]!=INF){
                    int h=Hash(i,j,s);
                    Q.push(h);
                    vis[h]=1;
                }
            }
        }
        spfa(s);
    }

    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(!f[i][j][0]){
                printf("%dn",f[i][j][S]);
                dfs(i,j,S);
                print();
                return 0;
            }
        }
    }
}

2018/8/22

QTREE4

从昨天晚上开始写,今天早上才写完
这个系列我要用多种方法写几遍,完成后会有一个总集
目前完成1~4的树剖版本

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ls (rt<<1)
#define rs (rt<<1|1)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e5+5;
const int INF=1e9;

int n,q;

int ecnt;
int fir[N],nex[N<<1],to[N<<1],w[N<<1];

inline void addedge(int u,int v,int c){
    nex[++ecnt]=fir[u];fir[u]=ecnt;to[ecnt]=v;w[ecnt]=c;
    nex[++ecnt]=fir[v];fir[v]=ecnt;to[ecnt]=u;w[ecnt]=c;
}

int dfs_clock;
int siz[N],son[N],fa[N],dep[N],sum[N];

void dfs1(int x,int f){
    fa[x]=f;
    dep[x]=dep[f]+1;
    siz[x]=1;
    for(int i=fir[x],v;i;i=nex[i]){
        if((v=to[i])==f)continue;
        sum[v]=sum[x]+w[i];
        dfs1(v,x);
        siz[x]+=siz[v];
        if(siz[v]>siz[son[x]])son[x]=v;
    }
}

int top[N],tail[N],dfn[N],ptn[N];

void dfs2(int x,int t){
    dfn[x]=++dfs_clock;
    ptn[dfs_clock]=x;
    top[x]=t;
    tail[t]=x;
    if(son[x])dfs2(son[x],t);
    for(int i=fir[x],v;i;i=nex[i]){
        if((v=to[i])==fa[x]||v==son[x])continue;
        dfs2(v,v);
    }
}

inline int dist(int x,int y){
    if(x<y)swap(x,y);
    x=ptn[x];
    y=ptn[y];
    return sum[x]-sum[y];
}

multiset<int>val[N],ans;

bool col[N];
int cnt;

struct Data{
    int lv,rv,v;
}tr[N<<2];

inline Data pushup(const Data &a,const Data &b,int l,int r,int mid){
    Data ret;
    ret.lv=max(a.lv,dist(l,mid)+dist(mid,mid+1)+b.lv);
    ret.rv=max(a.rv+dist(mid,mid+1)+dist(mid+1,r),b.rv);
    ret.v=max(max(a.v,b.v),a.rv+dist(mid,mid+1)+b.lv);
    return ret;
}

inline void update(int rt,int x){
    int d1,d2;
    d1=d2=(!col[x]?0:-INF);
    if(val[x].size())d1=max(d1,*val[x].rbegin());
    if(val[x].size()>1)d2=max(d2,*(++val[x].rbegin()));
    tr[rt].lv=tr[rt].rv=d1;
    tr[rt].v=(!col[x]?max(d1,d1+d2):d1+d2);
}

void change(int rt,int l,int r,int x){
    if(l==r){
        update(rt,ptn[x]);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)change(ls,l,mid,x);
    else change(rs,mid+1,r,x);

    tr[rt]=pushup(tr[ls],tr[rs],l,r,mid);
}

Data query(int rt,int l,int r,int x,int y){
    if(x<=l&&y>=r)return tr[rt];
    int mid=(l+r)>>1;
    if(y<=mid)return query(ls,l,mid,x,y);
    else if(x>mid)return query(rs,mid+1,r,x,y);
    else return pushup(query(ls,l,mid,x,y),query(rs,mid+1,r,x,y),max(x,l),min(y,r),mid);
}

inline void modify(int x){
    Data tmp;
    int to;
    while(top[x]!=1){
        to=fa[top[x]];
        tmp=query(1,1,n,dfn[top[x]],dfn[tail[top[x]]]);
        ans.erase(ans.find(tmp.v));
        val[to].erase(val[to].find(tmp.lv+sum[top[x]]-sum[to]));
        change(1,1,n,dfn[x]);
        tmp=query(1,1,n,dfn[top[x]],dfn[tail[top[x]]]);
        ans.insert(tmp.v);
        val[to].insert(tmp.lv+sum[top[x]]-sum[to]);
        x=to;
    }
    tmp=query(1,1,n,dfn[top[x]],dfn[tail[top[x]]]);
    ans.erase(ans.find(tmp.v));
    change(1,1,n,dfn[x]);
    tmp=query(1,1,n,dfn[top[x]],dfn[tail[top[x]]]);
    ans.insert(tmp.v);
}

inline int solve(int t){
    for(int x=t;x;x=son[x]){
        for(int i=fir[x],v;i;i=nex[i]){
            if((v=to[i])==son[x]||v==fa[x])continue;
            val[x].insert(solve(v)+w[i]);
        }
        change(1,1,n,dfn[x]);
    }
    Data tmp=query(1,1,n,dfn[t],dfn[tail[t]]);
    ans.insert(tmp.v);
    return tmp.lv;
}

int main(){
    r(n);
    cnt=n;
    for(int i=1,u,v,c;i<n;++i){
        r(u);r(v);r(c);
        addedge(u,v,c);
    }
    dfs1(1,0);
    dfs2(1,1);
    solve(1);
    r(q);
    while(q--){
        char gc;
        while(c!='C'&&c!='A')gc;
        int x;
        if(c=='C'){
            r(x);
            if(col[x])cnt++;
            else cnt--;
            col[x]^=1;
            modify(x);
        }
        else{
            if(cnt==0)puts("They have disappeared.");
            else if(cnt==1)puts("0");
            else printf("%dn",*ans.rbegin());
        }
    }
}

Formula 1

题意:给出有障碍的$n*m$的棋盘,求哈密顿回路个数

插头dp,论文里的入门第一题
其实插头dp没有那么玄学
只是讨论的情况相对较多
转移方程就比较多
代码中每一个if就是一种转移
具体的情况论文已经够清楚了,画画图就明白了
其实就是码量大,并不比其它的dp复杂

#include<bits/stdc++.h>

typedef long long ll;

const int N=15;
const int S=100043;

char g[N][N];
int n,m,ex,ey;
bool now;
ll ans;

int h[S];
int way[2][S];
ll f[2][S];
int id[2];

inline void insert(bool now,int s,ll sum){
    int ss=s%S;
    while(way[now][h[ss]]!=s&&h[ss]!=-1)if(++ss==S)ss=1;

    if(h[ss]==-1){
        h[ss]=++id[now];
        way[now][id[now]]=s;
        f[now][id[now]]=sum;
    }
    else f[now][h[ss]]+=sum;
}

inline int get(int s,int p){
    return (s>>((p-1)<<1))&3;
}

inline void set(int &s,int p,int v){
    s^=get(s,p)<<((p-1)<<1);
    s^=v<<((p-1)<<1);
}

inline void solve(){
    f[0][1]=1;id[0]=1;way[0][1]=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            id[now^=1]=0;
            memset(h,-1,sizeof(h));
            for(int k=1;k<=id[now^1];++k){
                int s=way[now^1][k];
                ll sum=f[now^1][k];
                int left=get(s,j);
                int up=get(s,j+1);
                if(g[i][j]!='.'){if(!left&&!up)insert(now,s,sum);continue;}
                else if(!left&&!up){if(g[i][j+1]=='.'&&g[i+1][j]=='.')set(s,j,1),set(s,j+1,2),insert(now,s,sum);}
                else if(left&&!up){
                    if(g[i+1][j]=='.')insert(now,s,sum);
                    if(g[i][j+1]=='.')set(s,j,0),set(s,j+1,left),insert(now,s,sum);
                }
                else if(!left&&up){
                    if(g[i][j+1]=='.')insert(now,s,sum);
                    if(g[i+1][j]=='.')set(s,j,up),set(s,j+1,0),insert(now,s,sum);
                }
                else if(left==2&&up==1)set(s,j,0),set(s,j+1,0),insert(now,s,sum);
                else if(left==1&&up==2){if(i==ex&&j==ey)ans+=sum;}
                else if(left==1&&up==1){
                    for(int l=j+2,cnt=1;l<=m+1;++l){
                        int tmp=get(s,l);
                        if(tmp==1)++cnt;
                        else if(tmp==2)--cnt;
                        if(cnt==0){
                            set(s,j,0);
                            set(s,j+1,0);
                            set(s,l,1);
                            insert(now,s,sum);
                            break;
                        }
                    }
                }
                else if(left==2&&up==2){
                    for(int l=j-1,cnt=1;l;--l){
                        int tmp=get(s,l);
                        if(tmp==1)--cnt;
                        else if(tmp==2)++cnt;
                        if(cnt==0){
                            set(s,j,0);
                            set(s,j+1,0);
                            set(s,l,2);
                            insert(now,s,sum);
                            break;
                        }
                    }
                }
            }
        }
        for(int j=1;j<=id[now];++j)way[now][j]<<=2;
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%s",g[i]+1);
    for(int i=n;i&&(!ex);--i)for(int j=m;j&&(!ex);--j)if(g[i][j]=='.')ex=i,ey=j;
    solve();
    printf("%lld",ans);
}

2018/8/23

Eat the Trees

这个才应该是插头dp的入门题吧,比起Formula 1少了不少讨论,用二进制表示状态,也不用Hash
前两维数组的空间似乎可以优化掉,常数也应该更小,但是我懒得写

#include<cstdio>
#include<cstring>
#include<iostream>

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=12;
const int S=1<<N;

int n,m;
ll f[N][N][S];

inline ll solve(){
    f[0][m][0]=1;
    for(int i=1,g;i<=n;++i){
        memset(f[i],0,sizeof(f[i]));
        for(int s=0;s<(1<<m);++s)f[i][0][s<<1]=f[i-1][m][s];
        for(int j=1;j<=m;++j){
            int x=1<<(j-1);
            int y=1<<j;
            r(g);
            for(int s=0;s<(1<<(m+1));++s){
                bool p=s&x;
                bool q=s&y;
                if(!g){if(!p&&!q)f[i][j][s]+=f[i][j-1][s];}
                else{
                    if(p^q)f[i][j][s]+=f[i][j-1][s]+f[i][j-1][s^x^y];
                    else f[i][j][s]+=f[i][j-1][s^x^y];
                }
            }
        }
    }
    return f[n][m][0];
}
int main(){
    int T;r(T);
    for(int cas=1;cas<=T;++cas){
        r(n);r(m);
        printf("Case %d: There are %lld ways to eat the trees.n",cas,solve());
    }
}

2018/8/24

昨天装Linux装了一晚上还炸了,今天重装了一早上。
这两天感觉被发了一张题单,感觉再也不用到处找题做了

可持久化数组

Linux下AC的第一题
主席树的基础应用,也只放下代码

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e6+7;

int a[N];
int rt[N];
int id;

struct seg{int val,ls,rs;}tr[N<<5];

#define mid ((l+r)>>1)

inline int build(int l,int r){
    int rt=++id;
    if(l<r)tr[rt].ls=build(l,mid),tr[rt].rs=build(mid+1,r);
    else tr[rt].val=a[l];
    return rt;
}

inline int update(int pre,int l,int r,int x,int v){
    int rt=++id;
    tr[rt]=tr[pre];
    if(l<r)x<=mid?tr[rt].ls=update(tr[pre].ls,l,mid,x,v):tr[rt].rs=update(tr[pre].rs,mid+1,r,x,v);
    else tr[rt].val=v;
    return rt;
}

inline int query(int rt,int l,int r,int x){
    if(l<r)return x<=mid?query(tr[rt].ls,l,mid,x):query(tr[rt].rs,mid+1,r,x);
    else return tr[rt].val;

}

int main(){
    int n,m,ver,opt,loc,val;
    r(n);r(m);
    for(int i=1;i<=n;++i)r(a[i]);
    rt[0]=build(1,n);
    for(int i=1;i<=m;++i){
        r(ver);r(opt);r(loc);
        if(opt==1){
            r(val);
            rt[i]=update(rt[ver],1,n,loc,val);
        }
        else{
            printf("%dn",query(rt[ver],1,n,loc));
            rt[i]=rt[ver];
        }
    }
}

2018/8/25

可持久化并查集

把fa数组可持久化,注意不能路径压缩,所以要启发式合并

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=2e5+7;

int rt[N];
int id;

struct seg{int fa,dep,ls,rs;}tr[N<<5];

#define mid ((l+r)>>1)

inline int build(int l,int r){
    int rt=++id;
    if(l<r)tr[rt].ls=build(l,mid),tr[rt].rs=build(mid+1,r);
    else tr[rt].fa=l;
    return rt;
}

inline int update(int pre,int l,int r,int x,int v){
    int rt=++id;
    tr[rt]=tr[pre];
    if(l<r)x<=mid?tr[rt].ls=update(tr[pre].ls,l,mid,x,v):tr[rt].rs=update(tr[pre].rs,mid+1,r,x,v);
    else tr[rt].fa=v;
    return rt;
}

inline int query(int rt,int l,int r,int x){
    if(l<r)return x<=mid?query(tr[rt].ls,l,mid,x):query(tr[rt].rs,mid+1,r,x);
    else return rt;

}

inline void add(int rt,int l,int r,int x){
    if(l<r)x<=mid?add(tr[rt].ls,l,mid,x):add(tr[rt].rs,mid+1,r,x);
    else ++tr[rt].dep;
}

int n,m;

inline int find(int ver,int x){
    int f=query(rt[ver],1,n,x);
    return x==tr[f].fa?f:find(ver,tr[f].fa);
}

inline void uni(int ver,int a,int b){
    rt[ver]=rt[ver-1];
    int f1=find(ver,a);
    int f2=find(ver,b);
    if(tr[f1].fa==tr[f2].fa)return;
    if(tr[f1].dep<tr[f2].dep)swap(f1,f2);
    rt[ver]=update(rt[ver-1],1,n,tr[f2].fa,tr[f1].fa);
    if(tr[f1].dep==tr[f2].dep)add(rt[ver],1,n,tr[f1].fa);
}

inline void query(int ver,int a,int b){
    printf("%dn",find(ver,a)==find(ver,b));
}

int main(){
    r(n);r(m);
    rt[0]=build(1,n);
    for(int i=1;i<=m;++i){
        int opt,a,b;
        r(opt);r(a);
        switch(opt){
            case 1:{
                r(b);
                uni(i,a,b);
                break;
            }
            case 2:{
                rt[i]=rt[a];
                break;
            }
            case 3:{
                r(b);
                rt[i]=rt[i-1];
                query(i,a,b);
                break;
            }
        }
    }
}

左偏树

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e5+7;

struct Node{
    int key,dis,ls,rs;
    Node(int d=-1):dis(d){};
}tr[N],null;

int fa[N];

int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

void uni(int x,int y){
    fa[find(x)]=find(y);
}

inline int Merge(int x,int y){
    if(!x)return y;
    if(!y)return x;
    if(tr[x].key>tr[y].key||(tr[x].key==tr[y].key&&x>y))swap(x,y);
    tr[x].rs=Merge(tr[x].rs,y);
    fa[tr[x].rs]=x;
    if(tr[tr[x].ls].dis<tr[tr[x].rs].dis)swap(tr[x].ls,tr[x].rs);
    tr[x].dis=tr[tr[x].rs].dis+1;
    return x;
}

inline void Pop(int x){
    x=find(x);
    int t=Merge(tr[x].ls,tr[x].rs);
    fa[x]=fa[tr[x].ls]=fa[tr[x].rs]=t;
    tr[x]=null;
}

inline int Top(int x){
    return tr[find(x)].key;
}

int main(){
    int n,m;
    r(n);r(m);
    for(int i=1;i<=n;++i)r(tr[i].key),tr[i].dis=0,fa[i]=i;
    for(int i=1,opt,x,y;i<=m;++i){
        r(opt);r(x);
        if(opt==1){
            r(y);
            if(!tr[x].key||!tr[y].key)continue;
            if(find(x)!=find(y))Merge(fa[x],fa[y]);
        }
        else {
            if(!tr[x].key)puts("-1");
            else {
                printf("%dn",Top(x));
                Pop(x);
            }
        }
    }
}

2018/8/26

线性基

#include

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template
inline void read(T&amp;x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=60;

ll a[N];

inline void insert(ll x){
    for(int i=N-1;~i;--i){
        if(!(x&gt;&gt;i))continue;
        if(!a[i])a[i]=x;
        x^=a[i];
    }
}

int main(){
    int n;r(n);
    ll x;
    for(int i=0;ix)x^=a[i];
    printf("%lld",x);
}

test53

2018/8/27

后缀排序

后缀数组模板题
倍增算法代码

#include

using namespace std;

const int N=2e6+7;

char s[N];

int sa[N];
int rank[N];
int rsort[N];
int y[N];
int wr[N];

inline bool cmp(int a,int b,int n){
    return wr[a]==wr[b]&amp;&amp;wr[a+n]==wr[b+n];
}

inline void SA(int n,int m){
    for(int i=1;i&lt;=n;++i)rank[i]=s[i];
    for(int i=1;i&lt;=n;++i)rsort[rank[i]]++;
    for(int i=1;i&lt;=m;++i)rsort[i]+=rsort[i-1];
    for(int i=n;i;--i)sa[rsort[rank[i]]--]=i;
    int p=0;
    for(int len=1;p&lt;n;len&lt;&lt;=1){
        p=0;
        for(int i=n-len+1;i&lt;=n;++i)y[++p]=i;
        for(int i=1;ilen)y[++p]=sa[i]-len;
        for(int i=1;i&lt;=n;++i)wr[i]=rank[y[i]];
        memset(rsort+1,0,m&lt;&lt;2);
        for(int i=1;i&lt;=n;++i)rsort[wr[i]]++;
        for(int i=1;i&lt;=m;++i)rsort[i]+=rsort[i-1];
        for(int i=n;i;--i)sa[rsort[wr[i]]--]=y[i];
        memcpy(wr+1,rank+1,n&lt;&lt;2);
        p=1;rank[sa[1]]=1;
        for(int i=2;i&lt;=n;++i){
            if(!cmp(sa[i],sa[i-1],len))++p;
            rank[sa[i]]=p;
        }
        m=p;
    }
}

int main(){
    scanf(&quot;%s&quot;,s+1);
    int n=strlen(s+1);
    SA(n,260);
    for(int i=1;i&lt;=n;++i)printf(&quot;%d &quot;,sa[i]);
}

最大连通子块和

动态dp
题解见wjx学姐的博客
写得很详细
话说好多人喜欢用手写堆,我还是喜欢用multiset
这道题和QTREE4相似,然而我写QTREE4时完全没有注意到这是动态dp

$f[x]$表示$x$的子树中,包含x的连通块的权值和最大值(可以为空)
$g[x]$表示$x$的子树中,包含x的连通块的权值和最大值(不可以为空)
$ans[x]$表示$x$的子树中,权值和最大值(可以为空)
$ch[x]$表示$max(ans[y])$($y$是$x$的轻儿子)

$g[x]=val_x+sum f[y]$($y$是$x$的儿子)
$f[x]=max(g[x],0)$
$ans[x]=max(f[x],ch[x],ans[son[x]])$

$ch[x]$用一个集合来写

通过dfs序,把子树问题转化为序列上的区间问题
求$f[x]$实际上是在数组$g$上的一个区间求最大前缀和
更新$ch[x]$即求某个$ans[y]$,实际上是在数组$g$上的一个区间求最大连续子段和
显然$g$可以直接修改
树剖+线段树更新$f$,$ch$即可($ans$不用更新,因为可以直接在线段树上查询)

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=200005;

int ecnt;
int fir[N],nex[N<<1],to[N<<1],w[N<<1];

inline void addedge(int u,int v){
    nex[++ecnt]=fir[u];fir[u]=ecnt;to[ecnt]=v;
    nex[++ecnt]=fir[v];fir[v]=ecnt;to[ecnt]=u;
}

multiset<ll>ch[N];

int dfs_clock;
int siz[N],son[N],fa[N],dep[N];

void dfs1(int x,int f){
    fa[x]=f;
    dep[x]=dep[f]+1;
    siz[x]=1;
    for(int i=fir[x],v;i;i=nex[i]){
        if((v=to[i])==f)continue;
        dfs1(v,x);
        siz[x]+=siz[v];
        if(siz[v]>siz[son[x]])son[x]=v;
    }
}

int top[N],tail[N],dfn[N],ptn[N];
ll g[N],f[N],val[N],ans[N];

void dfs2(int x,int t){
    dfn[x]=++dfs_clock;
    ptn[dfs_clock]=x;
    top[x]=t;
    tail[t]=x;
    if(son[x])dfs2(son[x],t);
    g[x]=val[x];
    ans[x]=ans[son[x]];
    for(int i=fir[x],v;i;i=nex[i]){
        if((v=to[i])==fa[x]||v==son[x])continue;
        dfs2(v,v);
        g[x]+=f[v];
        ch[x].insert(ans[v]);
    }
    f[x]=max(0ll,g[x]+f[son[x]]);
    ans[x]=max(ans[x],f[x]);
    if(ch[x].size())ans[x]=max(ans[x],*ch[x].rbegin());
}

struct seg{
    ll sum,lv,rv,mv;
    seg operator + (const seg & x){
        seg ret;
        ret.sum=sum+x.sum;
        ret.lv=max(lv,sum+x.lv);
        ret.rv=max(rv+x.sum,x.rv);
        ret.mv=max(max(mv,x.mv),rv+x.lv);
        return ret;
    }
}tr[N<<2];

inline void build(int rt,int l,int r){
    if(l==r){
        tr[rt].sum=g[ptn[l]];
        tr[rt].mv=tr[rt].lv=tr[rt].rv=max(0ll,g[ptn[l]]);
        if(ch[ptn[l]].size())tr[rt].mv=max(g[ptn[l]],*ch[ptn[l]].rbegin());
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    tr[rt]=tr[ls]+tr[rs];
}

inline void change(int rt,int l,int r,int x){
    if(l==r){
        tr[rt].sum=g[ptn[l]];
        tr[rt].mv=tr[rt].lv=tr[rt].rv=max(0ll,g[ptn[l]]);
        if(ch[ptn[l]].size())tr[rt].mv=max(g[ptn[l]],*ch[ptn[l]].rbegin());
        return;
    }
    x<=mid?change(ls,l,mid,x):change(rs,mid+1,r,x);
    tr[rt]=tr[ls]+tr[rs];
}

inline seg query(int rt,int l,int r,int x,int y){
    if(l>=x&&r<=y)return tr[rt];
    if(y<=mid)return query(ls,l,mid,x,y);
    else if(x>mid)return query(rs,mid+1,r,x,y);
    else return query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y);
}

int n,m;

inline void modify(int x,int derta){
    seg tmp;
    while(x){
        g[x]+=derta;
        tmp=query(1,1,n,dfn[top[x]],dfn[tail[top[x]]]);
        if(fa[top[x]])ch[fa[top[x]]].erase(ch[fa[top[x]]].find(tmp.mv));
        change(1,1,n,dfn[x]);
        tmp=query(1,1,n,dfn[top[x]],dfn[tail[top[x]]]);
        if(fa[top[x]])ch[fa[top[x]]].insert(tmp.mv);
        derta=tmp.lv-f[top[x]];
        f[top[x]]=tmp.lv;
        x=fa[top[x]];
    }
} 

int main(){
    r(n);r(m);
    for(int i=1;i<=n;++i)r(val[i]);
    for(int i=1,a,b;i<n;++i)r(a),r(b),addedge(a,b);
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    while(m--){
        char gc;
        while(c!='M'&&c!='Q')gc;
        int x,y;
        r(x);
        if(c=='M')r(y),modify(x,y-val[x]),val[x]=y;
        else printf("%lldn",query(1,1,n,dfn[x],dfn[tail[top[x]]]).mv);
    }
}

2018/8/28

TEST 54

今天考了一套简单到爆炸的题,然而我还是爆炸了
看来要去刷基础题了

T1

和上次的T1一模一样
就是最小生成树

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=350;

char ch[N];
int fa[N];

struct edge{
    int u,v,w;
    bool operator < (const edge &x)const {return w<x.w;}
}E[N*N];

int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

inline bool uni(int f1,int f2){
    if(find(f1)==find(f2))return 1;
    return fa[fa[f1]]=fa[f2],0;
}

int n,tot,cnt,ans;

int main(){
    freopen("newstart.in","r",stdin);
    freopen("newstart.out","w",stdout);
    r(n);
    for(int i=1,c;i<=n;++i){
        fa[i]=i;
        r(c);
        E[++tot]=(edge){i,n+1,c};
    }
    fa[n+1]=n+1;
    for(int i=1;i<=n;++i){
        for(int j=1,c;j<=n;++j){
            r(c);
            if(j>i)E[++tot]=(edge){i,j,c};
        }
    }
    sort(E+1,E+tot+1);
    for(int i=1;i<=tot;++i){
        if(!uni(E[i].u,E[i].v)){
            ++cnt;
            ans+=E[i].w;
            if(cnt==n)break;
        }
    }
    printf("%d\n",ans);
}

T2

dp方程很简单,然而我硬是没有写出来
结果我居然打了个dfs,dp果然是我的弱项
另外数组$f$的第一维可以直接去掉,显然是没有影响的

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1005;

int ans;
int BE[N][N];
int NEW[N][N];
int f[N][N];

int n,m;

int main(){
    freopen("industry.in","r",stdin);
    freopen("industry.out","w",stdout);
    r(n);r(m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)r(BE[i][j]),BE[i][j]+=BE[i][j-1];
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)r(NEW[i][j]),NEW[i][j]+=NEW[i-1][j];
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)f[i][j]=max(f[i-1][j]+BE[i][j],f[i][j-1]+NEW[i][j]);
    }
    printf("%d\n",f[n][m]);
}

T3

考场上写了$O(n^3)$暴力
就是$f[i][x][y]$表示前$i$个选了$x$个辐射塔,$y$个干扰塔,然后全部算出来
然而很显然的是激光塔放在哪里都一样,而辐射塔和干扰塔放得越靠前越好
所以用$f[i][x]$表示前$i$个选了$x$个辐射塔,$i-y$个干扰塔,剩下全放激光塔
复杂度$O(n^2)$

然后发现要写高精度,但是考虑最大值远小于$2^{128}$,用__int128水过即可

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll __int128

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1025;

ll f[N][N];
ll ans;

void write(__int128 x){
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

int main(){
    freopen("antbuster.in","r",stdin);
    freopen("antbuster.out","w",stdout);
    int n,t;
    ll r,g,b;
    r(n);r(r);r(g);r(b);r(t);
    ans=t*r*n;
    for(int i=1;i<=n;++i){
        f[i][0]=(i*(i-1)>>1)*t*g;
        ans=max(ans,f[i][0]+(r+i*g)*(n-i)*t);
        for(int j=1;j<=i;++j){
            f[i][j]=max(f[i-1][j-1]+(i-j)*(t+b*(j-1))*g,f[i-1][j]+(i-1-j)*(t+b*j)*g);
            ans=max(ans,f[i][j]+(r+(i-j)*g)*(n-i)*(t+b*j));
        }
    }
    write(ans);
}

单源最短路径(标准版)

终于抽出时间来写dijkstra了

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int INF=0x3f3f3f3f;
const int N=100005;
const int M=200005;

int dis[N],fir[N],nex[M],to[M],w[M];
int n,m,s;

struct data{
    int a,b;
    bool operator < (const data& x)const{
        return a>x.a;
    }
};

priority_queue<data>Q;
inline void dijkstra(int s){
    memset(dis+1,INF,n<<2);

    dis[s]=0;
    Q.push(data{0,s});
    while(!Q.empty()){
        int x=Q.top().b;
        int d=Q.top().a;
        Q.pop();
        if(d!=dis[x])continue;
        for(int i=fir[x],v,t;i;i=nex[i]){
            if((t=d+w[i])<dis[v=to[i]]){
                dis[v]=t;
                Q.push(data{t,v});
            }
        }
    }
}


int main(){
    r(n);r(m);r(s);
    for(int i=1,x;i<=m;++i){
        r(x),r(to[i]),r(w[i]);
        nex[i]=fir[x],fir[x]=i;
    }
    dijkstra(s);
    for(int i=1;i<=n;++i)printf("%d ",dis[i]);
}

2018/8/29

字符串哈希

#include<bits/stdc++.h>

using namespace std;

#define ull unsigned long long

const ull Base=131;
const int N=10005;

inline ull Hash(char s[]){
    int n=strlen(s);
    ull ans=0;
    for(int i=0;i<n;++i)ans=ans*Base+(ull)s[i];
    return ans;
}

set<ull> S;

char t[N];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i)scanf("%s",t),S.insert(Hash(t));
    printf("%d",S.size());
}

TEST 55

T1

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=100005;

int fir[N],nex[N],to[N];
int fa[N],siz[N],L[N],R[N];

void dfs(int x,int f){
    siz[x]=1;
    R[x]=x;L[x]=x;
    for(int i=fir[x],v;i;i=nex[i]){
        if((v=to[i])==f)continue;
        dfs(v,x);
        siz[x]+=siz[v];
        R[x]=max(R[x],R[v]);
        L[x]=min(L[x],L[v]);
    }
}

int main(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
    int n;r(n);
    for(int i=1,u,v;i<n;++i){
        r(u),r(v);
        nex[i]=fir[u],fir[u]=i,to[i]=v,fa[v]=u;
    }
    for(int i=1;i<=n;++i){
        if(!fa[i]){
            dfs(i,0);
            break;
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i)ans+=(siz[i]==R[i]-L[i]+1);
    printf("%d\n",ans);
}

T2

#include<bits/stdc++.h>

using namespace std;

const int p=1000000007;
const int N=1005;

typedef long long ll;

ll f[N][N];

char s[N];

inline ll add(ll a,ll b){
    a+=b;
    if(a>=p)a-=p;
    return a;
}

int main(){
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    scanf("%s",s+1);
    int n=strlen(s+1);
    f[1][1]=1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=i;++j)f[i][j]=add(f[i][j],f[i][j-1]);
        if(s[i]!='D')for(int j=1;j<=i+1;++j)f[i+1][j]=add(f[i+1][j],f[i][j-1]);
        if(s[i]!='I')for(int j=1;j<=i+1;++j)f[i+1][j]=add(f[i+1][j],add(f[i][i],p-f[i][j-1]));
    }
    ll ans=0;
    for(int i=1;i<=n+1;++i)ans=add(ans,f[n+1][i]);
    printf("%lld\n",ans);
}
/*
??D??I?I

*/

T3

题上说的是$x$的子序列中是$y$的子序列的个数,所以有一行转移要注释掉
就是这道题害得我没有AK,$300pts$->$250pts$,$rank1$->$rank2$
RLD就是这道题比我多加了一个特判,一举$260pts$,$rank1$,真是太强了

#include<bits/stdc++.h>

using namespace std;

const int N=1005;
const int p=1e9+7;

char s1[N],s2[N];
int f[N][N];
long long cnt[N][N];

int main(){
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    scanf("%s",s1);
    scanf("%s",s2);
    int n=strlen(s1),m=strlen(s2);
    for(int i=0;i<=m;++i)cnt[0][i]=1;
    for(int i=0;i<=n;++i)cnt[i][0]=1;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(s1[i]==s2[j]){
                f[i+1][j+1]=f[i][j]+1;
                cnt[i+1][j+1]=cnt[i][j];
//              if(f[i+1][j+1]==f[i+1][j])(cnt[i+1][j+1]+=cnt[i+1][j])%=p;
                if(f[i+1][j+1]==f[i][j+1])(cnt[i+1][j+1]+=cnt[i][j+1])%=p;
            }
            else{
                f[i+1][j+1]=max(f[i][j+1],f[i+1][j]);
                if(f[i+1][j+1]==f[i][j+1])(cnt[i+1][j+1]+=cnt[i][j+1])%=p;
                if(f[i+1][j+1]==f[i+1][j])(cnt[i+1][j+1]+=cnt[i+1][j])%=p;
                if(f[i+1][j+1]==f[i][j])(cnt[i+1][j+1]+=p-cnt[i][j])%=p;
            }
        }
    }
    printf("%lld\n",cnt[n][m]);
}
/*
rldakioi
rldakioirldakioi

*/

背包问题 V2

重新学dp啦
二进制优化多重背包

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

typedef long long ll;

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=50005;

ll f[N];

int main(){
    int n,W,tot=0;
    r(n);r(W);
    for(int i=1,w0,p0,c0,w,p;i<=n;++i){
        r(w0),r(p0),r(c0);
        for(int k=0;(1<<k)<c0;++k){
            w=w0*(1<<k);
            p=p0*(1<<k);
            c0-=(1<<k);
            for(int j=W;j>=w;--j)f[j]=max(f[j],f[j-w]+p);
        }
        w=w0*c0;
        p=p0*c0;
        for(int j=W;j>=w;--j)f[j]=max(f[j],f[j-w]+p);
    }
    printf("%lld\n",f[W]);

}

2018/8/30

杜教筛

题意给定一个正整数$N(N\le2^{31}-1)$

$ans_1=\sum_{i=1}^n\varphi(i)$
$ans_2=\sum_{i=1}^n \mu(i)$

对数论函数$f(n)$,求
$S(n)=\sum_{i=1}^{n}f(i)$
对于任意数论函数$g(n)$,均满足

$\sum_{i=1}^{n}(f*g)(i)=\sum_{i=1}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor)$

故$g(1)S(n) = \sum_{i=1}^n (f*g)(i) – \sum_{i=2}^n g(i)S(\lfloor \frac{n}{i} \rfloor)$

$\mu * 1 = \epsilon $
$S(n) = 1 – \sum_{i=2}^n S(\lfloor \frac{n}{i} \rfloor)$

$\varphi * 1 = id$
$S(n) = \frac{n(n+1)}{2} – \sum_{i=2}^n S(\lfloor \frac{n}{i} \rfloor)$

$\sum_{i=1}^n\varphi(i)$用莫比乌斯反演求更快,之前一直TLE,反演就A了

显然要求即为
$\sum_{i=1}^{n} \sum_{j=1}^{n} [gcd(i,j)==1]$排除掉($i=j=1$的情况(减$1$)再除以$2$)
显然可以反演来做

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=5e6;

ll phi[N],mu[N];
int prime[N];
bool mark[N];
int cnt;

inline void init(){
    phi[1]=mu[1]=1;
    for(int i=2;i<N;i++){
        if(!mark[i])prime[++cnt]=i,phi[i]=i-1,mu[i]=-1;
        for(int j=1;j<=cnt;j++){
            ll tmp=i*prime[j];
            if(tmp>=N)break;
            mark[tmp]=1;
            if(i%prime[j]==0){phi[tmp]=phi[i]*prime[j],mu[tmp]=0;break;}
            else phi[tmp]=phi[i]*phi[prime[j]],mu[tmp]=-mu[i];
        }
    }
    for(int i=1;i<N;++i)phi[i]+=phi[i-1],mu[i]+=mu[i-1];
}

map<int,ll>s_mu;
ll sum_mu(int n){
    if(n<N)return mu[n];
    if(s_mu.count(n))return s_mu[n];
    ll ans=1;
    for(ll i=2,j;i<=n;i=j+1){
        j=n/(n/i);
        ans-=(j-i+1)*sum_mu(n/i);
    }
    return s_mu[n]=ans;
}

ll sum_phi(int n){
    if(n<N)return phi[n];
    ll ans=0;
    for(ll i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        ans+=(n/i)*(n/i)*(sum_mu(j)-sum_mu(i-1));
    }
    return ((ans-1)>>1)+1;
}

int main(){
    init();
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        printf("%lld %lld\n",sum_phi(n),sum_mu(n));
    }
}

TEST 56

T3

我推的两种式子和都题解不一样,但是都是对的,而且复杂度似乎也是一样的

按照题解改的

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int p=1e9+7;

inline ll qpow(ll a,int b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

ll C[10][10];
ll B[10];
ll inv[10];
inline void pre(){
    for(int i=0;i<=6;++i){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;++j){
            C[i][j]=C[i-1][j-1]+C[i-1][j];
        }
    }

    inv[1]=1;
    for(int i=2;i<=6;++i)inv[i]=(p-p/i)*inv[p%i]%p;

    B[0]=1;
    for(int i=1;i<=5;++i){
        for(int j=0;j<i;++j){
            B[i]=(B[i]+C[i+1][j]*B[j])%p;
        }
        B[i]=B[i]*(p-inv[i+1])%p;
    }
}

inline ll get(ll n,int k){
    ll ret=0,t=++n;++k;
    for(int i=1;i<=k;++i){
        ret=(ret+C[k][i]*B[k-i]%p*t%p)%p;
        t=t*n%p;
    }
    return ret*inv[k]%p;
}

const int N=5e6;

ll phi[N];
int prime[N];
bool mark[N];
int cnt;

inline void init(){
    phi[1]=1;
    for(int i=2;i<N;i++){
        if(!mark[i])prime[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt;j++){
            ll tmp=i*prime[j];
            if(tmp>=N)break;
            mark[tmp]=1;
            if(i%prime[j]==0){phi[tmp]=phi[i]*prime[j]%p;break;}
            else phi[tmp]=phi[i]*phi[prime[j]];
        }
    }
    for(int i=1;i<N;++i)(phi[i]+=phi[i-1])%=p;
}

map<int,int>s_phi;
ll sum_phi(ll n){
    if(n<N)return phi[n];
    if(s_phi.count(n))return s_phi[n];
    ll ans=((ll)n*(n+1)>>1)%p;
    for(ll i=2,j;i<=n;i=j+1){
        j=n/(n/i);
        ans=(ans-(j-i+1)*sum_phi(n/i)%p+p)%p;
    }
    return s_phi[n]=ans;
}


int main(){
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    pre();
    init();
    ll n,ans=0;
    int k;
    scanf("%lld%d",&n,&k);
    for(ll i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        ans=(ans+(get(j,k)-get(i-1,k))*sum_phi(n/i)%p+p)%p;
    }
    printf("%lld\n",(ans*2-get(n,k)+p)%p);
}

我自己推的第一个式子
$\sum_{i=1}^{n} \sum _ {j=1}^{n}{gcd(i,j)}^{k}$
$=\sum_{d=1}^{n} d^k \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor} [gcd(i,j)==1]$
$=\sum_{d=1}^{n} d^k \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor} \sum_{p|gcd(i,j)}{\mu(p)}$
$=\sum_{d=1}^{n} d^k \sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p) {\lfloor\frac{n}{dp}\rfloor}^2$
这个式子我一开始以为是$O(n)$的,结果学长告诉我这是$O(n^\frac{3}{4})$的,还可以杜教筛优化

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=5e6+7;
const int p=1e9+7;

ll C[10][10];
ll B[10];
ll inv[10];
inline void pre(){
    for(int i=0;i<=6;++i){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;++j){
            C[i][j]=C[i-1][j-1]+C[i-1][j];
        }
    }

    inv[1]=1;
    for(int i=2;i<=6;++i)inv[i]=(p-p/i)*inv[p%i]%p;

    B[0]=1;
    for(int i=1;i<=5;++i){
        for(int j=0;j<i;++j){
            B[i]=(B[i]+C[i+1][j]*B[j])%p;
        }
        B[i]=B[i]*(p-inv[i+1])%p;
    }
}

inline ll get(ll n,int k){
    ll ret=0,t=++n;++k;
    for(int i=1;i<=k;++i){
        ret=(ret+C[k][i]*B[k-i]%p*t%p)%p;
        t=t*n%p;
    }
    return ret*inv[k]%p;
}


bool not_p[N];
int pr[N],pcnt;
ll mu[N];

inline ll qpow(ll a,int b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

inline void init(int n){
    mu[1]=1;
    for(int i=2;i<=n;++i){
        if(!not_p[i])pr[++pcnt]=i,mu[i]=p-1;
        for(int j=1,tmp;j<=pcnt&&(tmp=pr[j]*i)<=n;++j){
            not_p[tmp]=1;
            if(i%pr[j]==0){mu[tmp]=0;break;}
            mu[tmp]=p-mu[i];
        }
    }
    for(int i=1;i<=n;++i)(mu[i]+=mu[i-1])%p;
}

map<int,ll>s_mu;
ll sum_mu(int n){
    if(n<N)return mu[n];
    if(s_mu.count(n))return s_mu[n];
    ll ans=1;
    for(ll i=2,j;i<=n;i=j+1){
        j=n/(n/i);
        ans-=(j-i+1)*sum_mu(n/i);
    }
    return s_mu[n]=ans;
}


inline ll calc(int n){
    ll ans=0;
    for(int i=1,j,nn;i<=n;i=j+1){
        j=n/(nn=(n/i));
        (ans+=(sum_mu(j)-sum_mu(i-1)+p)%p*nn%p*nn%p)%=p;
    }
    return ans;
}

ll s[N];

int main(){
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    ll n;
    int k;
    r(n);r(k);
    pre();
    init(5e6);
    ll ans=0;
    for(int i=1,j,nn;i<=n;i=j+1){
        j=n/(nn=(n/i));
        (ans+=(get(j,k)-get(i-1,k)+p)%p*calc(n/i)%p)%=p;
    }
    printf("%lld\n",ans);
}

第二个式子
$\sum_{i=1}^{n} \sum _ {j=1}^{n}{gcd(i,j)}^{k}$
$=\sum_{d=1}^{n} d^k \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor} [gcd(i,j)==1]$
$=\sum_{d=1}^{n}{d^k}(2\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\varphi(i)-1)$
理解这个式子就画一个矩阵$A$,$A_{i,j}=[gcd(i,j)==1]$
然后这个矩阵的主对角线上除了$A_{1,1}$全是$0$而它的一半正好是欧拉函数的前缀和
所以
$\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor} [gcd(i,j)==1]=2\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\varphi(i)-1$

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int p=1e9+7;

inline ll qpow(ll a,int b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

ll C[10][10];
ll B[10];
ll inv[10];
inline void pre(){
    for(int i=0;i<=6;++i){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;++j){
            C[i][j]=C[i-1][j-1]+C[i-1][j];
        }
    }

    inv[1]=1;
    for(int i=2;i<=6;++i)inv[i]=(p-p/i)*inv[p%i]%p;

    B[0]=1;
    for(int i=1;i<=5;++i){
        for(int j=0;j<i;++j){
            B[i]=(B[i]+C[i+1][j]*B[j])%p;
        }
        B[i]=B[i]*(p-inv[i+1])%p;
    }
}

inline ll get(ll n,int k){
    ll ret=0,t=++n;++k;
    for(int i=1;i<=k;++i){
        ret=(ret+C[k][i]*B[k-i]%p*t%p)%p;
        t=t*n%p;
    }
    return ret*inv[k]%p;
}

const int N=5e6;

ll phi[N];
int prime[N];
bool mark[N];
int cnt;

inline void init(){
    phi[1]=1;
    for(int i=2;i<N;i++){
        if(!mark[i])prime[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt;j++){
            ll tmp=i*prime[j];
            if(tmp>=N)break;
            mark[tmp]=1;
            if(i%prime[j]==0){phi[tmp]=phi[i]*prime[j]%p;break;}
            else phi[tmp]=phi[i]*phi[prime[j]];
        }
    }
    for(int i=1;i<N;++i)(phi[i]+=phi[i-1])%=p;
}

map<int,int>s_phi;
ll sum_phi(ll n){
    if(n<N)return phi[n];
    if(s_phi.count(n))return s_phi[n];
    ll ans=((ll)n*(n+1)>>1)%p;
    for(ll i=2,j;i<=n;i=j+1){
        j=n/(n/i);
        ans=(ans-(j-i+1)*sum_phi(n/i)%p+p)%p;
    }
    return s_phi[n]=ans;
}


int main(){
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    pre();
    init();
    ll n,ans=0;
    int k;
    scanf("%lld%d",&n,&k);
    for(ll i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        ans=(ans+(get(j,k)-get(i-1,k))*((2*sum_phi(n/i)-1)%p)%p+p)%p;
    }
    printf("%lld\n",ans);
}

然后还有一个重要的问题,
所有这些式子都需要求$n^k$的前缀和
因为$k$比较小,所以标程是用公式算的

long long gett(long long n,int k)
{
    n%=mod;
    if(k==1)
        return n*(n+1)/2%mod;
    if(k==2)
        return n*(n+1)%mod*(2*n+1)%mod*mod6%mod;
    if(k==3){
        long long t=n*(n+1)/2%mod;;
        return t*t%mod;
    }
    if(k==4){
        return n*(n+1)%mod*(2*n+1)%mod*((3*n*n%mod+3*n-1)%mod)%mod*mod30%mod;
    }
    if(k==5){
        long long t=n*(n+1)%mod;
        t=t*t%mod;
        t=t*((2*n*n%mod+2*n-1)%mod)%mod;
        t=t*mod12%mod;
        return t;
    }
}

其中mod##表示##的逆元
然而我只记得住前三个
一开始还试了试拉格朗日插值
结果插得头昏脑胀都没有求出来
这时就可以使用伯努利数求自然数幂和
也就是我代码里的get()函数
其实也可以把系数算出来然后直接写在程序里
但是我太懒了不想写
另外还可以用斯特林数求自然数幂和
但是我不会

2018/8/31

今天考了两套长沙一中的noip模拟题
ljh连续两次rank1,巨强无比

Test57

Test58

简单的数学题

确实蛮简单的,但是我第一次交只有80分,我居然取了模还炸了long long
$\sum_{i=1}^{n} \sum_{j=1}^{n}{ijgcd(i,j)}$
$=\sum_{i=1}^{n} \sum_{j=1}^{n}{ij\sum_{d|gcd(i,j)}{\varphi(d)}}$
$=\sum_{d=1}^{n}{\varphi(d)d^2\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}{ij}}$
$=\sum_{d=1}^{n}{\varphi(d)d^2 (\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}{i})^2 }$
$=\sum_{d=1}^{n}{\varphi(d)d^2 \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}{i^3} }$
然后整除分块+杜教筛就可以了

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=5e6;

ll n,p,inv6;
ll phi[N];
int prime[N];
bool mark[N];
int cnt;

inline ll qpow(ll a,int b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

inline void init(){
    inv6=qpow(6,p-2);
    phi[1]=1;
    for(int i=2;i<N;i++){
        if(!mark[i])prime[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt;j++){
            ll tmp=i*prime[j];
            if(tmp>=N)break;
            mark[tmp]=1;
            if(i%prime[j]==0){phi[tmp]=phi[i]*prime[j]%p;break;}
            else phi[tmp]=phi[i]*phi[prime[j]]%p;
        }
    }
    for(int i=1;i<N;++i)(phi[i]=phi[i-1]+phi[i]*i%p*i%p)%=p;
}

inline ll sqr(ll x){
    x%=p;
    return x*x%p;
}

inline ll s1(ll x){
    x%=p;
    return (x*(x+1)>>1)%p;
}

inline ll s2(ll x){
    x%=p;
    return x*(x+1)%p*(2*x+1)%p*inv6%p;
}

inline ll s3(ll x){
    return sqr(s1(x));
}

map<ll,ll>s;
ll calc(ll n){
    if(n<N)return phi[n];
    if(s.count(n))return s[n];
    ll ans=s3(n);
    for(ll i=2,j;i<=n;i=j+1){
        j=n/(n/i);
        (ans+=p-(s2(j)-s2(i-1)+p)%p*calc(n/i)%p)%=p;
    }
    return s[n]=ans;
}

int main(){
    r(p);r(n);
    init();
    ll ans=0;
    for(ll i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        (ans+=(calc(j)-calc(i-1)+p)%p*s3(n/i)%p)%=p;
    }
    printf("%lld\n",ans);
}

2018/9/1

TEST 59

T1

快速沃尔什变换,然而我炸又long long
取个模就好了,因为方案数比较小

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1<<20|7;
const int p=998244353;
const ll inv2=499122177;

inline int add(int a,int b){
    a+=b;
    if(a>=p)a-=p;
    return a;
}

inline int sub(int a,int b){
    a-=b;
    if(a<0)a+=p;
    return a;
}

inline void FWT_or(int *A,int len,bool opt=1){
    for(int i=1;i<len;i<<=1){
        for(int j=0;j<len;j+=i<<1){
            for(int k=0;k<i;++k){
                A[j+k+i]=opt?add(A[j+k],A[j+k+i]):sub(A[j+k+i],A[j+k]);
            }
        }
    }
}

inline void FWT_and(int *A,int len,bool opt=1){
    for(int i=1;i<len;i<<=1){
        for(int j=0;j<len;j+=i<<1){
            for(int k=0;k<i;++k){
                A[j+k]=opt?add(A[j+k],A[j+k+i]):sub(A[j+k],A[j+k+i]);
            }
        }
    }
}

inline void FWT_xor(int *A,int len,bool opt=1){
    for(int i=1;i<len;i<<=1){
        for(int j=0;j<len;j+=i<<1){
            for(int k=0;k<i;++k){
                int u=A[j+k],v=A[j+k+i];
                A[j+k]=add(u,v);
                A[j+k+i]=sub(u,v);
                if(!opt){
                    A[j+k]=A[j+k]*inv2%p;
                    A[j+k+i]=A[j+k+i]*inv2%p;
                }
            }
        }
    }
}

int a[N],b[N],t[N];
int len;

inline int OR(){
    memcpy(t,a,len<<2);
    FWT_or(t,len);
    for(int i=0;i<len;++i)b[i]=(ll)t[i]*t[i]%p;
    FWT_or(b,len,0);
    for(int i=len;i;--i){
        if(a[i]==1)--b[i];
        if(b[i]>0)return i;
    }
    return 0;
}

inline int AND(){
    memcpy(t,a,len<<2);
    FWT_and(t,len);
    for(int i=0;i<len;++i)b[i]=(ll)t[i]*t[i]%p;
    FWT_and(b,len,0);
    for(int i=len;i;--i){
        if(a[i]==1)--b[i];
        if(b[i]>0)return i;
    }
    return 0;
}

inline int XOR(){
    memcpy(t,a,len<<2);
    FWT_xor(t,len);
    for(int i=0;i<len;++i)b[i]=(ll)t[i]*t[i]%p;
    FWT_xor(b,len,0);
    for(int i=len;i;--i){
        if(b[i])return i;
    }
    return 0;
}

int main(){
    freopen("maximum.in","r",stdin);
    freopen("maximum.out","w",stdout);
    int T;r(T);
    while(T--){
        int n,c,mx=0;
        r(n);r(c);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=0,x;i<n;++i)r(x),a[x]++,mx=max(mx,x);
        for(len=1;len<mx;len<<=1);
        switch(c){
            case 1:{printf("%d\n",AND());break;}
            case 2:{printf("%d\n",XOR());break;}
            case 3:{printf("%d\n",OR());break;}
        }
    }
}

T2

做过的题

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=2e5+5;
const ll INF=1e10;

vector<int>lp,rp,pos;

inline bool cmp(int a,int b){
    return pos[a]<pos[b];
}

inline int query(int tim,ll dis){
    return upper_bound(lp.begin(),lp.end(),dis+tim)-lp.begin()+upper_bound(rp.begin(),rp.end(),dis-tim)-rp.begin();
}

inline ll calc(int tim,int k){
    ll l=-INF,r=INF,ret,mid;
    while(l<=r){
        mid=(l+r)>>1;
        query(tim,mid)>k?ret=mid,r=mid-1:l=mid+1;
    }
    return ret;
}

int rank[N],order[N];

int main(){
    freopen("bridge.in","r",stdin);
    freopen("bridge.out","w",stdout);
    int n,q;
    r(n);
    for(int i=0,v;i<n;++i){
        r(v);
        pos.push_back(v);
        order[i]=i;
    }
    for(int i=0,d;i<n;++i){
        r(d);
        d?rp.push_back(pos[i]):lp.push_back(pos[i]);
    }
    sort(lp.begin(),lp.end());
    sort(rp.begin(),rp.end());
    sort(order,order+n,cmp);
    for(int i=0;i<n;++i)rank[order[i]]=i;
    for(r(q);q;--q){
        int t,x;
        r(x),r(t);
        printf("%lld\n",calc(t,rank[x]));
    }
}

TEST60

题目偏水,就不写了

2018/9/2

TEST61

太水了不写了

TEST62

T1

裸的卡特兰数,结果居然有好几个人写dp$O(n^2)$过了,你们是不是对数学有什么偏见??$O(n)$不好吗

#include<bits/stdc++.h>

using namespace std;

const int p=1e9+7;

typedef long long ll;

inline ll qpow(ll a,int b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

inline ll inv(ll a){
    return qpow(a,p-2);
}

int main(){
    freopen("school.in","r",stdin);
    freopen("school.out","w",stdout);
    int n;
    scanf("%d",&n);
    --n;
    ll t1=1;
    for(int i=1;i<=n;++i)t1=t1*i%p;
    ll t2=t1;
    for(int i=n+1;i<=(n<<1);++i)t2=t2*i%p;
    printf("%lld\n",t2*inv(t1*t1%p)%p*inv(n+1)%p);
}

T2

dp+换根
首先考虑不换根
对抗搜索即可
既然要换根,我们可以记录信息然后考虑如何转移
我们记录每个节点向下走的最大答案$mx[x]$和最小答案$mi[x]$
$mx[x]=max{(mi[y]+cost(x,y))}$
$mi[x]=min{(mx[y]+cost(x,y))}$
其中$y$是$x$的儿子
现在我们要换根,就是节点的父子关系改变
之前比如之前$x$的答案可以由$y$转移过来
现在$y$的答案可以由$x$转移过来
如果以前$x$的答案不来自$y$那么不需要对$x$的答案作任何修改
否则$x$的答案将变为次优解
然后还要用$x$的答案更新$y$的答案
上述过程可以用两次dfs实现
第一次得到初始解
之后依次换根,得到每个点的答案

话说我差点又炸long long

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=300005;
const ll INF=1e18;

int ecnt;
ll mx[N],mi[N];
ll mx2[N],mi2[N];
int fir[N],to[N<<1],nex[N<<1],w[N<<1];

inline void addedge(int u,int v,int c){
    nex[++ecnt]=fir[u];fir[u]=ecnt;to[ecnt]=v;w[ecnt]=c;
    nex[++ecnt]=fir[v];fir[v]=ecnt;to[ecnt]=u;w[ecnt]=c;
}

void dfs1(int x,int f=0){
    bool flag=0;
    for(int i=fir[x],v;i;i=nex[i]){
        if((v=to[i])==f)continue;
        flag=1;
        dfs1(v,x);
    }
    mx[x]=-INF*flag;
    mi[x]=INF*flag;//when x is a leaf ,both mx[x] and mi[x] should be zero
    for(int i=fir[x],v;i;i=nex[i]){
        if((v=to[i])==f)continue;
        ll t;
        if(mx[x]<=(t=mi[v]+w[i]))mx2[x]=mx[x],mx[x]=t;
        else if(mx2[x]<=t)mx2[x]=t;
        if(mi[x]>=(t=mx[v]+w[i]))mi2[x]=mi[x],mi[x]=t;
        else if(mi2[x]>=t)mi2[x]=t;
    }
}

ll mxans[N],mians[N];

void dfs2(int x,int f=0){
    mxans[x]=mx[x];
    mians[x]=mi[x];
    ll mxx=mx[x],mix=mi[x];
    for(int i=fir[x],v;i;i=nex[i]){//v change to father of x
        if((v=to[i])==f)continue;
        ll t;
        if(mx[x]==mi[v]+w[i]){//mx[x] can not come from mi[v]+w[i]
            if(mx2[x]!=-INF)mx[x]=mx2[x];
            else mx[x]=0;
        }
        if(mi[x]==mx[v]+w[i]){//mi[x] can not come from mx[v]+w[i]
            if(mi2[x]!=INF)mi[x]=mi2[x];
            else mi[x]=0;
        }
        ll mxv=mx[v],miv=mi[v],mx2v=mx2[v],mi2v=mi2[v];
        if(mx[v]<=(t=mi[x]+w[i])||!mx[v])mx2[v]=mx[v],mx[v]=t;//mx[v] can come from mi[x]+w[i]
        else if(mx2[v]<=t)mx2[v]=t;//mx2[v] can come from mi[x]+w[i]
        if(mi[v]>=(t=mx[x]+w[i])||!mi[v])mi2[v]=mi[v],mi[v]=t;//mi[v] can come from mx[x]+w[i]
        else if(mi2[v]>=t)mi2[v]=t;//mi2[v] can come from mx[x]+w[i]
        dfs2(v,x);
        mx[x]=mxx;mi[x]=mix;
        mx[v]=mxv;mi[v]=miv;
        mx2[v]=mx2v;mi2[v]=mi2v;
    }
}


int main(){
    freopen("travel.in","r",stdin);
    freopen("travel.out","w",stdout);
    int n;
    r(n);
    for(int i=1,u,v,c;i<n;++i){
        r(u),r(v),r(c);
        addedge(u,v,c);
    }
    dfs1(1);
    dfs2(1);
    for(int i=1;i<=n;++i)printf("%lld\n",mxans[i]);
}

T3

显然我们先将边反向
这是一个基环外向森林
对于一颗基环外向树
对于树上的点,设答案为$f$
显然有$f[x]=cost[x]+\frac{\sum{f[y]} } {cnt[x]+1}$
其中$y$是$x$的儿子,$cnt$是边数
对于环上的点
将其作为树根
设答案为$g$
显然有$g[x]=\frac{cost[x]+g[next[x]]+(f[x]-cost[x])*cnt[x]}{cnt[x]+1}$
注意这里$cnt$是括环上的边(只有一条)
然后就可以递推出答案了

2018/9/4

拉格朗日插值

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

typedef long long ll;

const int p=998244353;

inline ll qpow(ll a,int b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

inline ll sub(ll a,ll b){
    a-=b;
    if(a<0)a+=p;
    return a;
}

const int N=2005;

ll x[N],y[N];

int main(){
    int n,k;
    r(n);r(k);
    for(int i=1;i<=n;++i)r(x[i]),r(y[i]);
    ll ans=0;
    for(int i=1;i<=n;++i){
        ll ret=1;
        for(int j=1;j<=n;++j)if(i!=j)ret=ret*sub(x[i],x[j])%p;
        ret=qpow(ret,p-2);
        for(int j=1;j<=n;++j)if(i!=j)ret=ret*sub(k,x[j])%p;
        ans=(ans+ret*y[i])%p;
    }
    printf("%lld\n",ans);
}

上帝与集合的正确用法

扩展欧拉定理
$a^b\equiv{b\%\varphi(p)}$ $gcd(a,p)=1$ $\mod p$
$a^b\equiv{a^b}$ $gcd(a,p)\neq1,b<\varphi(p)$ $\mod p$
$a^b\equiv{a^{b\%\varphi(p)+\varphi(p)}}$ $gcd(a,p)\neq1,b\geq\varphi(p)$ $\mod p$

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

inline int qpow(long long a,int b,int p){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}

const int N=1e7+5;

int phi[N],pri[N];
int tot;
inline void init(){
    phi[1]=1;
    for(int i=2;i<N;++i){
        if(!phi[i])pri[++tot]=i,phi[i]=i-1;
        for(int j=1,tmp;j<=tot&&(tmp=i*pri[j])<N;++j){
            if(i%pri[j]==0){
                phi[tmp]=phi[i]*pri[j];
                break;
            }
            phi[tmp]=phi[i]*phi[pri[j]];
        }
    }
}

inline int solve(int n){
    if(phi[n]==1)return 0;
    return qpow(2,solve(phi[n])+phi[n],n);
}

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int T;
    init();
    for(r(T);T;--T){
        int n;
        r(n);
        printf("%d\n",solve(n));
    }
}

数字表格

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int p=1e9+7;
const int N=1e6+5;

inline ll qpow(ll a,int b){
    ll ans=1;
    while(b){
        if(b&1)(ans*=a)%=p;
        (a*=a)%=p;
        b>>=1;
    }
    return ans;
}

inline ll Inv(ll a){
    return qpow(a,p-2);
}

inline ll add(ll a,const ll &b){
    a+=b;
    if(a>=p)a-=p;
    return a;
}

int tot;
int mu[N];
int pri[N];
bool mark[N];

ll fib[N];
ll inv[N];

ll f[N];
ll g[N];

inline void init(){
    mu[1]=1;
    for(int i=2;i<N;++i){
        if(!mark[i])pri[++tot]=i,mu[i]=-1;
        for(int j=1,tmp;j<=tot&&(tmp=i*pri[j])<N;++j){
            mark[tmp]=1;
            if(i%pri[j]==0){mu[tmp]=0;break;}
            mu[tmp]=-mu[i];
        }
    }

    fib[1]=1;
    for(int i=2;i<N;++i)inv[i]=Inv(fib[i]=add(fib[i-1],fib[i-2]));

    for(int i=0;i<N;++i)f[i]=g[i]=1;

    for(int i=3;i<N;++i){
        for(int j=i,k=1;j<N;j+=i,++k){
            if(mu[k]==1){
                (f[j]*=fib[i])%=p;
                (g[j]*=inv[i])%=p;
            }
            else if(mu[k]==-1){
                (f[j]*=inv[i])%=p;
                (g[j]*=fib[i])%=p;
            }
        }
    }

    for(int i=2;i<N;++i){
        (f[i]*=f[i-1])%=p;
        (g[i]*=g[i-1])%=p;
    }
}

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ll T,n,m;
    init();
    for(r(T);T;--T){
        r(n);r(m);
        if(n>m)swap(n,m);
        ll ans=1;
        for(ll i=1,j,nn,mm;i<=n;i=j+1){
            j=min(n/(nn=n/i),m/(mm=(m/i)));
            (ans*=qpow(f[j]*g[i-1]%p,nn*mm%(p-1)))%=p;
        }
        printf("%lld\n",ans);
    }

}

2018/9/6

Test67

T1

包裹快递
注意开long double

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define db long double

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=200005;
const db eps=1e-6;

int x[N],y[N],s[N],i,n;

inline bool check(db v){
    db t=0;
    v=1/v;
    for(int i=1;i<=n;++i){
        if(t+s[i]*v>y[i])return 0;
        if(t+s[i]*v<x[i])t=x[i];
        else t+=s[i]*v; 
    }                
    return 1;
}

int main(){
    r(n);
    for(i=1;i<=n;++i)r(x[i]),r(y[i]),r(s[i]);
    db l=0,r=1e9,mid;
    while(r-l>eps)check(mid=(r+l)/2.0)?r=mid:l=mid;
    printf("%.2lf\n",double(l));
}

T2

迎接仪式

#include<bits/stdc++.h>

using namespace std;

char s[505];
int f[505][105][105];

int main(){
    int n,k,ans=0;
    scanf("%d%d%s",&n,&k,s+1);
    memset(f,-0x3f,sizeof(f));
    f[0][0][0]=0;
    f[1][0][0]=0;
    if(s[1]=='z')f[1][0][1]=0;
    else f[1][1][0]=0;
    for(int i=2;i<=n;++i){
        for(int j=0;j<=k;++j){
            for(int l=0;l<=k;++l){
                f[i][j][l]=f[i-1][j][l];
                if(s[i]=='z'&&s[i-1]=='j')f[i][j][l]=max(f[i][j][l],f[i-2][j][l]+1);
                if(s[i]=='z'&&s[i-1]=='z'&&l)f[i][j][l]=max(f[i][j][l],f[i-2][j][l-1]+1);
                if(s[i]=='j'&&s[i-1]=='j'&&j)f[i][j][l]=max(f[i][j][l],f[i-2][j-1][l]+1);
                if(s[i]=='j'&&s[i-1]=='z'&&j&&l)f[i][j][l]=max(f[i][j][l],f[i-2][j-1][l-1]+1);
                if(j==l)ans=max(ans,f[i][j][l]);
            }
        }
    }
    printf("%d\n",ans);
}

2018/9/7

Test 68

T1

一个普通的完全背包

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=4005;

ll w[N],t[N],f[5005];

int main(){
    freopen("restaurant.in","r",stdin);
    freopen("restaurant.out","w",stdout);
    int T,n,m,Tmax;
    for(r(T);T;--T){
        r(n),r(m),r(Tmax);
        for(int i=1;i<=n+m;++i)r(t[i]),r(w[i]);
        for(int i=1;i<=m;++i){
            for(int j=1,x;j<=n;++j){
                r(x);
                t[i+n]+=t[j]*x;
            }
        }
        for(int i=0;i<=Tmax;++i){
            f[i]=0;
            for(int j=1;j<=n+m;++j){
                if(i>=t[j])f[i]=max(f[i],f[i-t[j]]+w[j]);
            }
        }
        ll ans=0;
        for(int i=0;i<=Tmax;++i)ans=max(ans,f[i]);
        printf("%lld\n",ans);
    }
}

T2

树形dp

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e5+7;

vector<int> to[N];

int f1[N],f2[N];
int fa[N],ed[N];
int g[N];

void dfs1(int x){
    for(int i=0;i<to[x].size();++i){
        int v=to[x][i];
        dfs1(v);
        if(f1[v]+1>=f1[x]){
            f2[x]=f1[x];
            f1[x]=f1[v]+1;
        }
        else if(f1[v]+1>=f2[x]){
            f2[x]=f1[v]+1;
        }
    }
}

void dfs2(int x){
    for(int i=0;i<to[x].size();++i){
        int v=to[x][i];
        if(f1[v]+1==f1[x]){
            g[v]=max(g[x],f2[x])+1;
        }
        else {
            g[v]=max(g[x],f1[x])+1;
        }
        dfs2(v);
    }
}

int main(){
    freopen("olefin.in","r",stdin);
    freopen("olefin.out","w",stdout);
    int id;
    r(id);
    int T;
    for(r(T);T;--T){
        int n,m;
        r(n);r(m);
        for(int i=1;i<=n;++i)to[i].clear();
        memset(f1+1,0,n<<2);
        memset(f2+1,0,n<<2);
        memset(g+1,0,n<<2);
        for(int i=2;i<=n;++i)r(fa[i]),to[fa[i]].push_back(i);
        for(int i=1;i<=m;++i)r(ed[i]);
        dfs1(1);
        dfs2(1);
        for(int i=1;i<=m;++i){
            int ans,v=ed[i],x=fa[v];
            ans=max(f1[v]+1==f1[x]?f2[x]:f1[x],g[x])+f1[v]+1;
            printf("%d",ans);
            if(i<m)putchar(' ');
        }
        puts("");//数据有问题,std中只有m!=0才提行,然而这里明显应该这样写
    }
}

T3

先打表找规律
猜测有递推式
可以用BM/高斯消元/for循环测验
然后用矩阵快速幂求解
然而n太大,不方便转二进制
所以要用十进制快速幂
如果不是我不会十进制快速幂
我就AK了……

#include <bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long 

const int N=10;
const int p=998244353;

struct matrix{
    ll a[N][N];
    matrix(){
        memset(a,0,sizeof(a));
    }
    ll*operator[](const int x){return a[x];}

    inline void set(){
        for(int i=0;i<7;++i)a[i][i]=1;
    }

    matrix operator*(const matrix& x){
        matrix ret;
        for(int i=0;i<7;++i)
            for(int j=0;j<7;++j)
                for(int k=0;k<7;++k)
                    (ret.a[i][j]+=a[i][k]*x.a[k][j])%=p;
        return ret; 
    }
}a,ans,tmp,Pow[10];

ll s[]={6,1,3,10,23,62,170};
ll f[]={6,1,2,6,1,0,998244352};

char x[40005];

int main(){
    freopen("tromino.in","r",stdin);
    freopen("tromino.out","w",stdout);
    scanf("%s",x);
    int l=strlen(x);
    reverse(x,x+l);

    if(l==1&&x[0]<='6'){
        printf("%d\n",s[x[0]-'0']);
        return 0;
    }
    for(int i=1;i<=6;++i)a[1][i]=f[i];
    for(int i=2;i<=6;++i)a[i][i-1]=1;

    x[0]-=6;
    for(int i=0;x[i]<'0';++i){
        x[i]+=10;
        x[i+1]-=1;
    }

    while(x[l-1]=='0')--l;
    reverse(x,x+l);

    Pow[0].set();
    for(int i=1;i<10;++i)Pow[i]=Pow[i-1]*a;

    ans.set();

    for(int i=0;i<l;++i){
        ans=ans*ans;
        tmp=ans;
        ans=ans*ans;
        ans=ans*ans*tmp*Pow[x[i]-'0'];
    }

    ll Ans=0;
    for(int i=1;i<=6;++i)(Ans+=ans[1][i]*s[7-i])%=p;

    printf("%lld\n",Ans);
    return 0;
}

2018/9/8

Test 69

T1

设等级$x$的代价是$f_x$

$y=max(x-1,0)$
$k_x=\frac{min(c_x,b_y)}{c_x}$
显然有
$k_x – 1 * f_x+(1 – k_x – 1) * f_y=f_x + f_y$
然后就可以做了

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=10000007;
const int p=998244353;

int f[3];
int inv[N];

int main(){
    freopen("forging.in","r",stdin);
    freopen("forging.out","w",stdout);
    int n,a,bx,by,cx,cy,p0,b,c,k;
    r(n);r(a);r(bx);r(by);r(cx);r(cy);r(p0);

    inv[1]=1;
    for(int i=2;i<=p0;++i)inv[i]=(ll)(p-p/i)*inv[p%i]%p;

    b=by+1;c=cy+1;
    k=(ll)c*inv[min(c,b)]%p;
    f[0]=a;
    f[1]=(ll)f[0]*(k+1)%p;
    for(int i=1;i<n;i++,f[i%3]=((ll)f[(i-1)%3]*k+f[(i-2)%3])%p){
        c=((ll)c*cx+cy)%p0+1;
        k=(ll)c*inv[min(c,b)]%p;
        b=((ll)b*bx+by)%p0+1;
    }

    printf("%d\n",f[n%3]);
}

T2

$n|x^m-x$
$x^m \equiv x \mod n$

由中国剩余定理
我们只需在模$p_1,p_2…p_c$意义下分别求解
然后把每个解集的大小相乘就是答案

至于求解,标程用的是枚举$[1,p]$的每个数并判断
因为$x^m$可以线性筛
复杂度为$O(T*\sum_{i=1}^{c}{p_i})$
需要卡常数

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e4+5;
const int p=998244353;

inline ll qpow(ll a,int b,int mo=p){
    ll ans=1;
    for(;b;(a*=a)%=mo,b>>=1)if(b&1)(ans*=a)%=mo;
    return ans;
}

bool mark[N];
int f[N],pri[N];
inline int solve(int a,int m){
    memset(mark+1,0,a);
    int tot=0;
    f[1]=1;
    for(int i=2;i<a;++i){
        if(!mark[i]){
            pri[++tot]=i;
            f[i]=qpow(i,m,a);
        }
        for(int j=1,tmp;j<=tot&&(tmp=i*pri[j])<a;++j){
            mark[tmp]=1;
            f[tmp]=(ll)f[i]*f[pri[j]]%a;
            if(i%pri[j]==0)break;
        }
    }
    int sum=1;
    for(int i=1;i<a;++i)sum+=(f[i]==i);
    return sum;
}

int main(){
    freopen("division.in","r",stdin);
    freopen("division.out","w",stdout);
    int id,T,c,m;
    for(r(id),r(T);T;--T){
        r(c);r(m);
        ll ans=1;
        for(int i=0,a;i<c;++i)r(a),(ans*=solve(a,m))%=p;
        printf("%lld\n",ans);
    }
}

另外llj学长提供了更优秀的做法

考虑算出方程$x^{m-1}\equiv 1 \mod p$解的个数

首先我们会想到费马小定理
如果变量是$m$,是否一定有$m=k * (p-1)$呢?
显然不是
比如$x=1$是$m$可以去任意数
因为$x$的某些次幂在模$p$意义下是相同的
但是如果$x$是$p$的原根就没有这种可能了

设$p$有原根$g$
只要$g^a\equiv 1 \mod p$
一定有$a = k * (p-1)$

令$x=g^a$
则$g^{a(m-1)}\equiv 1 \mod p$
$a(m-1)=k(p-1)$

设$d=gcd(m-1,p-1)$
$\frac{a(m-1)}{d}=\frac{k(p-1)}{d}$
因为$\frac{m-1}{d}$与$\frac{p-1}{d}$互质
所以$a$是$\frac{p-1}{d}$的倍数
因为$a$的范围是$1$~$p-1$
所以$a$的个数是$\frac{p-1}{(\frac{p-1}{d})}=d$
然后加上$x=p$的一个解

答案就是$\prod_{i=1}^{c}{(gcd(p_i-1,m-1)+1)}$
复杂度$O(T* \sum_{i=1}^{c} \log \min( p_i,m ) )$

然后就可以$0msAC$了

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e4+5;
const int p=998244353;

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

inline int solve(int a,int m){
    return gcd(a-1,m-1)+1;
}

int main(){
    freopen("division.in","r",stdin);
    freopen("division.out","w",stdout);
    int id,T,c,m;
    for(r(id),r(T);T;--T){
        r(c);r(m);
        ll ans=1;
        for(int i=0,a;i<c;++i)r(a),(ans*=solve(a,m))%=p;
        printf("%lld\n",ans);
    }
}

2018/9/15

TEST70

T1

第一眼线段树
第二眼数学题
随便推一推式子就可以了,水题

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

inline char GetChar(){
    char gc;
    while(c!='R'&&c!='S')gc;
    return c;
}

const int N=1000005;
const int p=1e9+7;

int A[N],B[N];

int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    int n,m,k;
    r(n);r(m);r(k);
    for(int i=1;i<=n;++i)A[i]=1;
    for(int i=1;i<=m;++i)B[i]=1;
    while(k--){
        char c=GetChar();
        int x,y;r(x);r(y);
        if(c=='R')A[x]=1ll*A[x]*y%p;
        else B[x]=1ll*B[x]*y%p;
    }
    long long sum1=0,sum2=0;
    for(int i=1;i<=m;++i){
        (sum1+=B[i])%=p;
        (sum2+=1ll*B[i]*i)%=p;
    }
    long long ans=0;
    for(int i=1;i<=n;++i){
        (ans+=(sum1*(i-1)%p*m%p+sum2)%p*A[i]%p)%=p;
    }
    printf("%lld\n",ans);
    return 0;
}

2018/9/16

TEST71

T2

一开始写dfs
写完发现是个最短路
于是dijkstra就可以了
至于建边
首先向四周建长度为$1$的边
考虑传送门
向上下左右第一面墙连边
边权是该位置到最近的墙的距离
可以bfs
然而经过讨论和对拍
我们认为可以直接连到上下左右第一面墙的距离的最小值
不用bfs
考场$AC$代码

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=505;
const int INF=1e9;

int n,m,tot;

char G[N][N];

int U[N][N],D[N][N],L[N][N],R[N][N];

int sx,sy,ex,ey;

int id[N][N];

int ecnt;
int dis[N*N],fir[N*N],nex[N*N<<3],to[N*N<<3],w[N*N<<3];

inline void addedge(int u,int v,int c=1){
    if(!v||u==v)return;
    nex[++ecnt]=fir[u];fir[u]=ecnt;to[ecnt]=v;w[ecnt]=c;
}

struct data{
    int a,b;
    bool operator < (const data& x)const{
        return a>x.a;
    }
};

priority_queue<data>Q;
inline void dijkstra(int s,int t){
    for(int i=1;i<=tot;++i)dis[i]=INF;
    dis[s]=0;
    Q.push(data{0,s});
    while(!Q.empty()){
        int x=Q.top().b;
        int d=Q.top().a;
        Q.pop();
        if(d!=dis[x])continue;
        for(int i=fir[x],v,tmp;i;i=nex[i]){
            if((tmp=d+w[i])<dis[v=to[i]]&&tmp<dis[t]){
                dis[v]=tmp;
                Q.push(data{tmp,v});
            }
        }
    }
}

inline void init(){
    r(n);r(m);
    for(int i=0;i<n;++i)scanf("%s",G[i]);
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(G[i][j]!='#'){
                id[i][j]=++tot;
                U[i][j]=U[i-1][j];
                L[i][j]=L[i][j-1];
                if(G[i][j]=='C')sx=i,sy=j;
                else if(G[i][j]=='F')ex=i,ey=j;
            }
            else {
                U[i][j]=i;
                L[i][j]=j;
            }
        }
    }
    for(int i=n-1;i>=0;--i){
        for(int j=m-1;j>=0;--j){
            if(G[i][j]!='#'){
                D[i][j]=D[i+1][j];
                R[i][j]=R[i][j+1];
            }
            else {
                D[i][j]=i;
                R[i][j]=j;
            }
        }
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(G[i][j]!='#'){
                addedge(id[i][j],id[i+1][j]);
                addedge(id[i][j],id[i-1][j]);
                addedge(id[i][j],id[i][j+1]);
                addedge(id[i][j],id[i][j-1]);
                int dis=min(min(i-U[i][j],D[i][j]-i),min(j-L[i][j],R[i][j]-j));
                if(j-L[i][j]>2&&dis!=j-L[i][j])addedge(id[i][j],id[i][L[i][j]+1],dis);
                if(R[i][j]-j>2&&dis!=R[i][j]-j)addedge(id[i][j],id[i][R[i][j]-1],dis);
                if(i-U[i][j]>2&&dis!=i-U[i][j])addedge(id[i][j],id[U[i][j]+1][j],dis);
                if(D[i][j]-i>2&&dis!=D[i][j]-i)addedge(id[i][j],id[D[i][j]-1][j],dis);
            }
        }
    }
}

int main(){
    freopen("cell.in","r",stdin);
    freopen("cell.out","w",stdout);
    init();
    dijkstra(id[sx][sy],id[ex][ey]);
    if(dis[id[ex][ey]]<INF)printf("%d\n",dis[id[ex][ey]]);
    else puts("no");
}
/*
8 5
#####
#...#
#...#
#.C.#
#...#
#...#
#.F.#
#####
*/

2018/9/17

TEST 72

T1

套个二分就变成奶酪
似乎我这种做法会被卡常
然而我卡过去了
似乎正解是prim求最小生成树
张老师没有发题解没法改(其实只是我太懒了)

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long
#define db double

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

int n,m,k;

const int N=6005;
const db eps=5e-7;

ll X[N],Y[N];
int fa[N];

inline ll sqr(ll a){
    return a*a;
}

inline ll dist(int a,int b){
    return sqr(X[a]-X[b])+sqr(Y[a]-Y[b]);
}

int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

inline void uni(int a,int b){
    int f1=find(a),f2=find(b);
    if(f1!=f2)fa[f1]=f2;
}

inline bool solve(db x){
    x*=2.0;
    for(int i=0;i<=k+1;++i)fa[i]=i;
    for(int i=1;i<=k;++i){
        if(Y[i]<x)uni(i,k+1);
        if(m-Y[i]<x)uni(i,0);
    }
    x*=x;
    for(int i=1;i<=k;++i){
        for(int j=i+1;j<=k;++j){
            if(dist(i,j)<x){
                uni(i,j);
                if(find(0)==find(k+1))return 0;
            }
        }
    }
    return 1;
}

int main(){
    freopen("starway.in","r",stdin);
    freopen("starway.out","w",stdout);
    r(n);r(m);r(k);
    for(int i=1;i<=k;++i)r(X[i]),r(Y[i]);
    db l=0,r=m/2.0,mid;
    while(l+eps<=r)solve(mid=(l+r)/2.0)?l=mid:r=mid;
    printf("%.8lf",l);
}

TEST 73

T1

状压dp
考虑一种暴力的$dp$,设$dp[i][s]$表示询问的串为$i$,已经问过的状态为$s$,暴力转移,复杂度是$O(n^2 * 2^l)$
然后发现对于已经问过的状态,询问哪一个串并没有本质区别
因此预处理出$f[s]$表示问过的状态为$s$的情况下有多少个询问串能唯一确定,再$dp$就行了,复杂度$O(n * 2^l)$

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long
#define db double

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=50;
const int L=20;

char ch[N+5][L+5];

db f[1<<L];
int g[1<<L];
ll same[1<<L];

int main(){
    freopen("memory.in","r",stdin);
    freopen("memory.out","w",stdout);
    int n;r(n);
    for(int i=0;i<n;++i)scanf("%s",ch[i]);
    int m=strlen(ch[0]);
    for(int i=0;i<n;++i){
        for(int j=i+1;j<n;++j){
            int s=0;
            for(int k=0;k<m;++k)if(ch[i][k]==ch[j][k])s|=(1<<k);
            same[s]|=(1ll<<i);
            same[s]|=(1ll<<j);
        }
    }
    int S=(1<<m)-1;
    for(int i=S;i>=0;--i){
        for(int j=0;j<m;++j){
            if(i&(1<<j))same[i^(1<<j)]|=same[i];
        }
    }
    for(int i=0;i<=S;++i){
        for(int j=0;j<n;++j){
            if(same[i]&(1ll<<j))++g[i];
        }
    }
    for(int i=S;i>=0;--i){
        int cnt=0;
        for(int j=0;j<m;++j)if(!(i&(1<<j)))++cnt;
        if(!cnt||!g[i])continue;
        for(int j=0;j<m;++j){
            if(!(i&(1<<j))){
                f[i]+=((db)g[i^(1<<j)]*(f[i^(1<<j)]+1.0)+(db)(g[i]-g[i^(1<<j)]))/g[i]/cnt;//有g[i]-g[i^(1<<j)]个串的贡献是1;剩下的g[i^(1<<j)]个串的贡献是f[i^(1<<j)]再加1,概率是个数除以g[i]*cnt
            }
        }
    }
    printf("%.10lf",f[0]);

}

T2

有$n$个点,点$i$的度数至多为$d_i$
求恰好包含$x$个点的生成树个数

转化为prufer序列的计数
设$dp[i][j][k]$表示考虑了$i$个点,$prufer$序列长度为$j$,包含点数为$k$的方案数
那么
$dp[i][j][k]=dp[i-1][j][k]+\sum_{cnt=0}^{min(d_i-1,j)}{dp[i-1][j-cnt][k-1]*C(j,cnt)}$
注意$cnt$从$0$开始是因为
$cnt$是$prufer$序列中$i$的个数
即$i$的度数减$1$

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=105;
const int p=1e9+7;

inline ll add(ll a,ll b){
    a+=b;
    if(a>=p)a-=p;
    return a;
}

ll C[N][N];

inline void pre(){
    for(int i=0;i<N;++i){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;++j)C[i][j]=add(C[i-1][j-1],C[i-1][j]);
    }
}

int f[N][N][N];

int main(){
    freopen("neuron.in","r",stdin);
    freopen("neuron.out","w",stdout);
    int n;r(n);
    pre();
    f[0][0][0]=1;
    for(int i=1,d;i<=n;++i){
        r(d);
        for(int j=0;j<=n-2;++j){
            f[i][j][0]=f[i-1][j][0];
            for(int k=1;k<=i;++k){
                f[i][j][k]=f[i-1][j][k];
                for(int l=0;l<=min(j,d-1);++l){
                    f[i][j][k]=add(f[i][j][k],f[i-1][j-l][k-1]*C[j][l]%p);
                }
            }
        }
    }
    printf("%d ",n);
    for(int i=2;i<=n;++i)printf("%d ",f[n][i-2][i]);        
}

T3

看了题解的人都知道,这道题是给神仙做的

题解:
sam上维护lct
last相同的点放在同一棵splay
另开一棵可持久化线段树维护答案
access时更新
容斥一下。

我可能永远不会改这道题了吧

2018/9/18

TEST74

T1

选中某堆的概率比为$a_1:a_2:…:a_x$
所以选中第$i$堆的概率与选上第$1$堆的概率比为$a_i:a_1$

假如只考虑第$i$堆和第$1$堆
如果选了其中一个
那么第$i$堆比第$1$堆先选的贡献为$\frac{a_i}{a_i+a_1}$(概率为$\frac{a_i}{a_i+a_1}$,让选中$1$推迟了一次)
如果都没有选
则必有另一堆$j$有贡献$\frac{a_j}{a_j+a_1}$
总之一直到最后每个堆$x$都有贡献$\frac{a_x}{a_x+a_1}$
再加上第$1$堆的贡献$1$(选中$1$本身就需要一次)

所以期望次数是$1+\sum_{i=2}^{n}{\frac{a_i}{a_1+a_i}}$

#include<bits/stdc++.h>

using namespace std;

int main(){
    freopen("conjugate.in","r",stdin);
    freopen("conjugate.out","w",stdout);
    int n;
    double x,ans=0,t;
    scanf("%d%lf",&n,&x);
    while(--n)scanf("%lf",&t),ans+=t/(t+x);
    printf("%lf\n",ans+1);
}

2018/9/19

TEST 75

T1

大水题,考场上十多分钟就写出来了
怕不是想考我$O(1)$快速乘

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

map<ll,int>H;
int cnt[70];
int n,m;

inline void insert(ll x,int c){
    for(int i=0;(1ll<<i)<=x;++i)if(x&(1ll<<i))cnt[i]+=c;
}

inline void erase(ll x,int c){
    for(int i=0;(1ll<<i)<=x;++i)if(x&(1ll<<i))cnt[i]-=c;
}

inline void modify(ll x,ll y){
    int t=H[x];
    H[x]=0;
    H[y]+=t;
    erase(x,t);
    insert(y,t);
}

inline void add(ll& a,const ll& b,const ll& p){
    a+=b;
    if(a>=p)a-=p;
}

inline ll mul(ll a,ll b,const ll& p){
    return ((a*b-(ll)((long double)a/p*b+1e-6)*p)%p+p)%p;
}

inline void query(const ll& p){
    ll ans=0,mi=1;
    for(int i=0;i<64;++i){
        if(cnt[i])add(ans,mul(mul(n-cnt[i],cnt[i],p),mi,p),p);
        add(mi,mi,p);
    }
    add(ans,ans,p);
    printf("%lld\n",ans);
}

int main(){
    freopen("meaningless.in","r",stdin);
    freopen("meaningless.out","w",stdout);
    r(n);r(m);
    ll x;
    for(int i=1;i<=n;++i)r(x),H[x]++,insert(x,1);
    while(m--){
        int opt;
        ll x,y;
        r(opt);r(x);
        if(opt==1){
            r(y);
            modify(x,y);
        }
        else query(x);
    }
}

T2

超能粒子炮·改
lucas定理推式子的水题
然而考场上只写出暴力

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int p=2333;

int c[p][p];
int C(ll n,ll m){
    if(n<p&&m<p)return c[n][m];
    return C(n%p,m%p)*C(n/p,m/p)%p;
}

int f[p][p];
inline int F(ll n,ll k){
    if(k<0)return 0;
    if(n<p&&k<p)return f[n][k];
    return (F(n/p,k/p-1)*F(n%p,p-1)%p+C(n/p,k/p)*F(n%p,k%p)%p)%p;
}

inline int add(int a,int b){
    a+=b;
    if(a>=p)a-=p;
    return a;
}

inline void pre(){
    for(int i=0;i<p;++i){
        c[i][0]=c[i][i]=f[i][0]=1;
        for(int j=1;j<i;++j)c[i][j]=add(c[i-1][j-1],c[i-1][j]);
        for(int j=1;j<p;++j)f[i][j]=add(f[i][j-1],c[i][j]);
    }
}

int main(){
    freopen("quondam.in","r",stdin);
    freopen("quondam.out","w",stdout);
    pre();
    int T;
    for(r(T);T;--T){
        ll n,k;
        r(n);r(k);
        printf("%d\n",F(n,k));
    }
}

T3

首先这是一个多重背包
背包完了之后$f[m-min]$到$f[m-1]$都可行
但是我们并不知道跑完背包后剩下的物品的价值最小值是多少
所以我们并不知道哪些解是可行的
于是我们枚举$min$是哪个物品的价值

价值小于它的全部用完
然后这个物品至少剩下一个
其它价值大于等于它的跑背包

所以我们先对权值从大到小排序
这样我们可以保存之前的$dp$信息
新学会了复杂度$O(nm)$的多重背包
吊打二进制优化的多重背包

另外,可以开滚动数组

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)

typedef long long ll;

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=100005;
const int p=19260817;

struct Data{
    int c,w;
    bool operator < (const Data & x){
        return w>x.w;
    }
}a[N];

int n,m,sum;

int f[2][N];
bool now;

inline void add(int& a,const int& b){
    a+=b;
    if(a>=p)a-=p;
}

inline void dp(int c0,int w0){
    for(int w=0;w<w0;++w){
        int s=0,t=0;
        for(int j=0,x=w;x<=m;++j,x+=w0){
            add(s,f[now^1][x]);
            if(j-t>c0)add(s,p-f[now^1][t*w0+w]),++t;
            f[now][x]=s;
        }
    }
}

int main(){
    freopen("refrigerator.in","r",stdin);
    freopen("refrigerator.out","w",stdout);
    r(n);r(m);--m;
    for(int i=1;i<=n;++i)r(a[i].c),r(a[i].w),sum+=a[i].c*a[i].w;
    if(sum<=m)return puts("1"),0;
    sort(a+1,a+1+n);
    f[0][0]=1;
    int ans=0;
    for(int i=1;i<=n;++i){
        now^=1;
        sum-=a[i].c*a[i].w;
        dp(a[i].c-1,a[i].w);
        for(int j=max(0,m-sum-a[i].w+1);j<=m-sum;++j)add(ans,f[now][j]);
        dp(a[i].c,a[i].w);
    }
    printf("%d\n",ans);
}

TEST 76

T1

有$n$个数排成一排,一开始它们的值均为$0$,设第$i$个数为$x_i$。
给出$m$个修改操作,每个操作形如$l~ r~ a$,表示对于任意的$l\leq i\leq r$,使$x_i =max(x_i,a)$
询问$\sum_{i=1}^{n}{x_i^2}$
$a_i,n\leq 10 ^ {18},m\leq 10 ^ {5}$

做法一
按$a$排序,线段树动态开点做
然而我居然没有将询问排序还不喜欢用指针
导致我编程复杂度和空间复杂度全部爆炸
而且我还写漏了一句重要的话($100pts->0pts$)
排序后空间应该会小很多而且好写很多
但是我懒得写了,有时间再继续改吧

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int p=998244353;
const int N=1e5+7;

struct Node{
    int ls,rs;
    ll mx,mi;
    Node(){}
    Node(ll a){
        mx=mi=a;
        ls=rs=0;
    }
};

vector<Node>tr;

int id=1;

inline void modify(int rt,ll l,ll r,ll x,ll y,ll v){
    if(x<=l&&r<=y){
        if(tr[rt].mi>=v)return;
        if(tr[rt].mx<=v){
            tr[rt].mx=tr[rt].mi=v;
            return;
        }
    }
    ll mid=(l+r)>>1;
    if(!tr[rt].ls){
        tr[rt].ls=++id;
        tr.push_back(Node(tr[rt].mx));
    }
    if(!tr[rt].rs){
        tr[rt].rs=++id;
        tr.push_back(Node(tr[rt].mx));
    }
    if(tr[rt].mx==tr[rt].mi){
        tr[tr[rt].ls]=tr[tr[rt].rs]=Node(tr[rt].mx);
    }
    if(x>mid)modify(tr[rt].rs,mid+1,r,x,y,v);
    else if(y<=mid)modify(tr[rt].ls,l,mid,x,y,v);
    else modify(tr[rt].ls,l,mid,x,y,v),modify(tr[rt].rs,mid+1,r,x,y,v);
    tr[rt].mx=max(tr[tr[rt].ls].mx,tr[tr[rt].rs].mx);
    tr[rt].mi=min(tr[tr[rt].ls].mi,tr[tr[rt].rs].mi);
}

inline ll query(int rt,ll l,ll r){
    if(!rt)return 0;
    if(tr[rt].mx==tr[rt].mi){
        ll v=(tr[rt].mx%p);
        v=(r-l+1)%p*v%p*v%p;
        return v;
    }
    ll mid=(l+r)>>1;
    return (query(tr[rt].rs,mid+1,r)+query(tr[rt].ls,l,mid))%p;
}

int main(){
    freopen("segment.in","r",stdin);
    freopen("segment.out","w",stdout);
    ll n,m;
    r(n);r(m);
    tr.push_back(Node(0));
    tr.push_back(Node(0));
    while(m--){
        ll L,R,a;
        r(L);r(R);r(a);
        modify(1,1,n,L,R,a);
    }
    printf("%lld\n",query(1,1,n));
}

做法二($std$的做法)
按$l,r$排序
然后扫描每个端点,维护一个可重集储存当前最大值
然后就可以把这些修改操作分成$O(m)$个不相交的区间,各自贡献独立。

其实我考场上想这么做但是没有写出来
不然我怎么可能去写线段树(我还没有傻到会被题目名称骗到)???

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int p=998244353;

multiset<ll>S;

struct op{
    ll pos,a;
    bool type;

    op(){}
    op(ll pos,ll a,bool type):pos(pos),a(a),type(type){}

    bool operator < (const op& x)const {
        return pos<x.pos;
    }
};

vector<op>Q;

int main(){
    freopen("segment.in","r",stdin);
    freopen("segment.out","w",stdout);
    int m;
    ll n,l,r,a,ans=0;
    r(n);r(m);
    for(int i=0;i<m;++i){
        r(l);r(r);r(a);
        Q.push_back(op(l,a,1));
        Q.push_back(op(r+1,a,0));
    }
    sort(Q.begin(),Q.end());
    S.insert(0);    
    for(int i=0;i<Q.size();++i){
        if(i&&Q[i].pos!=Q[i-1].pos){
            ll Tmp=*S.rbegin()%p;
            (Tmp*=Tmp)%=p;
            (ans+=(Q[i].pos-Q[i-1].pos)%p*Tmp%p)%=p;
        }
        if(Q[i].type)S.insert(Q[i].a);
        else S.erase(S.find(Q[i].a));
    }
    printf("%lld\n",ans);
}

T2

初始还能容纳的人数为$w_i$每次减去$x$
所求即为没有$0$的子区间个数
考虑没有修改操作,用线段树维护$0$的位置,计算答案
有修改后,我们发现没有办法维护$0$的位置(总不能维护所有数的位置吧)
这个时候我们就要再次读题

保证对于任意一间房间$i$,任意时刻其人数不会超过$w_i$,但不保证人数不为负。

也就是说,可容纳人数不会小于$0$
如果区间内有$0$
那么$0$一定是区间最小值

反过来对于一个区间
如果它的最小值是$0$,我们可以用线段树维护
否则我们可以直接算出答案

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long
#define ls (rt<<1)
#define rs (rt<<1|1)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=3e5+7;

struct Seg{
    ll ans,l,r,mi,len;

    Seg operator + (const Seg &x){
        Seg ret;
        ret.len=len+x.len;
        if(mi==x.mi){
            ret.mi=mi;
            ret.l=l;
            ret.r=x.r;
            ret.ans=ans+x.ans+(r-1)*(x.l-1);
        }
        else if(mi<x.mi){
            ret.mi=mi;
            ret.l=l;
            ret.r=r+x.len;
            ret.ans=ans+(r-1)*x.len+((x.len+1)*x.len>>1);
        }
        else {
            ret.mi=x.mi;
            ret.l=len+x.l;
            ret.r=x.r;
            ret.ans=((len+1)*len>>1)+(x.l-1)*len+x.ans;
        }
        return ret;
    }
}tr[N<<2];

ll tag[N<<2];
int w[N];

inline void pushdown(int rt){
    if(tag[rt]){
        tag[ls]+=tag[rt];
        tag[rs]+=tag[rt];
        tr[ls].mi+=tag[rt];
        tr[rs].mi+=tag[rt];
        tag[rt]=0;
    }
}

inline void build(int rt,int l,int r){
    if(l==r){
        tr[rt].mi=w[l];
        tr[rt].l=tr[rt].r=tr[rt].len=1;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    tr[rt]=tr[ls]+tr[rs];
}

inline void modify(int rt,int l,int r,int x,int y,int v){
    if(x<=l&&r<=y){
        tr[rt].mi+=v;
        tag[rt]+=v;
        return;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(x<=mid)modify(ls,l,mid,x,y,v);
    if(mid<y)modify(rs,mid+1,r,x,y,v);
    tr[rt]=tr[ls]+tr[rs];
}

inline Seg query(int rt,int l,int r,int x,int y){
    if(x<=l&&r<=y)return tr[rt];
    pushdown(rt);
    int mid=(l+r)>>1;
    if(y<=mid)return query(ls,l,mid,x,y);
    if(x>mid)return query(rs,mid+1,r,x,y);
    return query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y);
}

int main(){
    freopen("hotel.in","r",stdin);
    freopen("hotel.out","w",stdout);
    int n,m;r(n);r(m);
    for(int i=1;i<=n;++i)r(w[i]);
    build(1,1,n);
    while(m--){
        int opt,l,r,x;
        r(opt),r(l),r(r);
        if(opt==1){
            r(x);
            modify(1,1,n,l,r,-x);
        }
        else {
            Seg ret=query(1,1,n,l,r);
            if(ret.mi)printf("%lld\n",(ll)(r-l+1)*(r-l+2)/2);
            else printf("%lld\n",ret.ans);
        }
    }
}

T3

打表找规律

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=5e5+7;
const int p=998244353;

int f[N];

inline void add(int &a,int b){
    if((a+=b)>=p)a-=p;
}

int main(){
    freopen("recursion.in","r",stdin);
    freopen("recursion.out","w",stdout);
    ll n;r(n);
    f[1]=1;
    f[2]=2;
    ll l=1,r;
    int sum1=1,sum2=1;
    for(int i=2;l<n;++i){
        r=min(n,l+f[i]);
        for(int j=l+1;j<=min((ll)(5e5),r);++j)f[j]=i;
        add(sum1,(ll)(r-l)*i%p);
        add(sum2,((l+r+1)*(r-l)>>1)%p*i%p);
        l=r;
    }
    printf("%d %d\n",sum1,sum2);
}

2018/9/21

Test77

T1

模拟即可

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()

const int N=1005;


inline void read(char *s,int &n){
    char gc;n=0;
    while(c!='\n'&&c!=EOF)s[n++]=c,gc;
}

int n,m;
char s[N],t[N];
char mp[30];

inline bool is(char x){
    return 'a'<=x&&x<='z';
}

inline bool check(){
    if(n!=m)return 0;
    memset(mp,0,sizeof(mp));
    for(int i=0;i<n;++i){
        if(is(t[i])){
            if(!is(s[i])||(mp[t[i]-'a']&&mp[t[i]-'a']!=s[i]))return 0;
            mp[t[i]-'a']=s[i];
        }
        else if(s[i]!=t[i])return 0;
    }
    return 1;
}

int main(){
    freopen("copycat.in","r",stdin);
    freopen("copycat.out","w",stdout);
    int T;
    scanf("%d\n",&T);
    while(T--){
        read(t,n);read(s,m);
        printf("%d\n",check());
    }
}

T2

边按温度排序,依次加边
并查集维护$S$与$T$的连通性
可以找出最小温度
然后按热量跑最短路

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const ll INF=1e18;
const int N=5e5+5;
const int M=1e6+5;

int n,m,S,T,ecnt;
int fir[N],nex[M<<1],to[M<<1];
ll dis[N],w[M<<1],t[M<<1],c[M<<1];

struct data{
    ll a,b;
    bool operator < (const data& x)const{
        return a>x.a;
    }
};

priority_queue<data>Q;
inline void dijkstra(){
    for(int i=1;i<=n;++i)dis[i]=INF;
    dis[S]=0;
    Q.push(data{0,S});
    while(!Q.empty()){
        int x=Q.top().b;
        ll d=Q.top().a;
        Q.pop();
        if(d!=dis[x])continue;
        for(int i=fir[x],v;i;i=nex[i]){
            ll t=d+w[i];
            if(t<dis[v=to[i]]&&t<dis[T]){
                dis[v]=t;
                Q.push(data{t,v});
            }
        }
    }
}

struct edge{
    int u,v;
    ll x,y,w;
    inline void init(int _u,int _v,int _x,int _y){
        u=_u,v=_v,x=_x,y=_y,w=x*y;
    }
    bool operator < (const edge& a){
        return x<a.x;
    }
}Tmp[M];

inline void addedge(int u,int v,ll c){
    nex[++ecnt]=fir[u];fir[u]=ecnt;to[ecnt]=v;w[ecnt]=c;
    nex[++ecnt]=fir[v];fir[v]=ecnt;to[ecnt]=u;w[ecnt]=c;
}

int fa[N];

int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

inline void uni(int x,int y){
    if(find(x)!=find(y))fa[find(x)]=find(y);
}

int main(){
    freopen("running.in","r",stdin);
    freopen("running.out","w",stdout);
    r(n),r(m);
    for(int i=1,u,v,x,y;i<=m;++i){
        r(u),r(v),r(x),r(y);
        Tmp[i].init(u,v,x,y);
    }
    ll maxv;
    r(S),r(T);
    sort(Tmp+1,Tmp+m+1);
    for(int i=1;i<=n;++i)fa[i]=i;
    for(int i=1;i<=m;++i){
        uni(Tmp[i].u,Tmp[i].v);
        if(find(S)==find(T)){
            maxv=Tmp[i].x;
            for(int j=1;Tmp[j].x<=maxv&&j<=m;++j){
                addedge(Tmp[j].u,Tmp[j].v,Tmp[j].w);
            }
            break;
        }
    }
    dijkstra();
    printf("%lld %lld\n",maxv,dis[T]);
}

Tset78

T1

模拟即可
代码太丑,不放了

T2

因为保证construct操作前坐标区间$[l,r]$ 中不存在信号站
所以写个set维护就好了
考虑插入,可能把一个区间拆成两半在插入,也可能直接插入
考虑删除,对于边界上的区间可能拆成两半,一半删除,也可能直接删除
考虑询问,可能在两个区间中间,也可能在一个区间内部,可能靠近右边的点,也可能靠近左边的点
然后就完了

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=2e5+7;
const int INF=1e9;

struct Data{
    int l,r,v;

    Data(){}
    Data(int _l,int _r,int _v){l=_l,r=_r,v=_v;}

    bool operator < (const Data &a)const{
        return l<a.l;
    }
};

char s[20];

int m;
ll c;

set<Data>S;
set<Data>::iterator it;

inline ll sqr(ll x){
    return x*x;
}

inline int getr(int l,int r,int v){
    return l+(r-l)/v*v;
}

inline int getl(int l,int r,int v){
    return r-(r-l)/v*v;
}

inline void Insert(int l,int r,int v){
    r=getr(l,r,v);
    it=S.upper_bound(Data(l,0,0));
    if(it!=S.begin()){
        Data Tmp=*(--it);
        if(Tmp.l<l&&Tmp.r>r){
            S.erase(it);
            S.insert(Data(Tmp.l,getr(Tmp.l,l,Tmp.v),Tmp.v));
            S.insert(Data(getl(r,Tmp.r,Tmp.v),Tmp.r,Tmp.v));
        }
    }
    S.insert(Data(l,r,v));
}

inline void Erase(int l,int r){
    it=S.lower_bound(Data(l,0,0));
    if(it!=S.begin()){
        Data Tmp=*(--it);
        if(Tmp.l<l&&Tmp.r>=l){
            S.erase(it);
            S.insert(Data(Tmp.l,getr(Tmp.l,l-1,Tmp.v),Tmp.v));
        }
    }
    it=S.upper_bound(Data(r,0,0));
    if(it!=S.begin()){
        Data Tmp=*(--it);
        if(Tmp.l<=r&&Tmp.r>r){
            S.erase(it);
            S.insert(Data(getl(r+1,Tmp.r,Tmp.v),Tmp.r,Tmp.v));
        }
    }
    S.erase(S.lower_bound(Data(l,0,0)),S.upper_bound(Data(r,0,0)));
}

inline ll Query(int x){
    it=S.lower_bound(Data(x,0,0));
    int dist=INF;
    if(it!=S.end())dist=(*it).l-x;
    if(it!=S.begin()){
        Data Tmp=*(--it);
        if(Tmp.r<=x)dist=min(dist,x-Tmp.r);
        else {
            dist=min(dist,x-getr(Tmp.l,x,Tmp.v));
            dist=min(dist,getl(x,Tmp.r,Tmp.v)-x);
        }
    }
    if(dist==INF)return 0;
    return max(0ll,c-sqr(dist));
}

int main(){
    freopen("cellphone.in","r",stdin);
    freopen("cellphone.out","w",stdout);
    r(m);r(c);
    while(m--){
        scanf("%s",s);
        if(s[0]=='c'){
            int l,r,v;r(l),r(r),r(v);
            Insert(l,r,v);
        }
        else if(s[0]=='d'){
            int l,r;r(l),r(r);
            Erase(l,r);
        }
        else {
            int x;r(x);
            printf("%lld\n",Query(x));
        }
    }
    return 0;
}

2018/9/22

Test79

东辰学校出的烂题$T1$,$T3$秒切,$T2$完全看不懂

T1

考场代码,还有较大优化空间
题解说卡double,然而我早有准备
听说有人被卡精度,我关了防卡机制结果还是过了

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long
#define db double

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=2e5+7;

struct Point{
    ll x,y,rx,ry;
    Point(){}
    Point(ll x,ll y,ll rx,ll ry):x(x),y(y),rx(rx),ry(ry){}
}A[N];

inline bool cmp(const Point &a,const Point &b){
    return a.y<b.y;
}

inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}

struct Fen{
    db val;
    Fen(){}
    Fen(ll x,ll y){
        x=abs(x),y=abs(y);
        ll t=gcd(x,y);//防卡精度
        x/=t,y/=t;
        val=(db)x/(db)(y);
    }
    friend bool operator < (const Fen &a,const Fen &b) {
        return a.val<b.val;
    }
    friend bool operator == (const Fen &a,const Fen &b) {
        return a.val==b.val;
    }
};

inline Fen slope(const Point &a,const Point &b){
    return Fen((a.y-b.y),(a.x-b.x));
}

int main(){
    freopen("slope.in","r",stdin);
    freopen("slope.out","w",stdout);
    int n;
    ll p,q;
    r(n);r(p);r(q);
    for(int i=1,x,y;i<=n;++i)r(x),r(y),A[i]=Point(x*q,y*q-x*p,x,y);
    sort(A+1,A+n+1,cmp);
    Fen ans;ans.val=1e18;
    ll x,y;
    for(int i=1;i<n;++i){
        Fen k=slope(A[i],A[i+1]);
        if(k<ans){
            ans=k;
            x=A[i].rx-A[i+1].rx;
            y=A[i].ry-A[i+1].ry;
        }
        else if(k==ans){
            if(Fen(A[i].ry-A[i+1].ry,A[i].rx-A[i+1].rx)<Fen(y,x)){
                ans=k;
                x=A[i].rx-A[i+1].rx;
                y=A[i].ry-A[i+1].ry;
            }
        }
    }
    if(x<0&&y<=0)x=-x,y=-y;
    ll t=gcd(x,y);
    printf("%lld/%lld\n",y/t,x/t);
}

T3

没有看懂题解,我写的吉司机线段树

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long
#define ls (rt<<1)
#define rs (rt<<1|1)

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N=1e5+7;

int dfs_clock;
int dfn[N],siz[N];
ll sum[N],val[N];

vector<int> G[N];
vector<int> V[N];

inline void dfs(int x){
    dfn[x]=++dfs_clock;
    val[dfs_clock]=sum[x];
    siz[x]=1;
    for(int i=0;i<G[x].size();++i){
        sum[G[x][i]]=sum[x]+V[x][i];
        dfs(G[x][i]);
        siz[x]+=siz[G[x][i]];
    }
}

struct seg{
    ll mx,se,t,mi,sum;

    seg operator +(const seg & x){
        seg ret;
        if(mx==x.mx){
            ret.mx=mx;
            ret.se=max(se,x.se);
            ret.t=t+x.t;
        }
        else if(mx>x.mx){
            ret.mx=mx;
            ret.se=max(se,x.mx);
            ret.t=t;
        }
        else {
            ret.mx=x.mx;
            ret.se=max(mx,x.se);
            ret.t=x.t;
        }
        ret.mi=min(mi,x.mi);
        ret.sum=sum+x.sum;
        return ret;
    }
}tr[N<<2];

inline void build(int rt,int l,int r){
    if(l==r){
        tr[rt].mx=tr[rt].mi=tr[rt].sum=val[l];
        tr[rt].se=0;
        tr[rt].t=1;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    tr[rt]=tr[ls]+tr[rs];
}

inline ll query(int rt,int l,int r,int x,int y,ll k,ll s){
    if(x<=l&&r<=y){
        if(tr[rt].mx<k)return 0;
        if(tr[rt].se<k)return (tr[rt].mx-s)*tr[rt].t;
        if(tr[rt].mi>=k)return tr[rt].sum-s*(r-l+1);
    }
    int mid=(l+r)>>1;
    if(y<=mid)return query(ls,l,mid,x,y,k,s);
    if(x>mid)return query(rs,mid+1,r,x,y,k,s);
    return query(ls,l,mid,x,y,k,s)+query(rs,mid+1,r,x,y,k,s);
}

int main(){
    freopen("forging.in","r",stdin);
    freopen("forging.out","w",stdout);
    int n;r(n);
    for(int i=2,f,w;i<=n;++i){
        r(f);r(w);
        G[f].push_back(i);
        V[f].push_back(w);
    }
    dfs(1);
    build(1,1,n);
    int q;r(q);
    while(q--){
        int u,k;
        r(u),r(k);
        printf("%lld\n",query(1,1,n,dfn[u],dfn[u]+siz[u]-1,k+sum[u],sum[u]));
    }
}

2 条评论

XZYQvQ · 2018年8月28日 10:40 下午

你们什么时候还开启了评论,很强啊Orz
(似乎现在重新设定以后大家都有了自己的进程表的所有权限OvO)
其实我没试过

Mr_asd · 2018年8月28日 10:27 下午

强强强

发表评论

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

你是机器人吗? =。= *