从前有一个叫做LL的人，

他由于太蒟蒻了

很悲伤

 

1.足球比赛

推出了式子，不会组合数线性求法

写了个n^2dp  炸了

有点痛

#include
     
      #define ll long longusing namespace std;template
      
       inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=1e7+5,mod=1e9+7;int inv[maxn];inline int pow(int a,int x){    int ret=1;    while(x)     {        if(x&1)ret=1ll*ret*a%mod;        x>>=1;        a=1ll*a*a%mod;    }    return ret;} int main(){    int n,pa,pb,qa,qb,invb;//    freopen("in.txt","r",stdin);    rd(n);    rd(pa),rd(pb),rd(qa),rd(qb);    if(pa==pb)    {        ll x=pow(qa,n);        ll y=pow(qb,n);        invb=pow(qb,(int)(1ll*n*(mod-2)%(mod-1)));        printf("%lld",1ll*invb*(y-x+mod)%mod);    }    else if(!qa)    {        ll x=pow(pb-pa,n);        ll y=pow(pb,n);        invb=pow(pb,(int)(1ll*n*(mod-2)%(mod-1)));        printf("%lld",1ll*(y-x+mod)%mod*invb%mod);    }    else if(!pa||qa==qb)    {        printf("0");    }    else     {        inv[1]=inv[0]=1;        for(register int i=2;i<=n;++i)            inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;        invb=pow((int)(1ll*pb*qb%mod),(int)(1ll*n*(mod-2)%(mod-1)));        int P=pow(pb-pa,mod-2),Q=pow(qb-qa,mod-2);                int lastq=pow(qb-qa,n),lastp=1ll*pa*pow(pb-pa,n-1)%mod;        int sum=lastq,C=n,ans=(ans+1ll*sum*C%mod*lastp%mod)%mod;        for(register int i=2;i<=n;++i)        {            lastp=1ll*lastp*pa%mod*P%mod;            lastq=1ll*lastq*qa%mod*Q%mod;            sum=(sum+1ll*lastq*C)%mod;            C=1ll*C*(n-i+1)%mod*inv[i]%mod;            ans=(ans+1ll*sum*C%mod*lastp)%mod;        }            printf("%d",1ll*ans*invb%mod);    }     return 0;}
      
     

2. 文明

虽然明知道是树剖

还是很暴力地用十分钟写了个Lca倍增

#include
     
      #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
      
       inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=5e5+5;int n,m,k=1,tot,son[maxn],top[maxn],rev[maxn],fa[maxn];int hd[maxn],deep[maxn],siz[maxn],seg[maxn],he[maxn];struct node{    int to,nt;}e[maxn<<1];inline void add(int x,int y){    e[++k].to=y;e[k].nt=hd[x];hd[x]=k;    e[++k].to=x;e[k].nt=hd[y];hd[y]=k;}inline void dfs(int x){    deep[x]=deep[fa[x]]+(siz[x]=1);    for(int i=hd[x];i;i=e[i].nt)    {        int v=e[i].to;        if(v==fa[x])continue;        fa[v]=x;        dfs(v);        siz[x]+=siz[v];        if(siz[v]>siz[son[x]])        son[x]=v;    }}inline void dfs2(int x,int ftop){    top[x]=ftop;    seg[x]=++tot;    rev[tot]=x;    if(son[x])    {        dfs2(son[x],ftop);        for(int i=hd[x];i;i=e[i].nt)        {            int v=e[i].to;            if(!top[v])            dfs2(v,v);        }    }}int sum[maxn<<2],lazy[maxn<<2];#define ls rt<<1#define rs rt<<1|1inline void pushup(int rt){    sum[rt]=sum[ls]+sum[rs];}inline void pushdown(int rt,int l,int r,int mid){    lazy[ls]=lazy[rs]=lazy[rt];    if(lazy[rt]==1)    sum[ls]=mid-l+1,sum[rs]=r-mid;    else sum[ls]=sum[rs]=0;    lazy[rt]=0;}inline void build(int rt,int l,int r){    if(l==r)    {        sum[rt]=1;        re ;    }        int mid=(l+r)>>1;    build(ls,l,mid);    build(rs,mid+1,r);    pushup(rt);}inline void modify(int rt,int l,int r,int x,int y){    if(x<=l&&r<=y)    {        sum[rt]=0;        lazy[rt]=2;        re ;    }    int mid=(l+r)>>1;    if(lazy[rt])pushdown(rt,l,r,mid);    if(x<=mid)modify(ls,l,mid,x,y);    if(y>mid)modify(rs,mid+1,r,x,y);    pushup(rt);}inline int LCA(int x,int y){    while(top[x]!=top[y])    {        if(deep[top[x]]
       
        =deep[x]-deep[fa[top[x]]])    {        dis-=(deep[x]-deep[fa[top[x]]]);        x=fa[top[x]];    }    re rev[seg[x]-dis];}int main(){    int x,y,rt,k;    rd(n),rd(m);    inc(i,2,n)    {        rd(x),rd(y);        add(x,y);    }        fa[1]=1;    dfs(1);    dfs2(1,1);    build(1,1,n);    inc(i,1,m)    {        lazy[1]=1;        sum[1]=n;        rd(k);        rd(rt);        inc(j,1,k-1)        {            rd(x);            int lca=LCA(x,rt);            int left=deep[rt]-deep[lca],right=deep[x]-deep[lca];            if(left<=right)            {                int v=jump(x,(left+right-1)>>1);                modify(1,1,n,seg[v],seg[v]+siz[v]-1);            }            else            {                int v=jump(rt,(left+right)>>1);                modify(1,1,n,1,seg[v]-1);                modify(1,1,n,seg[v]+siz[v],n);            }        }        printf("%d\n",sum[1]);    }    re 0;}
       
      
     

3.贪玩蓝月

渣渣辉……

暴力背包合并+单调队列

#include
      
       #define re return#define ll long long#define dec(i,l,r) for(int i=l;i>=r;--i)#define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int N=5e4+10;int P;struct node{    int w,v;    node(int ww=0,int vv=0){        w=ww;v=vv;    }}Q[N];struct quu{    ll top,f[N][505];    node g[N];    inline void init()    {        top=f[0][0]=0;        inc(i,1,P-1)f[0][i]=-1147483647;    }    inline void push(node x)    {        g[++top]=x;        inc(i,0,P-1)        f[top][(i+x.w)%P]=max(f[top-1][(i+x.w)%P],f[top-1][i]+x.v);         }}L,R;inline void rebuild(){    int r=0;    dec(i,L.top,1)Q[++r]=L.g[i];    inc(i,1,R.top)Q[++r]=R.g[i];    L.init();R.init();    //重新初始化     int mid=r>>1;    dec(i,mid,1)  L.push(Q[i]);    inc(i,mid+1,r)R.push(Q[i]);    }inline int Next(int x){re x>0?x-1:P-1;}inline bool check_in(int x,int l,int r){    if(l<=r){re (x>=l&&x<=r);}    else re x>=l||x<=r;}int q[1005];inline void query(int l,int r){    int head=1,tail=0;    ll ans=-1;    dec(i,r,l)    {        while(head<=tail&&L.f[L.top][i]>=L.f[L.top][q[tail]])--tail;        q[++tail]=i;        ans=max(ans,L.f[L.top][i]+R.f[R.top][0]);    }    //初始化单调序列     l=Next(l),r=Next(r);    for(int i=1;i<=P-1;++i,l=Next(l),r=Next(r))    {        while(head<=tail&&(!check_in(q[head],l,r)))++head;        while(head<=tail&&L.f[L.top][l]>=L.f[L.top][q[tail]])--tail;        q[++tail]=l;        ans=max(ans,L.f[L.top][q[head]]+R.f[R.top][i]);    }     if(ans<0)    printf("-1\n");    else printf("%lld\n",ans);    re ;}int m;int main(){    //freopen("in.txt","r",stdin);    int test_id,x,y;    rd(test_id);//输入测试数据编号     rd(m),rd(P);//操作数以及模数     L.init(),R.init();//左右区间初始化     char opt[20];    inc(i,1,m)    {        scanf("%s",opt);        if(opt[0]=='I'&&opt[1]=='F')        {            rd(x),rd(y);            L.push((node){x,y});//左端进入         }        else if(opt[0]=='I')//右端加入         {            rd(x),rd(y);            R.push((node){x,y});        }        else if(opt[0]=='D'&&opt[1]=='F')//左端弹出         {            if(!L.top)rebuild();//没有了。暴力重构             if(L.top)--L.top;//有直接减             else --R.top;                    }        else if(opt[0]=='D')        {            if(!R.top)                rebuild();            if(R.top)--R.top;//其实Rebuild后R.top还等于0应该是不存在的                 else --L.top;                    }        else         {            rd(x),rd(y);            //查询             query(x,y);        }    }    re 0;}
       
      

 

 

——九月22日考试有感