T了两个点,求助,如何继续优化常数
查看原帖
T了两个点,求助,如何继续优化常数
632236
gan1234楼主2023/5/2 16:39
#include<bits/stdc++.h>
#define ll long long
#define MAXN 100005
#define mod1 1000000007
#define mod2 1145141
using namespace std;
ll tt1[MAXN],tt2[MAXN];
int ksm(int x,int k,int p){
    if(p==mod1)return tt1[k];
    else return tt2[k];
}

int n,T,Q,m,ans;
int S[MAXN];
int Sh1,Sh2;
vector<int>a[MAXN];
struct Que{
    int head,tail;
    int a[MAXN];
    void push(int x){
        a[tail]=x;
        tail++;
        if(tail==MAXN)tail=0;
    }
    void pop(){
        head++;
        if(head==MAXN)head=0;
    }
    int front(){
        return a[head];
    }
    int back(){
        if(tail==0)return a[MAXN-1];
        else return a[tail-1];
    }
}Xh1,Xh2;
int lenX=1;
int R[MAXN];

void add(int k){
    int l=a[k].size();
    for(int i=0;l>i;i++){
        Xh1.push((Xh1.back()+ksm(100001,a[k][i],mod1))%mod1);
        Xh2.push((Xh2.back()+ksm(100001,a[k][i],mod2))%mod2);
        lenX++;
        if(lenX>T+1){
            Xh1.pop();
            Xh2.pop();
            lenX--;
        }
    }
}

signed main(){
    tt1[0]=tt2[0]=1;
    for(int i=1;MAXN-1>=i;i++)tt1[i]=(tt1[i-1]*100001)%mod1,tt2[i]=(tt2[i-1]*100001)%mod2;
    ios::sync_with_stdio(0);
    cin>>n>>T>>Q;
    for(int i=1;T>=i;i++)cin>>S[i];
    for(int i=1;n>=i;i++){
        int l;
        cin>>l;
        for(int j=1;l>=j;j++){
            int k;
            cin>>k;
            a[i].push_back(k);
        }
    }
    cin>>m;
    for(int i=1;m>=i;i++)cin>>R[i];
    for(int i=1;T>=i;i++){
        Sh1=(Sh1+ksm(100001,S[i],mod1))%mod1;
        Sh2=(Sh2+ksm(100001,S[i],mod2))%mod2;
    }
    Xh1.push(0);Xh2.push(0);
    if(Q>=m){
        int t=0,cnt=0;
        while(lenX<T)
            for(int i=1;m>=i;i++){
                add(R[((i-1)%m)+1]);cnt++;
                if(lenX>T){
                    if((Xh1.back()-Xh1.front()+mod1)%mod1==Sh1&&
                        (Xh2.back()-Xh2.front()+mod2)%mod2==Sh2)ans++;
                }
                if(cnt==Q){
                    cout<<ans<<endl;
                    return 0;
                }
            }
        //cout<<ans<<endl;
        Q-=cnt;
        if(Q>=m)
        for(int i=1;m>=i;i++){
            add(R[((i-1)%m)+1]);
            if(lenX>T){
                if((Xh1.back()-Xh1.front()+mod1)%mod1==Sh1&&
                    (Xh2.back()-Xh2.front()+mod2)%mod2==Sh2)t++;
            }
        }
        ans+=t*(Q/m);
    }
    Q%=m;
    for(int i=1;Q>=i;i++){
        add(R[((i-1)%m)+1]);
        if(lenX>T){
            if((Xh1.back()-Xh1.front()+mod1)%mod1==Sh1&&
                (Xh2.back()-Xh2.front()+mod2)%mod2==Sh2)ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}
2023/5/2 16:39
加载中...