#606831 (C++17) No.1354 Sambo's Treasure

提出ソース
結果

問題	No.1354 Sambo's Treasure
ユーザー	penguinman
提出日時	2021-01-17 16:40:40
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	20,626 bytes
コンパイル時間	3,928 ms
コンパイル使用メモリ	257,604 KB
実行使用メモリ	101,768 KB
最終ジャッジ日時	2024-05-07 05:54:50
合計ジャッジ時間	7,842 ms
ジャッジサーバーID （参考情報）	judge2 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	18 ms 20,352 KB
testcase_01	AC	19 ms 14,848 KB
testcase_02	AC	20 ms 14,940 KB
testcase_03	AC	19 ms 14,976 KB
testcase_04	AC	20 ms 14,848 KB
testcase_05	AC	19 ms 14,944 KB
testcase_06	AC	19 ms 14,848 KB
testcase_07	AC	21 ms 14,848 KB
testcase_08	AC	19 ms 14,936 KB
testcase_09	AC	19 ms 14,848 KB
testcase_10	AC	20 ms 14,848 KB
testcase_11	AC	19 ms 14,976 KB
testcase_12	AC	20 ms 14,920 KB
testcase_13	AC	20 ms 14,976 KB
testcase_14	AC	20 ms 14,976 KB
testcase_15	AC	20 ms 14,848 KB
testcase_16	AC	21 ms 14,976 KB
testcase_17	AC	20 ms 14,976 KB
testcase_18	AC	20 ms 14,976 KB
testcase_19	AC	20 ms 14,848 KB
testcase_20	AC	19 ms 14,848 KB
testcase_21	AC	19 ms 14,940 KB
testcase_22	AC	19 ms 14,776 KB
testcase_23	TLE	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-
testcase_48	--	-
testcase_49	--	-
testcase_50	--	-
testcase_51	--	-
testcase_52	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-
testcase_56	--	-
testcase_57	--	-
testcase_58	--	-
testcase_59	--	-
testcase_60	--	-
testcase_61	--	-
testcase_62	--	-
testcase_63	--	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include<bits/stdc++.h>
//using namespace std;
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define per(i,j,n) for(int i=(int)(j);(int)(n)<=i;i--)
#define ALL(a) (a).begin(),(a).end()
#define pb emplace_back
#define mp std::make_pair
//#define endl "\n"
//
using std::endl;
using std::cin;
using std::cout;
using ll=long long;
using std::vector;
using std::string;
using std::upper_bound;
using std::lower_bound;
using vi=vector<ll>;
using vii=vector<vi>;
using pii=std::pair<ll,ll>;
//constexpr ll MOD=1e9+7; constexpr ll root=0;
//
constexpr ll MOD=998244353; constexpr ll root=3;
//constexpr ll MOD=924844033; constexpr ll root=5;
//constexpr ll MOD=10000000; constexpr ll root=0;
//constexpr ll MOD=1e4; constexpr ll root=0;
//constexpr ll MOD=1e5; constexpr ll root=0;
constexpr ll MAX=5e5;
constexpr ll inf=(1ll<<60);
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
template<typename T>
struct Segment_tree{
    ll N;
    T mem;
    vector<T> node;
    Segment_tree(vector<T> &X,T m):mem(m){
        ll sz=X.size();
        N=1;
        while(N<sz) N*=2;
        node.resize(2*N-1,mem);
        rep(i,0,sz) node[N-1+i]=X[i];
        per(i,N-2,0){
            node[i]=Compare(node[i*2+1],node[i*2+2]);
        }
    }
    T Compare(T &A,T &B){
        return std::min(A,B);
    }
    void update(ll X,T val){
        X+=N-1;
        node[X]=val;
        while(X>0){
            X=(X-1)/2;
            node[X]=Compare(node[X*2+1],node[X*2+2]);
        }
    }
    T Query(ll a,ll b,ll now=0,ll l=0,ll r=-1){ //[a,b),[l,r)
        if(r<0) r=N;
        if(r<=a||b<=l) return mem;
        if(a<=l&&r<=b) return node[now];
        auto vl=Query(a,b,now*2+1,l,(l+r)/2),vr=Query(a,b,now*2+2,(l+r)/2,r);
        return Compare(vl,vr);
    }
    ll lower_bound(ll left,ll right,T val,ll now=0,ll l=0,ll r=-1){
        if(r<0) r=N;
        if(node[now]<val||l>=right||left>=r) return r;
        else if(now>=N-1) return l;
        ll vl=lower_bound(left,right,val,now*2+1,l,(l+r)/2);
        if(vl==(l+r)/2) return lower_bound(left,right,val,now*2+2,(l+r)/2,r);
        return vl;
    }
};
template<typename T>
struct lazy_Segment_tree{
    int N;
    vector<T> node,lazy;
    T INF;
    vector<bool> flag;
    lazy_Segment_tree(vector<T> X,T Y):INF(Y){
        N=1;
        while(X.size()>N) N*=2;
        node.resize(2*N-1,Y);
        lazy.resize(2*N-1);
        flag.resize(2*N-1);
        rep(i,0,X.size()) node[i+N-1]=X[i];
        per(i,N-2,0) node[i]=compare(node[i*2+1],node[i*2+2]);
    }
    T compare(T X,T Y){
        return std::max(X,Y);
    }
    T plus(T X,int l,int r){
        return X;
    }
    void eval(int now,int l,int r){
        if(flag[now]){
            if(r-l>1){
                flag[now*2+1]=flag[now*2+2]=1;
                lazy[now*2+1]=lazy[now*2+2]=lazy[now];
            }
            node[now]=lazy[now];
            flag[now]=0;
        }
    }
    void update(int a,int b,T add,int now=0,int l=0,int r=-1){
        if(r<0) r=N;
        eval(now,l,r);
        if(b<=l||r<=a) return;
        if(a<=l&&r<=b){
            lazy[now]=add;
            flag[now]=1;
            eval(now,l,r);
        }
        else{
            update(a,b,add,now*2+1,l,(r+l)/2);
            update(a,b,add,now*2+2,(r+l)/2,r);
            node[now]=compare(node[now*2+1],node[now*2+2]);
        }
    }
    T Query(int a,int b,int now=0,int l=0,int r=-1){
        if(r<0) r=N;
        eval(now,l,r);
        if(b<=l||r<=a) return INF;
        if(a<=l&&r<=b) return node[now];
        return compare(Query(a,b,now*2+1,l,(r+l)/2),Query(a,b,now*2+2,(r+l)/2,r));
    }
    ll lower_bound(ll left,ll right,T val,ll now=0,ll l=0,ll r=-1){
        eval(now,l,r);
        if(r<0) r=N;
        if(node[now]<val||l>=right||left>=r) return r;
        else if(now>=N-1) return l;
        ll vl=lower_bound(left,right,val,now*2+1,l,(l+r)/2);
        if(vl==(l+r)/2) return lower_bound(left,right,val,now*2+2,(l+r)/2,r);
        return vl;
    }
};
struct Binary_indexed_tree{
    int N;
    vi bit;
    Binary_indexed_tree(int n):N(n){
        bit.resize(N+1,0);
    }
    void add(int x,ll a){
        x++;
        for(x;x<=N;x+=(x&-x)) bit[x]+=a;
    }
    ll sum(int x){
        x++;
        ll ret=0;
        for(x;x>0;x-=(x&-x)) ret+=bit[x];
        return ret;
    }
    ll lower_bound(ll X){
        if(sum(N)<X) return -1;
        ll ret=0,memo=1,sum=0;
        while(memo*2<=N) memo*=2;
        while(memo>0){
            if(memo+ret<=N&&sum+bit[memo+ret]<X){
                sum+=bit[memo+ret];
                ret+=memo;
            }
            memo/=2;
        }
        return ret;
    }
};
struct Union_Find{
    ll N;
    vi par;
    vi siz;
    Union_Find(int n):N(n){
        par.resize(N);
        siz.resize(N,1);
        rep(i,0,N) par[i]=i;
    }
    ll root(ll X){
        if(par[X]==X) return X;
        return par[X]=root(par[X]);
    }
    bool same(ll X,ll Y){
        return root(X)==root(Y);
    }
    void unite(ll X,ll Y){
        X=root(X);
        Y=root(Y);
        if(X==Y) return;
        if(siz[Y]<siz[X]) std::swap(X,Y);
        par[X]=Y;
        siz[Y]+=siz[X];
        siz[X]=0;
    }
    ll size(ll X){
        return siz[root(X)];
    }
};
struct Strongly_Connected_Components{
    ll N,M;
    vii edge,ver;
    vi ind;
    Strongly_Connected_Components(vii e){
        ll n=e.size();
        ll m=0;
        vii revedge(n);
        ind.resize(n);
        rep(i,0,n){
            m+=e[i].size();
            for(auto p:e[i]) revedge[p].pb(i);
        }
        vi num(n,-1),po(n);
        vector<bool> seen(n);
        ll cnt=0;
        rep(i,0,n){
            if(num[i]==-1){
                dfs(i,e,num,cnt);
            }
        }
        rep(i,0,n) po[num[i]]=i;
        per(i,n-1,0){
            ll X=po[i];
            if(!seen[X]){
                std::queue<ll> que;
                vi v;
                que.push(X);
                seen[X]=1;
                while(!que.empty()){
                    ll now=que.front(); que.pop();
                    v.pb(now);
                    ind[now]=ver.size();
                    for(auto p:revedge[now]){
                        if(!seen[p]){
                            seen[p]=1;
                            que.push(p);
                        }
                    }
                }
                ver.pb(v);
            }
        }
        N=ver.size();
        M=0;
        edge.resize(N);
        rep(i,0,n){
            for(auto p:e[i]){
                if(ind[i]==ind[p]) continue;
                M++;
                edge[ind[i]].pb(ind[p]);
            }
        }
    }
    void dfs(ll now,vii &e,vi &num,ll &cnt){
        num[now]=0;
        for(auto next:e[now]){
            if(num[next]==-1){
                dfs(next,e,num,cnt);
            }
        }
        num[now]=cnt++;
    }
};
struct Directed_Gragh{
    ll N,M;
    vii edge;
    Directed_Gragh(vii e):edge(e){
        N=edge.size();
        rep(i,0,N) M+=edge[i].size();
    }
    vi sort(){
        vi ret;
        vi cnt(N);
        rep(i,0,N){
            for(auto p:edge[i]) cnt[p]++;
        }
        std::queue<ll> que;
        rep(i,0,N){
            if(cnt[i]==0) que.push(i);
        }
        while(!que.empty()){
            ll now=que.front(); que.pop();
            ret.pb(now);
            for(auto next:edge[now]){
                cnt[next]--;
                if(cnt[next]==0) que.push(next);
            }
        }
        return ret;
    }
};
struct Tree{
    int N;
    vii dp;
    vi par;
    vi dist;
    vi subtree;
    vii edge;
    Tree(vii E):edge(E){
        N=edge.size();
        dp.resize(N);
        par.resize(N);
        dist.resize(N,-1);
        for(int i=0;i<N;i++) dp[i].resize(20);
        dist[0]=dp[0][0]=0;
        std::queue<int> que;
        que.push(0);
        while(!que.empty()){
            int now=que.front(); que.pop();
            for(int i=0;i<edge[now].size();i++){
                int next=edge[now][i];
                if(dist[next]==-1){
                    dist[next]=dist[now]+1;
                    que.push(next);
                    par[next]=now;
                    dp[next][0]=now;
                }
            }
        }
        for(int i=1;i<20;i++){
            for(int j=0;j<N;j++) dp[j][i]=dp[dp[j][i-1]][i-1];
        }
    }
    int LCA(int X,int Y){
        if(dist[X]<dist[Y]) std::swap(X,Y);
        {
            int Z=dist[X]-dist[Y];
            int i=0;
            while(Z){
                if(Z&1) X=dp[X][i];
                i++;
                Z>>=1;
            }
        }
        if(X==Y) return X;
        for(int i=19;i>=0;i--){
            if(dp[X][i]!=dp[Y][i]){
                X=dp[X][i];
                Y=dp[Y][i];
            }
        }
        return dp[X][0];
    }
    void Subtree(){
        subtree.resize(N,-1);
        dfs(0);
    }
    void dfs(ll now){
        subtree[now]=1;
        for(auto next:edge[now]){
            if(subtree[next]==-1){
                dfs(next);
                subtree[now]+=subtree[next];
            }
        }
    }
};
template<typename T>
struct max_flow{
    struct Edge{
        int to;
        T cap;
        int rev;
    };
    int N;
    vector<vector<Edge>> edge;
    vector<int> dist,itr;
    max_flow(vii e,vii w){
        N=e.size();
        edge.resize(N);
        rep(i,0,N){
            rep(j,0,e[i].size()){
                edge[i].pb((Edge){(int)e[i][j],(T)w[i][j],(int)edge[e[i][j]].size()});
                edge[e[i][j]].pb((Edge){i,0,(int)edge[i].size()-1});
            }
        }
    }
    void add_edge(int from,int to,T cap){
        edge[from].pb((Edge){to,cap,(int)edge[to].size()});
        edge[to].pb((Edge){from,0,(int)edge[from].size()-1});
    }
    void bfs(int s){
        dist.assign(N,-1);
        std::queue<int> que;
        dist[s]=0;
        que.push(s);
        while(!que.empty()){
            int now=que.front(); que.pop();
            for(auto p:edge[now]){
                int next=p.to;
                if(p.cap>0&&dist[next]<0){
                    dist[next]=dist[now]+1;
                    que.push(next);
                }
            }
        }
    }
    T dfs(int now,int t,T f){
        if(now==t) return f;
        for(;itr[now]<edge[now].size();itr[now]++){
            Edge& p=edge[now][itr[now]];
            if(p.cap>0&&dist[now]<dist[p.to]){
                T mem=dfs(p.to,t,std::min(f,p.cap));
                if(mem>0){
                    p.cap-=mem;
                    edge[p.to][p.rev].cap+=mem;
                    return mem;
                }
            }
        }
        return 0;
    }
    T Query(int s,int t){
        T ret=0;
        while(1){
            bfs(s);
            if(dist[t]<0) break;
            itr.assign(N,0);
            while(1){
                int mem=dfs(s,t,(1<<30));
                if(mem<=0) break;
                ret+=mem;
            }
        }
        return ret;
    }
};
struct min_cost_flow{
    struct Edge{
        int to,cap,rev;
        ll cost;
    };
    int N;
    vector<vector<Edge>> edge;
    vector<ll> dist,h;
    void add_edge(int from,int to,int cap,ll cost){
        edge[from].pb((Edge){to,cap,(int)edge[to].size(),cost});
        edge[to].pb((Edge){from,0,(int)edge[from].size()-1,-cost});
    }
    min_cost_flow(vii e,vii m,vii w){
        N=e.size();
        edge.resize(N);
        rep(i,0,N){
            rep(j,0,e[i].size()){
                add_edge(i,e[i][j],m[i][j],w[i][j]);
            }
        }
    }
    void potential(){
        h.assign(N,0);
        vector<vector<int>> edge2(N);
        vii weight(N);
        vector<int> cnt(N);
        rep(i,0,N){
            for(auto e:edge[i]){
                if(e.cap>0&&e.cost<0){
                    edge2[i].pb(e.to);
                    weight[i].pb(-e.cost);
                    cnt[e.to]++;
                }
            }
        }
        std::queue<ll> que;
        rep(i,0,N){
            if(cnt[i]==0) que.push(i);
        }
        vector<int> ver;
        while(!que.empty()){
            int now=que.front(); que.pop();
            ver.pb(now);
            for(auto next:edge2[now]){
                cnt[next]--;
                if(cnt[next]==0) que.push(next);
            }
        }
        per(i,N-1,0){
            rep(j,0,edge2[ver[i]].size()){
                int next=edge2[ver[i]][j];
                h[ver[i]]=std::max(h[ver[i]],h[next]+weight[ver[i]][j]);
            }
        }
    }
    ll Query(int s,int t,int f){
        ll ret=0;
        potential();
        while(f){
            vi dist(N,inf);
            vector<int> memv(N),meme(N);
            dist[s]=0;
            prique<std::pair<ll,int>> que;
            que.push(mp(0,s));
            while(!que.empty()){
                auto now=que.top().second; 
                if(dist[now]<que.top().first){
                    que.pop();
                    continue;
                }
                que.pop();
                rep(i,0,edge[now].size()){
                    auto e=edge[now][i];
                    auto next=e.to;
                    if(e.cap>0&&dist[next]>dist[now]+h[now]-h[next]+e.cost){
                        dist[next]=dist[now]+h[now]-h[next]+e.cost;
                        memv[next]=now;
                        meme[next]=i;
                        que.push(mp(dist[next],next));
                    }
                }
            }
            if(dist[t]==inf) return -1;
            int now=t,max=f;
            while(now!=s){
                auto& e=edge[memv[now]][meme[now]];
                max=std::min(max,e.cap);
                now=memv[now];
            }
            f-=max;
            now=t;
            while(now!=s){
                auto& e=edge[memv[now]][meme[now]];
                e.cap-=max;
                auto& e2=edge[e.to][e.rev];
                e2.cap+=max;
                now=memv[now];
            }
            rep(i,0,N) h[i]+=dist[i];
            ret+=h[t]*max;
        }
        return ret;
    }
};
struct Fast_Fourier_Transform{
    void dft(vector<std::complex<double>> &func,int inverse){
        int siz=func.size();
        if(siz==1) return;
        vector<std::complex<double>> left,right;
        rep(i,0,siz/2){
            left.pb(func[i*2]);
            right.pb(func[i*2+1]);
        }
        dft(left,inverse);
        dft(right,inverse);
        std::complex<double> now=1,zeta=std::polar(1.0,inverse*2.0*acos(-1)/siz);
        rep(i,0,siz){
            func[i]=left[i%(siz/2)]+now*right[i%(siz/2)];
            now*=zeta;
        }
    }
    template<typename T>
    vector<double> multiply(vector<T> f,vector<T> g){
        vector<std::complex<double>> nf,ng;
        int siz=1;
        while(siz<f.size()+g.size()) siz<<=1;
        nf.resize(siz);
        ng.resize(siz);
        rep(i,0,f.size()) nf[i]=f[i];
        rep(i,0,g.size()) ng[i]=g[i];
        dft(nf,1);
        dft(ng,1);
        rep(i,0,siz) nf[i]*=ng[i];
        dft(nf,-1);
        vector<double> ret(siz);
        rep(i,0,siz) ret[i]=nf[i].real()/siz;
        return ret;
    }
};
struct Numver_Theoretic_Transform{
    void dft(vi &func,bool inverse){
        int siz=func.size();
        if(siz==1) return;
        vi left,right;
        rep(i,0,siz/2){
            left.pb(func[i*2]);
            right.pb(func[i*2+1]);
        }
        dft(left,inverse);
        dft(right,inverse);
        ll now=1;
        ll zeta;
        if(inverse) zeta=modpow(root,MOD-1-(MOD-1)/siz,MOD);
        else zeta=modpow(root,(MOD-1)/siz,MOD);
        rep(i,0,siz){
            func[i]=(left[i%(siz/2)]+now*right[i%(siz/2)])%MOD;
            now*=zeta;
            now%=MOD;
        }
    }
    vi multiply(vi f,vi g){
        vi nf,ng;
        int siz=1;
        while(siz<f.size()+g.size()) siz<<=1;
        nf.resize(siz);
        ng.resize(siz);
        rep(i,0,f.size()) nf[i]=f[i];
        rep(i,0,g.size()) ng[i]=g[i];
        dft(nf,0);
        dft(ng,0);
        rep(i,0,siz){
            nf[i]*=ng[i];
            nf[i]%=MOD;
        }
        dft(nf,1);
        vi ret(siz);
        ll div=modpow(siz,MOD-2,MOD);
        rep(i,0,siz) ret[i]=nf[i]*div%MOD;
        return ret;
    }
};
template<typename T>
struct tancomp{
    int place(std::pair<T,T> p){
        if(p.first<=0&&p.second<0) return 0;
        if(p.first>0&&p.second<=0) return 1;
        if(p.first==0&&p.second==0) return 2;
        if(p.first>=0&&p.second>0) return 3;
        return 4;
    }
    bool operator()(const std::pair<T,T> &l,const std::pair<T,T> &r){
        if(place(l)!=place(r)) return place(l)<place(r);
        //l.second/l.first<r.second/r.first
        return l.second*r.first<l.first*r.second;
    }
};
template<typename T>
vector<std::pair<T,T>> Declination_sort(ll N,vector<T> X,vector<T> Y){
    vector<std::pair<T,T>> ret(N);
    rep(i,0,N){
        ret[i]=(mp(X[i],Y[i]));
    }
    sort(ALL(ret),tancomp<T>());
    return ret;
}
vi fac,finv,inv;
void COMinit() {
    fac.resize(MAX);
    finv.resize(MAX);
    inv.resize(MAX);
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
ll COM(ll n,ll r){
    if(n<r||n<0||r<0) return 0;
    return fac[n]*finv[r]%MOD*finv[n-r]%MOD;
}
void comp(vi &A){
    std::map<ll,ll> memo;
    rep(i,0,A.size()) memo[A[i]]=0;
    ll cnt=0;
    for(auto &p:memo) p.second=cnt++;
    rep(i,0,A.size()) A[i]=memo[A[i]];
}
void dec(std::map<ll,ll> &mem,ll X){
    mem[X]--;
    if(mem[X]==0) mem.erase(X);
}
void print(bool flag){
    vector<char> P={
        "No",
        "Yes"
    };
    cout<<P[flag]<<endl;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::random_device rnd;
    std::mt19937 mt(rnd());
    ll N,M,L,K; cin>>N>>M>>L>>K;
    vi xc(M+2),yc(M+2),xt(L),yt(L);
    rep(i,0,M) cin>>xc[i+1]>>yc[i+1];
    rep(i,0,L) cin>>xt[i]>>yt[i];
    xc[M+1]=yc[M+1]=N;
    vector<vector<pii>> mem(M+1);
    rep(i,0,L){
        REP(j,0,M){
            if(xc[j]==xt[i]&&yc[j]==yt[i]){
                K--;
                break;
            }
            if(xc[j+1]==xt[i]&&yc[j+1]==yt[i]){
                K--;
                break;
            }
            if(xc[j]<=xt[i]&&xt[i]<=xc[j+1]&&yc[j]<=yt[i]&&yt[i]<=yc[j+1]){
                mem[j].pb(mp(xt[i],yt[i]));
            }
        }
    }
    vii dp(M+2,vi(L+1));
    dp[0][0]=1;
    COMinit();
    Numver_Theoretic_Transform ntt;
    REP(i,0,M){
        mem[i].pb(mp(xc[i],yc[i]));
        mem[i].pb(mp(xc[i+1],yc[i+1]));
        sort(ALL(mem[i]));
        ll P=mem[i].size()-2;
        vii dp2(P+2,vi(P+1));
        dp2[0][0]=1;
        vii from(P+2),weight(P+2);
        REP(j,0,P+1){
            vi dp3(P+2);
            dp3[j]=1;
            if(j){
                dp3[j]=MOD-1;
            }
            REP(k,j+1,P+1){
                if(mem[i][k].second<mem[i][j].second) continue;
                rep(l,j,k){
                    if(mem[i][l].second<=mem[i][k].second){
                        if(l==0) dp3[l]=(MOD-dp3[l])%MOD;
                        ll A=mem[i][k].first-mem[i][l].first,B=mem[i][k].second-mem[i][l].second;
                        dp3[k]+=(MOD-dp3[l])%MOD*COM(A+B,A)%MOD;
                        dp3[k]%=MOD;
                        if(l==0) dp3[l]=(MOD-dp3[l])%MOD;
                    }
                }
                from[k].pb(j);
                weight[k].pb(dp3[k]);
            }
        }
        rep(j,1,mem[i].size()){
            rep(a,0,from[j].size()){
                ll k=from[j][a];
                ll X=weight[j][a];
                ll Y=0;
                if(j<mem[i].size()-1) Y++;
                REP(l,Y,P){
                    dp2[j][l]+=dp2[k][l-Y]*X%MOD;
                    dp2[j][l]%=MOD;
                }
            }
        }
        dp[i+1]=ntt.multiply(dp[i],dp2[P+1]);
        while(dp[i+1].size()>L||dp[i+1][dp[i+1].size()-1]==0) dp[i+1].pop_back();
    }
    ll ans=0;
    REP(i,0,std::min((ll)dp[M+1].size(),K)){
        ans+=dp[M+1][i];
        ans%=MOD;
    }
    if(ans<0) ans+=MOD;
    cout<<ans<<endl;
}
yukicoder

結果

テストケース

ソースコード
