[Nowcoder Multi Univerisity Training 2J]Subarray

Solution

可能作为区间端点的点个数最多为3e7
f[i]表示以第i个区间右端点为答案右端点的最大区间和
g[i]表示以第i个区间左端点为答案左端点的最大区间和
f[i]=\max(0,f[i−1]−(l[i]−r[i−1]−1))+r[i]−l[i]+1
g[i]=\max(0,g[i+1]−(l[i+1]−r[i]−1))+r[i]−l[i]+1
如果f[i]+g[i+1]≥l[i+1]−r[i]−1,说明答案的左右端点可以跨越[r[i]+1,l[i+1]−1],那么把这些合并考虑
搞完上面,问题就变成了给你若干个长度和不超过3e7的(1,−1)序列,问有多少区间和大于1
然后就好做了

[HDU6371]Chopping hands

Link

Solution

在有序表里删除点可以方便地维护中位数,所以初始全部插入然后DFS枚举删除哪些。

先按照pack大小排序可以强力加速。

然而HDOJ太慢还是T了。

然后spice的参数顺序!
a.splice(iter_a,b,iter_b)是把ba里搞!

Code

const int XN=30,XM=211;

std::vector<int> pack[XN];

int w[XM][XM],c[XN],n;
long long Ans,succs[XN],cost;

std::list<int> a,temp;
std::vector<std::list<int>::iterator> it[XM];
std::pair<std::list<int>::iterator,int> med;
std::vector<std::pair<int,std::pair<int,int>>> nums;

int cnt[XM];

int ord[XN];

void DFS(int p=1) {
    //std::cerr<<p<<','<<cost<<'\n';
    if(nums[a.back()].first*2-(cost+succs[p])<Ans)
        return;
    if(p==n+1)
        Enlarge(Ans,(a.size()&1?2*nums[(*med.first)].first
                    :nums[(*med.first)].first+nums[(*std::next(med.first))].first)-cost);
    else {
        cost+=c[ord[p]];
        DFS(p+1);
        cost-=c[ord[p]];
        if(!(p==n && cost==0)) {
            static std::pair<int,std::list<int>::iterator> stack[XM];
            static int top;
            auto backup=med;
            int pre=top;
            for(auto x : pack[ord[p]]) {
                stack[++top]={x,std::next(it[x][cnt[x]])};
                if(*it[x][cnt[x]]<*med.first)
                    med.second--;
                else if(*it[x][cnt[x]]==*med.first)
                    med.first++;
                temp.splice(temp.end(),a,it[x][cnt[x]--]);
                while(med.second<(int)(a.size()+1)/2) {
                    ++med.first;
                    ++med.second;
                }
                while(med.second>(int)(a.size()+1)/2) {
                    --med.first;
                    --med.second;
                }
            }
            DFS(p+1);
            med=backup;
            for(;top!=pre;top--)
                a.splice(stack[top].second,temp,it[stack[top].first][++cnt[stack[top].first]]);
        }
    }
}

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--) {
        //std::cerr<<T<<'\n';
        int m;std::cin>>n>>m;
        for(int i=1;i<=n;++i)
            std::cin>>c[i];
        for(int i=1;i<=m;++i)
            cnt[i]=0;
        for(int i=1;i<=n;++i) {
            int k;std::cin>>k;
            pack[i].resize(k);
            for(int j=0;j<k;++j) {
                std::cin>>pack[i][j];
                cnt[pack[i][j]]++;
            }
            ord[i]=i;
        }
        std::sort(ord+1,ord+1+n,[&](int x,int y)->bool {
            return pack[x].size()>pack[y].size();
        });
        succs[n+1]=0;
        for(int i=n;i>=1;--i)
            succs[i]=succs[i+1]+std::min(0,c[ord[i]]);
        a.clear();
        nums.clear();
        for(int i=1;i<=m;++i) {
            int k;std::cin>>k;
            it[i].resize(k+1);
            for(int j=1;j<=k;++j) {
                std::cin>>w[i][j];
                nums.push_back({w[i][j],{i,j}});
            }
        }
        std::sort(nums.begin(),nums.end());
        for(auto &p : nums)
            it[p.second.first][p.second.second]=a.insert(a.end(),a.size());

        med.first=a.begin();
        std::advance(med.first,(med.second=(a.size()+1)/2)-1);

        Ans=-1e18;
        cost=0;
        DFS();
        assert(temp.empty());
        std::cout<<Ans<<'\n';
    }
    return 0;
}

[Nowcoder Multi Univerisity Training 1C]Euclidean Distance

Link

Solution

(令x_i=\frac {a_i}m
{\displaystyle {\mathcal {L}}}=\sum (p_i-x_i)^2+\lambda(\sum p_i-1),即为求\max_\lambda\ \min_{p}\ {\displaystyle {\mathcal {L}}}(p_i\ge 0)

{\displaystyle {\mathcal {L}}}=\sum (p_i-(x_i-\lambda))^2+\sum(2x_i\lambda-\lambda^2)+2\lambda,对于每个(p_i-(x_i-\lambda))^2\ge \min(x_i-\lambda,0)^2,可以缩掉p_i了。
然后就是求\sum\min(x_i-\lambda,0)^2+\sum(2x_i\lambda-\lambda^2)-2\lambda的最大值。

Code

const int XN=1e4+11,INF=1e9;

struct Fact {
    long long p,q;

    Fact(long long x,long long y=1) {
        long long d=std::__gcd(x,y);
        p=x/d;q=y/d;
        if(q<0) {
            p=-p;
            q=-q;
        }
    }
};

bool operator <(Fact x,Fact y) {
    return __int128(x.p)*y.q-__int128(x.q)*y.p<0;
}

Fact operator -(Fact x) {
    return {-x.p,x.q};
}

Fact operator +(Fact x,Fact y) {
    return Fact({x.p*y.q+x.q*y.p,x.q*y.q});
}


Fact operator *(Fact x,Fact y) {
    return Fact({x.p*y.p,x.q*y.q});
}

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,m;
    while(std::cin>>n>>m) {
        static int a[XN];
        for(int i=1;i<=n;++i)
            std::cin>>a[i];
        std::sort(a+1,a+1+n); 
        a[0]=-INF;
        a[n+1]=INF;
        long long A=-n;
        Fact B={-2,1},C={0,1};
        for(int i=1;i<=n;++i)
            B=B+Fact(2*a[i],m);
        Fact Ans{0,1};

        auto Solve=[&](Fact L,Fact R)->Fact {
            if(A==0)
                return B*(B.p*B.q>=0?R:L)+C;
            Fact axis=-1*B*Fact(1,2*A);
            if(!(axis<L) && !(R<axis)) {
                return (4*A*C+(-B*B))*Fact(1,4*A);  
            } else {
                Fact X=axis<L?L:R;
                return A*X*X+B*X+C; 
            }
        };

        for(int i=1;i<=n+1;++i) {
            Enlarge(Ans,Solve({a[i-1],m},{a[i],m}));
            if(i!=n+1) {
                A++;
                B=B+(-2*Fact(a[i],m));
                C=C+1ll*a[i]*a[i]*Fact(1,1ll*m*m);
            }
        }
        if(Ans.q==1)
            std::cout<<Ans.p<<'\n';
        else
            std::cout<<Ans.p<<'/'<<Ans.q<<'\n';
    }
    return 0;
}

[HDU6364]Ringland

Link

读入卡的相当死。。

Code

const int XN=5e5+11;

void Work() {
    int n,l;fin>>n>>l;
    static int a[XN*3],b[XN];
    static long long sum[XN*3];
    for(int i=1;i<=n;++i) {
        fin>>a[i+n];
        a[i]=a[i+n]-l;
        a[i+2*n]=a[i+n]+l;
    }
    for(int i=1;i<=n;++i)
        fin>>b[i];
    for(int i=1;i<=3*n;++i)
        sum[i]=0;

    for(int i=1,j=1;i<=3*n;++i) {
        while(j<=std::min(n,i) && b[j]<=a[i])
            ++j;
        sum[std::max(1,i-n+1)]-=a[i];
        sum[i-j+2]+=2ll*a[i];
        sum[i+1]-=a[i];
    }

    for(int i=1,j=1;i<=n;++i) {
        sum[1]+=b[i];
        while(j<=3*n && a[j]<b[i])
            ++j;
        sum[j-i+1]-=2*b[i];
    }
    long long Ans=1e18;
    for(int i=1;i<=2*n+1;++i)
        Reduce(Ans,sum[i]+=sum[i-1]);
    printf("%lld\n",Ans);
}

int main() {
    //freopen("input","r",stdin);
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}

[HDU6368]Variance-MST

Link

Solution

题解说的很清楚了。。
核心就是如果直接删掉环上最小边再加上最大边,不能保证修改的这两条边的均值是递增的,即a < b < c < d可能有\frac {a+d}2 < \frac {b+c}2,因此必须把所有成环的边记录一下,按照两条边的均值排序后再按顺序进行删边加边操作。

Code

#include <bits/stdc++.h>

const int XN=1e5+11,XM=2e5+11,P=998244353,INF=1e9;

int Pow(long long base,int v) {
    long long res;
    for(res=1;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

struct Edge {
    int x,y,v,id;
}edges[XM];

struct LinkCutTrees {
    struct Node {
        Node *son[2],*fa;
        bool rev;

        std::pair<int,Edge*> v,min;

        Node(void*):rev(0),min(INF,0) {
            son[0]=son[1]=fa=0;
        }

        Node(std::pair<int,Edge*> const &v):rev(0),v(v),min(v) {
            son[0]=son[1]=fa=null;
        }

        void *operator new(size_t flag) {
            static Node *pool=(Node*)malloc((XN+XM)*sizeof(Node)),*mem=pool++;
            return flag?mem++:mem=pool;
        }

        int Type() {
            return fa->son[1]==this;
        }

        bool isRoot() {
            return fa->son[0]!=this && fa->son[1]!=this;
        }

        void Adopt(Node *s,int d) {
            son[d]=s;
            if(s!=null)
                s->fa=this;
        }

        void Reverse() {
            rev^=1;
            std::swap(son[0],son[1]);
        }

        void Up() {
            min=std::min(std::min(son[0]->min,son[1]->min),v);
        }

        void Down() {
            if(rev) {
                if(son[0]!=null)
                    son[0]->Reverse();
                if(son[1]!=null)
                    son[1]->Reverse();
                rev=0;
            }
        }

    };

    std::vector<Node*> node;

    static Node *null;

    LinkCutTrees():node{0} {}

    void Link(int id1,int id2) {
        Link(node[id1],node[id2]);
    }

    void Cut(int id1,int id2) {
        Cut(node[id1],node[id2]);
    }

    void Add(std::pair<int,Edge*> const &x) {
        node.push_back(new Node(x));
        if(x.second)
            x.second->id=node.size()-1;
    }

    std::pair<int,Edge*> Query(int x,int y) {
        MakeRoot(node[x]);
        Expose(node[y]);
        return node[y]->min;
    }

    Node *FindRoot(int x) {
        return FindRoot(node[x]);
    }


    static void Trans(Node *pos) {
        Node *f=pos->fa,*g=f->fa;
        f->Down();pos->Down();
        int d=pos->Type();
        if(!f->isRoot())
            g->son[f->Type()]=pos;
        pos->fa=g;
        f->Adopt(pos->son[!d],d);f->Up();
        pos->Adopt(f,!d);
    }

    static void Splay(Node *pos) {
        pos->Down();
        for(Node *fa;!pos->isRoot();Trans(pos))
            if(!(fa=pos->fa)->isRoot())
                Trans(pos->Type()==fa->Type()?fa:pos);
        pos->Up();
    }

    static void Access(Node *pos) {
        for(Node *pred=null;pos!=null;pred=pos,pos=pos->fa) {
            Splay(pos);
            pos->son[1]=pred;
            pos->Up();
        }
    }

    static void Expose(Node *pos) {
        Access(pos);
        Splay(pos);
    }

    static Node *FindRoot(Node *pos) {
        Expose(pos);
        while(pos->son[0]!=null) {
            pos->Down();
            pos=pos->son[0];
        }
        //std::cerr<<std::find(node.begin(),node.end(),pos)-node.begin()<<'\n';
        return pos;
    }

    static void MakeRoot(Node *pos) {
        Expose(pos);
        pos->Reverse();
    }

    static void Cut(Node *p1,Node *p2) {
        MakeRoot(p1);
        Expose(p2);
        assert(p2->son[0]==p1);
        p2->son[0]=p1->fa=null;
        p2->Up();
    }

    static void Link(Node *p1,Node *p2) {
        MakeRoot(p1);
        p1->fa=p2;
    }
};

LinkCutTrees::Node *LinkCutTrees::null=new LinkCutTrees::Node((void*)0);

void Work() {
    LinkCutTrees::Node::operator new(0);
    LinkCutTrees lct;
    int n,m;std::cin>>n>>m;
    for(int i=1;i<=n;++i)
        lct.Add({INF,0});
    for(int i=1;i<=m;++i)
        std::cin>>edges[i].x>>edges[i].y>>edges[i].v;

    std::sort(edges+1,edges+1+m,[](Edge const &a,Edge const &b)->bool {
        return a.v<b.v;
    });

    for(int i=1;i<=m;++i)
        lct.Add({edges[i].v,edges+i});//指针会变!
    std::vector<std::tuple<int,int,int>> tg;//维护所有切换 0 时间 1 系数 2 delta
    for(int i=1;i<=m;++i) {
        int x=edges[i].x,y=edges[i].y,v=edges[i].v,id=edges[i].id;
        if(lct.FindRoot(x)==lct.FindRoot(y)) {
            auto me=lct.Query(x,y);
            lct.Cut(me.second->x,me.second->id);
            lct.Cut(me.second->y,me.second->id);
            tg.emplace_back(me.first+v,-1,me.first);
            tg.emplace_back(me.first+v,1,v);
        } else
            tg.emplace_back(-INF,1,v);
        lct.Link(x,id);
        lct.Link(y,id);
    }

    std::sort(tg.begin(),tg.end());
    //E(X^2)-E^2(x)
    std::pair<long long,long long> optm={(long long)1e18,0ll},cur{0ll,0ll};
    int cnt=0;
    for(auto &tgs : tg) {
        int t,op,d;
        std::tie(t,op,d)=tgs;

        cur.first+=1ll*op*d*d;
        cur.second+=op*d;

        auto X=[&](std::pair<long long,long long> const &x)->__int128 {//long long,int??
            return __int128(x.first)*(n-1)-__int128(x.second)*x.second;
        };
        if((cnt+=op)==n-1 && X(optm)>X(cur)) {
            optm=cur;
        }
    }
    int inv=Pow(n-1,P-2),a=optm.first%P*inv%P,b=optm.second%P*inv%P,
        Ans=(a-1ll*b*b%P)%P;
    if(Ans<0)
        Ans+=P;
    std::cout<<Ans<<'\n';
}

int main() {
    //freopen("in","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

[HDU6372]Lucas

Link

Solution

根据Lucas Theorem,\binom{n}{m}\mod p=0\Leftrightarrow np进制表示的每一位都\ge mp进制表示的对应位。
对于题目中的np进制数字iHMBB[i][j]=1j的个数就是满足如上条件的j的个数,HMBB的一次方中的1的个数就是p^n-1\ge i\ge j(i,j)数(此处的\ge指每位对应\ge
同理,HMBB^k1的个数就是p^n-1\ge a_1\ge a_2\ge…\ge a_{k+1}的个数。
而每一位是独立的,可以单独计算一位的然后求个幂。
而一位的答案就是以p-1为开头,长度为k+2的不升序列的长度。用组合数计算,可以假设开头再放上一个0,那么就是开头为0,结尾p-1,中间k+1个数的非降序列数。除去开头,后面k+2个数每个数字相对于前面的数字的增量\ge 0,且总的增量为p-1,因此对于增量列出方程

\left\{\begin{aligned}
\sum \Delta_i=&p-1\\
\Delta_i \ge&0
\end{aligned}\right.

方案数为\binom{(p-1)+(k+1)}{k+1}
最终要计算的就是

\begin{aligned}
&\sum_{i=1}^{k}\sum_{j=1}^n \binom{p+i}{i+1}^j
\end{aligned}

Code

#include <bits/stdc++.h>

const int N=2e6,XN=N+11,P=1e9+7;

void M(int &x) {
    ((x>=P) && (x-=P)) || ((x<0) && (x+=P));
}

int Pow(long long base,int v,int P) {
    long long res=1;
    for(;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

int prime[XN],pcnt;
void Prep() {
    static bool notPrime[XN];
    for(int i=2;i<=N;++i) {
        if(!notPrime[i]) {
            prime[++pcnt]=i;
        }
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0) {
                break;
            } 
        }
    }
}

int fact[XN],ifact[XN];
int C(int n,int m) {
    return n>=m?1ll*fact[n]*ifact[m]%P*ifact[n-m]%P:0;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);std::cout.tie(0);

//  freopen("input","r",stdin);

    fact[0]=1;
    for(int i=1;i<=N;++i)
        fact[i]=1ll*fact[i-1]*i%P;
    ifact[N]=Pow(fact[N],P-2,P);
    for(int i=N-1;i>=0;--i)
        ifact[i]=1ll*ifact[i+1]*(i+1)%P;

    Prep();
    int T;std::cin>>T;
    while(T--) {
        int c,n,k;std::cin>>c>>n>>k;
        int p=prime[c];
        int Ans=0;
        for(int i=1;i<=k;++i) {
            int v=C(p+i,i+1);
            M(Ans+=v==1?v*n%P:1ll*v*(1ll-Pow(v,n,P))%P*Pow(1-v,P-2,P)%P);
        }
        std::cout<<Ans<<'\n';
    }
    return 0;
}

[Gym 102114C]Call It What You Want

Link

给的\Phi_d的复数形式的公式是骗人玩的…很好我又被骗了…

Solution

x^n-1=\prod_{d|n}\Phi_d(x)\Leftrightarrow \Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(\frac nd)}
\Phi_d(x)的最高次项为\varphi(d),所以在模x^{\varphi(d)+1}下求出\Phi_n(x)然后再求答案,单次询问的复杂度为\mathcal{O}(\sum_{d | n}{2^{\omega(d)}\varphi(d)}) = \mathcal{O}(2^6 n)

Code

#include <bits/stdc++.h>

const int N=1e5,XN=N+11;

int prime[XN],pcnt,phi[XN];
std::vector<int> pdv[XN];

void Prep() {
    static bool notPrime[XN];
    phi[1]=1;
    for(int i=2;i<=N;++i) {
        if(!notPrime[i]) {
            prime[++pcnt]=i;
            phi[i]=i-1;
            pdv[i]={i};
        }
        for(int j=1;j<=pcnt && i*prime[j]<=N;++j) {
            notPrime[i*prime[j]]=1;
            pdv[i*prime[j]]=pdv[i];
            if(i%prime[j]==0) {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            } else {
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
                pdv[i*prime[j]].push_back(prime[j]);
            }
        }
    }
}

//P只有复根 无法因式分解

std::vector<int> FindDivisors(int x) {
    std::vector<int> res={};
    for(int d=1;d*d<=x;++d)
        if(x%d==0) {
            res.push_back(d);
            if(x!=d*d)
                res.push_back(x/d);
        }
    return res;
}

std::vector<int> Calc(int n) {
    std::vector<int> posi,nega;
    for(int S=0;S<(1<<pdv[n].size());++S) {
        int d=1;
        for(size_t i=0;i<pdv[n].size();++i)
            if(S>>i&1)
                d*=pdv[n][i];
        (__builtin_popcount(S)&1?nega:posi).push_back(n/d);
    }
    std::vector<int> P{1};
    for(auto d : posi) {
        //P*=(x^d-1)
        std::vector<int> T(P.size()+d,0);
        for(size_t i=0;i<P.size();++i) {
            T[i]-=P[i];
            T[i+d]+=P[i];
        }
        P=T;
    }
    for(auto d : nega) {
        //P/=(x^d-1)
        std::vector<int> T(P.size()-d,0);
        for(int i=T.size()-1;i>=0;--i) {
            T[i]=P[i+d];
            P[i]+=P[i+d];
            P[i+d]=0;
        }
        P=T;
    }
    return P;
}

void Work() {
    int n;std::cin>>n;
    auto divisor=FindDivisors(n);
    std::vector<std::vector<int>> Ans;
    for(int d : divisor)
        Ans.push_back(Calc(d));
    std::sort(Ans.begin(),Ans.end(),[](auto const &a,auto const &b)->bool {
        if(a.size()!=b.size())
            return a.size()<b.size();
        else
            for(int i=a.size()-1;i>=0;--i)
                if(a[i]!=b[i])
                    return a[i]<b[i];
            assert(0);
    });
    for(auto &v : Ans) {
        std::cout<<'(';
        for(int i=v.size()-1;i>=0;--i)
            if(v[i]) {
                if(v[i]>0 && i!=(int)v.size()-1)
                    std::cout<<'+';
                else if(v[i]<0)
                    std::cout<<'-';
                if(abs(v[i])!=1 || i==0)
                    std::cout<<abs(v[i]);
                if(i) {
                    std::cout<<'x';
                    if(i>=2)
                        std::cout<<'^'<<i;
                }
            }
        std::cout<<')';
    }
    std::cout<<'\n';
}

int main() {
    //freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    Prep();
    int T;std::cin>>T;
    while(T--)
        Work();
    return 0;
}

[Gym 102114F]Fireflies

Link

第一步的题意转化就并没想到(根本没往子集的方向去想)
Consider all the lattice points in a hypercube \ { (x_1,x_2,…,x_n)|0\le x_i < p_i \ } . Find a maximal subset such that there are no two points (x_1,x_2,…,x_n),(y_1,y_2,…,y_n) meeting the condition x_i≤y_i for all i. Report its size modulo 10^9+7.

Solution

对于任意集合S,如果它的一个子集集合F满足\forall X,Y\in F,X\not\subset Y,Y\not\subset X,则我们把这样的子集F称为Sperner族。
一个集合的极大Sperner族的元素个数为\binom{|S|}{\lfloor\frac {|S|}{2}\rfloor},是为Sperner定理。达到这个数目只需要取出所有\lfloor\frac {|S|}{2}\rfloor元子集。
Sperner定理可以直接用于解决问题在p_i=2时的情形,将某一位坐标的0,1转化为在集合中的选与不选。

Sperner 定理的一种推广可以给出本问题的答案:选择满足所有坐标之和等于 M = \lfloor \frac{1}{2} \sum_{i = 1}^{n}(p_i-1) \rfloor的位置即可达到最大的数量。

最终问题变成了,求\sum x_i=M,x_i\in[0,p_i)的解数,也就是\sum x_i=M+n,x_i\in[1,p_i]的解数。

由容斥原理,答案为\sum_{T\subset S}(-1)^{|T|}\binom{M-1-\sum_{i\subset T}p_i}{n-1}

使用meet-in-middle策略。
由于\binom{a-x}{b}可以写成一个b次的多项式,而n-1又很小,因此可以处理出左侧集合的关于右侧集合选出元素之和x对答案贡献的多项式的前缀和,枚举右侧集合的元素,然后利用左侧集合多项式的前缀和来处理答案。

\begin{aligned}
&\sum_{T\subset S}(-1)^{|T|}\binom{M-1-\sum_{i\subset T}p_i}{n-1}\\
=&\sum_{T_1\in S_1}\sum_{T_0\in S_0}(-1)^{|T_0|+|T_1|}\binom{M-1-\sum_{i\in T_0}p_i-\sum_{i\in T_1}p_i}{n-1}\\
=&\sum_{T_1\in S_1}(-1)^{|T_1|}\sum_{T_0\in S_0}(-1)^{|T_0|}F(\sum_{i\in T_1}p_i)\\
\end{aligned}

Code

#include <bits/stdc++.h>

const int XN=40,P=1e9+7;

int Pow(long long base,int v) {
    long long res;
    for(res=1;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

std::vector<int> Conv(std::vector<int> const &a,std::vector<int> const &b) {
    std::vector<int> c(a.size()+b.size()-1,0);
    for(size_t i=0;i<a.size();++i)
        for(size_t j=0;j<b.size();++j)
            (c[i+j]+=1ll*a[i]*b[j]%P)%=P;
    return c;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    freopen("input","r",stdin);

    int ifact[XN]={1};
    for(int i=1;i<XN;++i)
        ifact[i]=1ll*ifact[i-1]*Pow(i,P-2)%P;

    int T;std::cin>>T;

    while(T--) {
        int n;std::cin>>n;
        std::vector<int> p(n),s0,s1;
        long long M=0;
        for(int i=0;i<n;++i) {
            std::cin>>p[i];
            M+=p[i]-1;
            (i<(n+1)/2?s0:s1).push_back(p[i]);
        }
        (M/=2)+=n;
        std::vector<std::pair<long long,int>> v0;
        for(int S=0;S<(1<<s0.size());++S) {
            long long sum=0;
            for(size_t i=0;i<s0.size();++i)
                if(S>>i&1)
                    sum+=s0[i];
            v0.push_back({sum,__builtin_popcount(S)&1?-1:1});
        }
        std::sort(v0.begin(),v0.end());
        std::vector<std::vector<int>> f(v0.size(),std::vector<int>(n,0));
        for(size_t i=0;i<v0.size();++i) {
            std::vector<int> p{1};
            for(int j=0;j<n-1;++j)
                p=Conv(p,{(int)((M-1-v0[i].first-j)%P),-1});//XXX
            for(int &x : p)
                x=1ll*x*ifact[n-1]*v0[i].second%P;
            for(int j=0;j<n;++j)
                f[i][j]=((i?f[i-1][j]:0)+p[j])%P;
        }
        //需要枚举右集合的状态 一下子统计上所有左集合中和+和<=M-1的状态的
        //(-1)^J0 * (-1)^J1*F(X0+X1)
        int Ans=0;
        for(int S=0;S<(1<<s1.size());++S) {
            long long sum=0;
            for(size_t i=0;i<s1.size();++i)
                if(S>>i&1)
                    sum+=s1[i];
            if(sum<=M-1) {
                int p=std::upper_bound(v0.begin(),v0.end(),std::make_pair(M-1-sum,1))-v0.begin()-1,
                    c=__builtin_popcount(S)&1?-1:1;
                int res=0;
                sum%=P;
                for(int i=n-1;i>=0;--i)
                    res=(res*sum+f[p][i])%P;
                (Ans+=c*res)%=P;
            }
        }
        if(Ans<0)
            Ans+=P;
        std::cout<<Ans<<'\n';
    }
    return 0;
}

[LOJ2720][NOI2018]君の名は。

Link

Solution

首先求出TS的对应区间内每个前缀能匹配到的最长长度,用后缀自动机维护right集合比较好做。
然后将T反转求一下后缀数组,每个后缀(原串的前缀)给答案带来贡献就是n-sa[i]+1-std::max(height[i],match[sa[i]])

Code

#include <bits/stdc++.h>

template <class T>
bool Enlarge(T &a,T const &b) {
    return a<b?a=b,1:0;
}

const int XN=5e5+11;

struct SegTree {
    static int n;

    struct Node {
        Node *son[2];
        int sum;

        Node(int sum):sum(sum) {
            son[0]=son[1]=0;
        }

        void Up() {
            sum=0;
            for(int d=0;d<2;++d)
                if(son[d])
                    sum+=son[d]->sum;
        }
    }*root;

    SegTree(Node *root=0):root(root) {}

    void Add(int goal,int v) {
        std::function<void(Node*&,int,int)> Add=[&](Node *&pos,int L,int R) {
            pos=pos?new Node(*pos):new Node(0);
            if(L==R)
                pos->sum+=v;
            else {
                int M=(L+R)/2;
                goal<=M?Add(pos->son[0],L,M)
                       :Add(pos->son[1],M+1,R);     
                pos->Up();
            }
        };

        Add(root,1,n);
    }

    int Sum(int l,int r) {
        int res=0;

        std::function<void(Node*,int,int)> GetSum=[&](Node *pos,int L,int R) {
            if(!pos)
                return;
            if(l<=L && R<=r)
                res+=pos->sum;
            else {
                int M=(L+R)/2;
                if(l<=M)
                    GetSum(pos->son[0],L,M);
                if(M+1<=r)
                    GetSum(pos->son[1],M+1,R);
            }
        };

        GetSum(root,1,n);
        return res;
    }

    friend SegTree Merge(SegTree const &x,SegTree const &y) {
        std::function<Node*(Node*,Node*)> Merge=[&](Node *x,Node *y)->Node* {
            if(!x || !y)
                return x?x:y;
            else {
                Node *pos=new Node(0);
                pos->son[0]=Merge(x->son[0],y->son[0]);
                pos->son[1]=Merge(x->son[1],y->son[1]);
                pos->Up();
                return pos;
            }
        };

        return SegTree(Merge(x.root,y.root));
    }
};

int SegTree::n;

struct SuffixAutomata {
    struct Node {
        Node *son[26];
        Node *par;
        int deg,maxRight;
        SegTree T;

        Node(int maxRight=0):par(0),deg(0),maxRight(maxRight) {
            memset(son,0,sizeof(son));
        }

        void *operator new(size_t) {
            static Node *pool=(Node*)malloc(XN*2*sizeof(Node)),*mem=pool;
            nodes.push_back(mem);
            return mem++;
        }
    }*root,*last;

    static std::vector<Node*> nodes;

    std::vector<Node*> loc;

    SuffixAutomata():root(new Node),last(root) {}

    void Extend(int x) {
        Node *p=last,*nx=new Node(last->maxRight+1);
        for(;p && !p->son[x];p->son[x]=nx,p=p->par);
        if(p==0) {
            nx->par=root;
        } else {
            Node *ox=p->son[x];
            if(p->maxRight+1==ox->maxRight) {
                nx->par=ox;
            } else {
                Node *o=new Node(*ox);
                o->maxRight=p->maxRight+1;
                ox->par=nx->par=o;
                for(;p && p->son[x]==ox;p->son[x]=o,p=p->par);
            }
        }
        loc.push_back(last=nx);
    }

    void Solve() {
        SegTree::n=loc.size();
        for(size_t i=0;i<loc.size();++i)
            loc[i]->T.Add(i+1,1);
        for(auto p : nodes)
            if(p->par)
                p->par->deg++;
        std::queue<Node*> Q;
        for(auto p : nodes)
            if(!p->deg)
                Q.push(p);
        while(!Q.empty()) {
            Node *p=Q.front();Q.pop();
            if(p->par) {
                p->par->T=Merge(p->par->T,p->T);
                if(--p->par->deg==0)
                    Q.push(p->par);
            }
        }
    }

    std::vector<int> Match(int l,int r,std::string const &s) {
        Node *pos=root;
        std::vector<int> res;
        int len=0;
        for(char c : s) {
            int x=c-'a';
            while(pos!=root && !pos->son[x])
                len=(pos=pos->par)->maxRight;
            if(pos->son[x]) {
                ++len;
                pos=pos->son[x];
            }
            while(len && !pos->T.Sum(l+len-1,r))
                if(--len==pos->par->maxRight)
                    pos=pos->par;
            res.push_back(len);
        }
        return res;
    }
};

std::vector<SuffixAutomata::Node*> SuffixAutomata::nodes;

std::vector<int> SAIS(std::vector<int> &s,int sig) {
    enum Type { L,S };

    int n=s.size();
    std::vector<Type> type(n);
    std::vector<int> sa(n),cnt(sig),lp(sig),sp(sig);

    auto LMS=[&](int x) {
        return x>0 && type[x]==S && type[x-1]==L;
    };

    auto Induce=[&]() {
        for(int i=0;i<sig;++i)
            lp[i]=i?cnt[i-1]:0;
        for(int i=0;i<n;++i)
            if(sa[i]>0 && type[sa[i]-1]==L)
                sa[lp[s[sa[i]-1]]++]=sa[i]-1;
        for(int i=0;i<sig;++i)
            sp[i]=cnt[i]-1;
        for(int i=n-1;i>0;--i)
            if(sa[i]>0 && type[sa[i]-1]==S)
                sa[sp[s[sa[i]-1]]--]=sa[i]-1;
    };

    type[n-1]=S;
    for(int i=n-2;i>=0;--i)
        type[i]=s[i]<s[i+1] || (s[i]==s[i+1] && type[i+1]==S)?S:L;
    for(int x : s)
        cnt[x]++;
    for(int i=1;i<sig;++i)
        cnt[i]+=cnt[i-1];
    std::vector<int> lms;
    for(int i=0;i<n;++i)
        if(LMS(i))
            lms.push_back(i);
    for(int i=0;i<sig;++i)
        sp[i]=cnt[i]-1;
    std::fill(sa.begin(),sa.end(),-1);
    for(int i : lms)
        sa[sp[s[i]]--]=i;
    Induce();
    std::vector<int> id(n,-1);
    int c=0;
    for(int i=0,last=-1;i<n;++i)
        if(LMS(sa[i])) {
            auto Equal=[&](int x,int y)->bool {
                do if(s[x++]!=s[y++]) return 0;
                while(!LMS(x) && !LMS(y));
                return s[x]==s[y];
            };
            id[sa[i]]=last!=-1 && Equal(sa[i],last)?c-1:c++;
            last=sa[i];
        }

    std::vector<int> s1;
    for(int i=0;i<n;++i)
        if(id[i]!=-1)
            s1.push_back(id[i]);
    std::vector<int> sa1(c);
    if(c==(int)lms.size())
        for(int i=0;i<c;++i)
            sa1[s1[i]]=i;
    else
        sa1=SAIS(s1,c);
    for(int i=0;i<sig;++i)
        sp[i]=cnt[i]-1;
    std::fill(sa.begin(),sa.end(),-1);
    for(int i=lms.size()-1;i>=0;--i)
        sa[sp[s[lms[sa1[i]]]]--]=lms[sa1[i]];
    Induce();
    return sa;
}

long long Calc(std::string const &s,std::vector<int> &match) {
    int n=s.size();

    std::vector<int> a(s.size());
    for(int i=0;i<n;++i)
        a[i]=s[i]-'a'+1;
    std::reverse(a.begin(),a.end());
    match.push_back(-1);
    std::reverse(match.begin(),match.end());
    a.push_back(0);

    auto sa=SAIS(a,26+1);
    a.insert(a.begin(),-1);
    std::vector<int> rank(n+1),height(n+1);
    for(int i=1;i<=n;++i)
        rank[++sa[i]]=i;
    for(int i=1,len=0;i<=n;++i)
        if(rank[i]!=1) {
            int j=sa[rank[i]-1];
            while(a[i+len]==a[j+len]) ++len;
            height[rank[i]]=len;
            if(len) len--;
        }
    long long res=0;
    for(int i=1;i<=n;++i)
        res+=n-sa[i]+1-std::max(height[i],match[sa[i]]);

    return res;
}

int main() {
    freopen("name.in","r",stdin);
    freopen("name.out","w",stdout);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    SuffixAutomata sam;
    std::string s;
    std::cin>>s;
    for(char c : s)
        sam.Extend(c-'a');
    sam.Solve();
    int q;std::cin>>q;
    while(q--) {
        std::string t;
        int l,r;
        std::cin>>t>>l>>r;
        auto v=sam.Match(l,r,t);
        long long Ans=Calc(t,v);
        std::cout<<Ans<<'\n';
    }
    return 0;
}