CSES Work Combinations
// compile: make data
// run: ./data < data.in
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#define Debug(x...) _debug_print_format(#x, x);
std::ifstream terminal("/dev/tty");
#define PP cerr<<"\033[1;30mpause...\e[0m",terminal.ignore();
#else
#define debug(x...)
#define Debug(x...)
#define PP
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define VI vector<int>
#define VII vector<vector<int>>
#define VIII vector<vector<vector<int>>>
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0)
#define cmin(x,...) x=min({(x), __VA_ARGS__})
#define cmax(x,...) x=max({(x), __VA_ARGS__})
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define NaN (int)(0x8b88e1d0595d51d1)
#define double long double
#define int long long
#define uint unsigned long long
#define MAXN 200010
#define P 1000000007

struct trie {
    int base, N;
    struct node {
        int isword, c;
        vector<node*> ch;
        node *parent = nullptr;
    };
    node *root;
    vector<node> datalist;
    int total = 0;
    node *newnode(int c, node *p = nullptr) {
        node *x = &datalist[total++];
        x->ch.resize(N, 0);
        x->c = c;
        x->parent = p;
        return x;
    }
    trie(int M, char L = 0, char R = 127) {
        base = L;
        N = R - L + 1;
        datalist.resize(M);
        root = newnode(-1);
    }
    void insert(string s) {
        node *x = root;
        for (char c: s) {
            if (!x->ch[c - base]) {
                x->ch[c - base] = newnode(c - base, x);
            }
            x = x->ch[c - base];
        }
        x->isword = 1;
    }
    string get(node *x) {
        vector<char> v;
        while (x->parent) {
            v.push_back(x->c + base);
            x = x->parent;
        }
        reverse(v.begin(), v.end());
        string res(v.begin(), v.end());
        return res;
    }
    void graphviz_dump(string filename = "graph.dot") {
        FILE *f = fopen(filename.c_str(), "w");
        fprintf(f, "digraph {\n");
        rep(i, 0, total) {
            node *x = &datalist[i];
            fprintf(f, "    %lld;\n", i, (x->c >= 0 ? char(x->c + base) : ' '), x->isword ? "red" : "black");
        }
        queue<node*> q; q.push(root);
        while (!q.empty()) {
            node *x = q.front(); q.pop();
            rep(i, 0, N) {
                if (x->ch[i]) {
                    fprintf(f, "    %ld -> %ld;\n", x - &datalist[0], x->ch[i] - &datalist[0]);
                    q.push(x->ch[i]);
                }
            }
        }
        fprintf(f, "}\n");
    }
    void solve(string s) {
        vector<int> dp(sz(s)+1, 0);
        dp[0] = 1;
        rep(i, 0, sz(s)+1) {
            if (!dp[i]) continue;
            node *x = root;
            int j = i;
            while (j < sz(s) && x->ch[s[j] - base]) {
                x = x->ch[s[j] - base];
                if (x->isword) dp[j+1] += dp[i], dp[j+1] %= P;
                ++j;
            }
        }
        cout << dp[sz(s)] << endl;
    }
};

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    string s; cin >> s;
    int n; cin >> n;
    trie t(1e6+1, 'a', 'z');
    rep(i, 0, n) {
        string x; cin >> x;
        t.insert(x);
    }
    // t.graphviz_dump();
    t.solve(s);

    return 0;
}

Comments

  1. 9 months ago
    2025-12-06 2:27:26

    I have spent a few weeks playing Xo3game and I can confirm many games are engaging. Jump in and start playing: xo3game

  2. 9 months ago
    2025-12-19 13:42:32

    Win777slots? Dude, the name alone is worth a try. Hoping for some lucky spins over there! I’m ready at win777slots.

  3. 9 months ago
    2025-12-29 6:10:42

    Kwin68app, not my first choice, needs improvement. I would not suggest using this one, not very reliable. Checkout the site here: kwin68app

  4. 2 weeks ago
    2026-8-28 10:38:11

    Just what I was looking for in a gaming site. Simple registration and the luck seems to be on my side here. Big thumbs up for 777asgame.

  5. 5 days ago
    2026-9-07 13:02:09

    I finally found a site that actually loads fast. The interface is super clean and getting started was a breeze. Definitely giving hulk123login a try tonight!

  6. 2 days ago
    2026-9-09 17:42:25

    [5561]Remi189: Login Daftar Akun Slot Gacor Deposit Dana,Remi189 menyediakan akses login dan daftar akun mudah untuk main slot gacor deposit dana serta cara main baccarat online. Download apk casino terpercaya sekarang. visit: remi189

Send Comment Edit Comment


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
Previous
Next