Algoogle

Algorithm for Programming Contest

Codeforces 434C Tachibana Kanade’s Tofu

Category: Codeforces Tag: aho-corasick, dp

Tachibana Kanade’s Tofu

問題概要


m進数のn個のパターンとそのそれぞれにスコアv[i](0<=i<n)が与えられる.
m進数の区間[l,r]の値xについて, そのxの一部分にパターンiをu個含む場合v[i]*uだけxのスコアに加える.
このとき, 区間[l,r]にスコアがkを超えないものはいくつあるか.

解法


桁DPする.
[l,r]なので[0,r]と[0,l-1]に分けてやることで下を無視する.
上限は現在まで上限に沿ってきているかどうかの状態をDPに持たせる.
パターンにマッチするかはAho-Corasickでオートマトンを生成し, 各状態をDPに持たせれば良い.
またパターンにleading-0が含まれるのでDPの状態に現在の値がleading-0かどうかの状態も持たせる.
またスコアはKより大きい数はいらないので無視するかまとめて使わない部分に足してしまう.
dp[digit][state][min(K+1,score)][is leading-0][is upper bound]
みたいにすればよい.
あとは素直にループを回せば良い

コード


(434C.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) begin(u),end(u)
#define pb push_back

const int mod = 1e9+7;
struct mint{
    int x;
    mint():x(0){}
    mint(int y){ if((x=y%mod+mod) >= mod) x-= mod;}

    mint &operator+=(const mint &m){ if((x += m.x) >= mod) x-=mod; return *this;}
    mint &operator-=(const mint &m){ if((x += mod-m.x) >= mod) x-=mod; return *this;}
    mint &operator*=(const mint &m){ x = 1LL*x*m.x%mod; return *this;}
    mint &operator/=(const mint &m){ x=(1LL*x*ex(m,mod-2).x)%mod; return *this;}
    mint operator+(const mint &m)const{ return mint(*this) += m;}
    mint operator-(const mint &m)const{ return mint(*this) -= m;}
    mint operator*(const mint &m)const{ return mint(*this) *= m;}
    mint operator/(const mint &m)const{ return mint(*this) /= m;}
    bool operator<(const mint &m)const{ return x < m.x;}
    mint ex(mint a, long long t){
        if(!t) return 1;
        mint res = ex(a,t/2);
        res *= res;
        return (t&1)?res*a:res;
    }
};
ostream &operator<<(ostream& os, const mint &m){ os << m.x; return os;}

struct PMA{
    int id, val, next[32];
    vector<int> matched;
    PMA(){memset(next, -1, sizeof(next)); val = 0; id = -1;}
};

PMA* pma[256];
int N, M, K, pl, v[32];
vector<vector<int>> ps;
vector<int> lr[2];
mint dp[210][210][510][2][2], ans[2];

vector<int> set_union(const vector<int> &a, const vector<int> &b){
    vector<int> res;
    set_union(all(a), all(b), back_inserter(res));
    return res;
}

PMA *buildPMA(vector<vector<int>> pattern){
    PMA *root, *now;
    pma[pl] = new PMA;
    root = pma[pl];
    root->id = pl;
    root->next[0] = pl++;
    for(int i = 0; i < (int)pattern.size(); ++i){
        auto &pat = pattern[i];
        now = root;
        for(int p: pat){
            ++p;
            if(now->next[p]<0){
                now->next[p] = pl;
                pma[pl] = new PMA;
                pma[pl]->id = pl;
                ++pl;
            }
            now = pma[now->next[p]];
        }
        now->matched.push_back(i);
    }

    queue<PMA*> que;
    for(int i = 1; i <= M; i++){
        if(root->next[i]<0) root->next[i] = root->id;
        else {
            pma[root->next[i]]->next[0] = root->id;
            que.push(pma[root->next[i]]);
        }
    }
    while(!que.empty()){
        now = que.front(); que.pop();
        for(int i = 1; i <= M; i++){
            if(now->next[i]>=0){
                PMA *nxt = pma[now->next[0]];
                while(nxt->next[i]<0) nxt = pma[nxt->next[0]];
                pma[now->next[i]]->next[0] = nxt->next[i];
                pma[now->next[i]]->matched = set_union(pma[now->next[i]]->matched, pma[nxt->next[i]]->matched);
                que.push(pma[now->next[i]]);
            }
        }
    }
    return root;
}

mint calc(int s){
    memset(dp,0,sizeof(dp));
    vector<int> &up = lr[s];
    dp[0][0][0][1][1] = 1;
    rep(i,up.size()) rep(j,pl) rep(k,K) rep(l,2) rep(m,2){
        if(!dp[i][j][k][l][m].x) continue;
        rep(d, m? up[i]+1: M) {
            int ni = i+1, nj = j, nk = k , nl = l&!d, nm = m&(up[i]==d);
            PMA *nxt = pma[j];
            while(nxt->next[d+1] < 0) nxt = pma[nxt->next[0]];
            nxt = pma[nxt->next[d+1]];
            if(!nl) nj = nxt->id, nk = min(K,k+nxt->val);
            dp[ni][nj][nk][nl][nm] += dp[i][j][k][l][m];
        }
    }
    mint ret = mint();
    rep(j,pl)rep(k,K)rep(l,2)rep(m,2)
        ret += dp[up.size()][j][k][l][m];
    return ret;
}

mint solve(){
    buildPMA(ps);
    rep(i,pl) for(int j: pma[i]->matched) pma[i]->val += v[j];
    int pos = lr[0].size()-1;
    do {
        if(pos+1<(int)lr[0].size()) lr[0][pos+1] = M-1;
        lr[0][pos]--;
    } while (lr[0][pos--]<0);
    if(lr[0].size() > 1 and !lr[0][0]) lr[0].erase(begin(lr[0]),begin(lr[0])+1);
    ++K;
    rep(i,2) ans[i] = calc(i);
    return ans[1]-ans[0];
}

void input(){
    cin >> N >> M >> K;
    rep(i,2){
        int len, d;
        cin >> len;
        while(len--) {
            cin >> d;
            lr[i].pb(d);
        }
    }
    rep(i,N){
        ps.pb(vector<int>());
        int len, d;
        cin >> len;
        while(len--) {
            cin >> d;
            ps[i].pb(d);
        }
        cin >> v[i];
    }
}

int main(){
    cin.sync_with_stdio(0);
    input();
    cout << solve() << endl;
    return 0;
}

Comments