XR-4 混乱度

题目

链接

简答

根据 Kummer 定理，$\binom{a_1+a_2+\cdots+a_n}{a_1,a_2,\cdots,a_n}$ 在模 $p$ 意义下不为0当前仅当 $p$ 进制下不进位

考虑固定右端点枚举左端点，$p$ 进制下所有位上的和都必须小于 $p$ ，所有至多往左枚举 $p\log_p A$ 项，但这样是 $\log_p^2A$ 的，直接枚举非 $0$ 位就是 $\mathcal{O}\left(np\log_p A\right)$

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N=500010;
int p,dg[N],num[N][100][2],n,cnt[100],lim,inv[100],fac[100],ifac[100];ull a[N];
int main(){
    scanf("%d%d",&n,&p);if(p==2) lim=60;else if(p==3) lim=40;else if(p==5) lim=30;else lim=25;
    inv[1]=1;for(int i=2;i<p;++i) inv[i]=(p-p/i)*inv[p%i]%p;
    fac[0]=ifac[0]=1;for(int i=1;i<p;++i) fac[i]=fac[i-1]*i%p,ifac[i]=inv[fac[i]];
    for(int i=1;i<=n;++i){
        scanf("%llu",&a[i]);
        for(int j=0;j<lim;++j){
            if(a[i]%p) num[i][dg[i]][0]=j,num[i][dg[i]][1]=a[i]%p,++dg[i];
            a[i]/=p;
        }
    }
    ull ans=0;
    for(int i=1;i<=n;++i){
        memset(cnt,0,sizeof(int)*(lim+5));
        int cur=1;
        for(int l=i;l;--l){
            bool cap=true;
            for(int k=0;k<dg[l];++k){
                int pos=num[l][k][0],t=num[l][k][1];
                if(cnt[pos]+t>=p){cap=false;break;}
                cur=cur*ifac[cnt[pos]]%p;cnt[pos]+=t;
                cur=cur*ifac[t]*fac[cnt[pos]]%p;
            }
            if(!cap) break;
            ans+=cur;
            // printf("%d %d %d\n",i,l,cur);
        }
    }
    printf("%llu\n",ans);
    return 0;
}

APIO2021 封闭道路 (CF1119F Niyaz and Small Degrees)

题目

APIO CF

简答

由于 $\sum d\left(x\right)=2n-2$ , 所以所有点需要被考虑的次数总和是 $\mathcal{O}\left(n\right)$ 的，考虑优化单次复杂度

设 $dp$ 状态 $f_{i,0/1}$ 表示是否会删和父节点那条边的最小代价

那么每次 $dp$ 的时候就是从 $f_{v,1}+e_{u,v}-f_{v,0},e_{u,v'}$ 中选出最小的一些点再加上 $\sum f_{v,0}$ ，平衡树维护即可

注意精细实现使得总复杂度 $\mathcal{O}\left(n\log n\right)$

代码

#include <cstdio>
#include <algorithm>
#include <random>
using namespace std;
typedef long long ll;
constexpr int N=250010,inf=1e9;
constexpr ll linf=1e18;
mt19937 rde;
uniform_int_distribution<int> rnd(0,inf);
struct Tree{
    int rd[N<<3],ch[N<<3][2],cnt[N<<3],sz;ll sum[N<<3],val[N<<3];
    void pushup(int u){cnt[u]=cnt[ch[u][0]]+cnt[ch[u][1]]+1,sum[u]=sum[ch[u][0]]+sum[ch[u][1]]+val[u];}
    void split(int u,int &x,int &y,int k){
        if(!u){x=y=0;return;}if(!k){y=u,x=0;return;}
        if(cnt[ch[u][0]]>=k) y=u,split(ch[u][0],x,ch[u][0],k);
        else x=u,split(ch[u][1],ch[u][1],y,k-cnt[ch[u][0]]-1);
        pushup(u);
    }
    void split_val(int u,int &x,int &y,ll k){
        if(!u){x=y=0;return;}
        if(val[u]<=k) x=u,split_val(ch[u][1],ch[u][1],y,k);
        else y=u,split_val(ch[u][0],x,ch[u][0],k);
        pushup(u);
    }
    int merge(int x,int y){
        if(!x || !y) return x|y;
        if(rd[x]<rd[y]){ch[x][1]=merge(ch[x][1],y);pushup(x);return x;}
        ch[y][0]=merge(x,ch[y][0]);pushup(y);return y;
    }
    ll query(int &u,int k){
        int t1=0,t2=0;split(u,t1,t2,k);
        // print(t1),print(t2);
        ll ret=sum[t1];u=merge(t1,t2);
        return ret;
    }
    void del(int &u,ll k,int gdb){
        // printf("deleting %d from %d\n",k,gdb);
        // print(u);
        int t1=0,t2=0,t3=0,t4=0;split_val(u,t1,t2,k);
        // printf("fck\n");
        split(t1,t3,t4,cnt[t1]-1);
        // printf("%d %d %d %d\n",t1,t2,t3,t4);
        u=merge(t3,t2);
        // printf("comp\n");
    }
    void insert(int &u,ll k,int gdb){
        // printf("inserting %d to %d\n",k,gdb);
        ++sz;cnt[sz]=1;sum[sz]=val[sz]=k;rd[sz]=rnd(rde);
        int t1=0,t2=0;split_val(u,t1,t2,k);u=merge(t1,sz);u=merge(u,t2);
        // print(u);
    }
    void print(int u){
        printf("tree %d %d %d %lld %lld\n",u,ch[u][0],ch[u][1],sum[u],val[u]);
        if(ch[u][0]) print(ch[u][0]);if(ch[u][1]) print(ch[u][1]);
    }
}T;
#define pr pair<int,int>
#define fr first
#define sd second
vector<pr > es[N];int deg[N],n,rts[N];ll f[N][2];
vector<int> pts[N];bool vis[N];
void solve(int u,int fa,int wgt,int lim){
    // printf("%d %d %d %d\n",u,fa,wgt,lim);
    if(fa) T.del(rts[u],wgt,u);int cur=0;ll sum=0;
    vis[u]=true;
    for(auto v:es[u]) if(v.fr!=fa){
        if(deg[v.fr]<=lim) break;
        solve(v.fr,u,v.sd,lim);int j=v.fr;
        T.del(rts[u],v.sd,u);
        if(f[j][1]+v.sd<=f[j][0]) ++cur,sum+=f[j][1]+v.sd;
        else T.insert(rts[u],f[j][1]+v.sd-f[j][0],u),sum+=f[j][0];
    }
    if(cur>=deg[u]-lim-1) f[u][1]=sum;
    else f[u][1]=sum+T.query(rts[u],deg[u]-lim-cur-1);
    // T.print(rts[u]);printf("%d cur:%d sum: %lld\n",u,cur,sum);
    if(!lim && fa) f[u][0]=linf;
    else if(cur>=deg[u]-lim) f[u][0]=sum;
    else f[u][0]=T.query(rts[u],deg[u]-lim-cur)+sum;
    for(auto v:es[u]) if(v.fr!=fa){
        if(deg[v.fr]<=lim) break;int j=v.fr;
        T.insert(rts[u],v.sd,u);
        if(f[j][1]+v.sd>f[j][0]) T.del(rts[u],f[j][1]+v.sd-f[j][0],u);
    }
    if(fa) T.insert(rts[u],wgt,u);
}
int main(){
    scanf("%d",&n);
    for(int i=1,ta,tb,tc;i<n;++i) scanf("%d%d%d",&ta,&tb,&tc),T.insert(rts[ta],tc,ta),T.insert(rts[tb],tc,tb),
                                  es[ta].push_back(make_pair(tb,tc)),es[tb].push_back(make_pair(ta,tc)),++deg[ta],++deg[tb];
    for(int i=1;i<=n;++i) sort(es[i].begin(),es[i].end(),[](auto a,auto b){return deg[a.fr]>deg[b.fr];});
    for(int i=1;i<=n;++i) for(int j=0;j<deg[i];++j) pts[j].push_back(i);
    // printf("hey\n");
    for(int i=0;i<n;++i){
        ll ans=0;
        for(auto j:pts[i]) if(!vis[j]) solve(j,0,0,i),ans+=f[j][0];
        for(auto j:pts[i]) vis[j]=false;
        printf("%lld ",ans);
    }
    printf("\n");
    return 0;
}

LOJ 577 简单算术

题目

链接

简答

有个有趣的小结论，对于多项式 $F\left(x\right),p\in \mathbb{P}$ ，$F\left(x \right)^p\equiv \sum_{i\ge0} f_ix^{pi}\pmod{p}$

有这个结论直接记忆化递归即可，复杂度 $\mathcal{O}\left(poly\left(n\right)poly\left(p\right)Q+pn^2\right)$

代码

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
constexpr int N=60;
int a[N],p,n,T,poly[N][N*N];
map<pair<ll,ll>,int> mm;
int solve(ll m,ll k){
    if(m<p) return poly[m][k];
    if(mm.count(make_pair(m,k))) return mm[make_pair(m,k)];
    ll g=m/p,r=m%p;int ret=0;
    for(int i=k%p;i<=r*n && i<=k;i+=p) ret=(ret+poly[r][i]*solve(g,(k-i)/p)%p)%p;
    mm[make_pair(m,k)]=ret;
    return ret;
}
int main(){
    scanf("%d%d",&n,&p);
    for(int i=0;i<=n;++i) scanf("%d",&a[i]),poly[1][i]=a[i];poly[0][0]=1;
    for(int i=2;i<p;++i) for(int j=0,l2=(i-1)*n;j<=n;++j) for(int k=0;k<=l2;++k) poly[i][j+k]=(poly[i][k+j]+a[j]*poly[i-1][k]%p)%p;
    scanf("%d",&T);
    while(T--){
        ll m,k;scanf("%lld %lld",&m,&k);
        printf("%d\n",solve(m,k));
    }
    return 0;
}

IOI2019 矩形区域

题目

链接

简答

考虑每行每列中合法的区间，不妨设 $a_{l-1}\ge a_{r+1}$

则位置 $k$ 作为区间右端点 $+1$ 时，左端点 $-1$ 只会是 $\arg\max_{i}a_i\ge a_k$ ，因此每行每列合法的区间数是 $\mathcal{O}\left(n\right)$

考虑此时所有行的合法区间，上下连着的左右端点相同的区间可以被扔到列上查询

若此时行的合法区间上下左右边界是 $\left[r_0,r_1\right],\left[c_0,c_1\right]$ ，则在 $c_1$ 这一列查询这一列上能向左延申 $\ge c_1-c_0+1$ 的且 $\subseteq\left[r_0,r_1\right]$ 的合法区间个数

此时每一列上变成一个三维偏序，对所有区间和询问的延申长度排序就变为求当前有多少个区间 $\subseteq\left[r_0,r_1\right]$ ， 即二维偏序

由于行的总合法区间个数是 $\mathcal{O}\left(nm\right)$ 的，所以所有区间查询的 $\sum r_1-r0+1$ 是 $\mathcal{O}\left(nm\right)$ 的

所以直接暴力枚举右端点，求有多少个左端点 $\ge r_0$，$\sum_{i=r_0}^{r_1}\sum_{segs} \left[l\ge r_0\right]\left[r=i\right]$，直接建 $n$ 棵树状数组维护，更新一个区间时在右端点那个后缀数组上修改，查询时对于 $\left[l,r\right]$ 每个线段树查询相加即可

总复杂度 $\mathcal{O}\left(nm\log_2m\right)$

精细实现一下直接LOJ rk1

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctype.h>
#include <vector>
using namespace std;
typedef long long ll;
constexpr int N=2510,inf=1e9;
int rl[N][N<<1],rr[N][N<<1],rcnt[N],rg[N][N<<1];bool rb[N][N<<1];
int cl[N][N<<1],cr[N][N<<1],ccnt[N],cg[N][N<<1];bool cb[N][N<<1];
struct qry{int l,r,x;};vector<qry> qls[N];
int n,m,a0[N][N],a1[N][N],qtmp[N*N],ctmp[N<<1],qx0[N*N];
int bt[N][N];
void add(int *arr,int x,int v,int lim){for(;x<=lim;x+=(x&(-x))) arr[x]+=v;}
int query(int *arr,int x){int ret=0;for(;x;x-=(x&(-x))) ret+=arr[x];return ret;}
void bkt_sort(int *res,int *nums,int t,int lim){
    static int cnt[N];memset(cnt,0,sizeof(int)*(lim+2));
    for(int i=1;i<=t;++i) ++cnt[nums[i]];
    for(int i=lim-1;i;--i) cnt[i]+=cnt[i+1];
    for(int i=t;i;--i) res[cnt[nums[i]]--]=i;
}
struct stck{
    int dt[N<<1],cnt;bool ity(){return cnt==0;}int top(){return dt[cnt];}void push(int val){dt[++cnt]=val;}void pop(){--cnt;}void init(){cnt=0;}
}f1;
namespace fr{
    char buf[1<<23],obuf[1<<23],*p1=buf,*p2=buf,*O=obuf;
    #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    template<typename T>
    void rd(T &res){
        bool flag=false;T ret=0;static char c;c=getchar();
        while(!isdigit(c) && c!='-') c=getchar();
        // printf("%c\n",c);
        if(c=='-') flag=true,c=getchar();while(isdigit(c)) ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
        res=flag?-ret:ret;
    }
    template<typename T>
    void write(T k){
        if(k<0) *O++=='-';
        if(k>=10) write(k/10);
        *O++=k%10+'0';
    }
    void flush(){
        fwrite(obuf,O-obuf,1,stdout);
    }
}
int main(){
    // freopen("ioi.in","r",stdin);
    fr::rd(n),fr::rd(m);
    // printf("%d %d\n",n,m);
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) fr::rd(a0[i][j]),a1[j][i]=a0[i][j];
    for(int i=1;i<=n;++i){
        f1.init();f1.push(1);
        for(int j=2;j<=m;++j){
            int cur;
            while(!f1.ity() && a0[i][cur=f1.top()]<a0[i][j]){
                if(cur<j-1) ++rcnt[i],rl[i][rcnt[i]]=cur+1,rr[i][rcnt[i]]=j-1;
                f1.pop();
            }
            if(!f1.ity()){
                cur=f1.top();
                if(cur<j-1) ++rcnt[i],rl[i][rcnt[i]]=cur+1,rr[i][rcnt[i]]=j-1;
                if(a0[i][cur]==a0[i][j]) f1.pop();
            }
            f1.push(j);
        }
        for(int j=1,k=1;j<=rcnt[i];++j){
            while(k<=rcnt[i-1] && ((rr[i-1][k]<rr[i][j]) || (rr[i-1][k]==rr[i][j] && rl[i-1][k]>rl[i][j]))) ++k;
            if(rr[i-1][k]==rr[i][j] && rl[i-1][k]==rl[i][j]) rg[i][j]=rg[i-1][k]+1,rb[i-1][k]=true;
            else rg[i][j]=1;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1,a,b,c;j<=rcnt[i];++j) if(!rb[i][j]){
            a=i-rg[i][j]+1,b=rr[i][j]-rl[i][j]+1,c=rr[i][j];
            qls[c].push_back((qry){a,i,b});
        }
    }
    for(int i=1;i<=m;++i){
        f1.init();f1.push(1);
        for(int j=2;j<=n;++j){
            int cur;
            while(!f1.ity() && a1[i][cur=f1.top()]<a1[i][j]){
                if(cur<j-1) ++ccnt[i],cl[i][ccnt[i]]=cur+1,cr[i][ccnt[i]]=j-1;
                f1.pop();
            }
            if(!f1.ity()){
                cur=f1.top();
                if(cur<j-1) ++ccnt[i],cl[i][ccnt[i]]=cur+1,cr[i][ccnt[i]]=j-1;
                if(a1[i][cur]==a1[i][j]) f1.pop();
            }
            f1.push(j);
        }
        for(int j=1,k=1;j<=ccnt[i];++j){
            while(k<=ccnt[i-1] && ((cr[i-1][k]<cr[i][j]) || (cr[i-1][k]==cr[i][j] && cl[i-1][k]>cl[i][j]))) ++k;
            if(cr[i-1][k]==cr[i][j] && cl[i-1][k]==cl[i][j]) cg[i][j]=cg[i-1][k]+1,cb[i-1][k]=true;
            else cg[i][j]=1;
        }
    }
    int ans=0;
    for(int i=1;i<=m;++i){
        int h=qls[i].size();for(int j=1;j<=h;++j) qx0[j]=qls[i][j-1].x;
        bkt_sort(qtmp,qx0,h,m);bkt_sort(ctmp,cg[i],ccnt[i],m);int k=0;
        for(int j=1;j<=h;++j){
            int t=qtmp[j];
            while(k<ccnt[i] && cg[i][ctmp[k+1]]>=qx0[t]) ++k,add(bt[cr[i][ctmp[k]]],n-cl[i][ctmp[k]]+1,1,n);
            for(int l0=qls[i][t-1].l,r0=qls[i][t-1].r,h=l0;h<=r0;++h) ans+=query(bt[h],n-l0+1);
        }
        for(int j=1;j<=k;++j) add(bt[cr[i][ctmp[j]]],n-cl[i][ctmp[j]]+1,-1,n);
    }
    // printf("%d %d %d\n",n,m,ans);
    fr::write(ans);
    fr::flush();
    return 0;
}