P4134

标签：tmp int cin define P4134 dp MOD

\(dp_{i,j}\) 表示填了 \(i\) 个数，当前的颜色为 \(j\) 的方案数

\[ dp_{i,j}=\sum\limits_{k=1}^{tot}[k\neq j]dp_{i-1,k}+dp_{i,j}\times i \]

对于每个 \(dp_i\) 建 segment_tree ，前面的式子可以求和解决，后面的部分可以区间乘

// Author: xiaruize
#ifndef ONLINE_JUDGE
#define debug(x) cerr << "On Line:" << __LINE__ << #x << "=" << x << endl
bool start_of_memory_use;
#else
#define debug(x)
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
clock_t start_clock = clock();
#endif
// #define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)

{
    if (a > b)
        return a;
    return b;
}
int min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000009;
const int N = 1300 + 10;

void add(int &x, int y)
{
    x += y;
    if (x < 0)
        x += MOD;
    if (x >= MOD)
        x -= MOD;
}

void mul(int &x, int y)
{
    x = 1ll * x * y % MOD;
}

struct segment_tree
{
#define ls p << 1
#define rs p << 1 | 1

    struct node
    {
        int sum, laz;

        node()
        {
            sum = 0;
            laz = 1;
        }

        void tag(int x)
        {
            mul(sum, x);
            mul(laz, x);
        }
    } tr[N << 2];

    void pushdown(int p)
    {
        tr[ls].tag(tr[p].laz);
        tr[rs].tag(tr[p].laz);
        tr[p].laz = 1;
        return;
    }

    void pushup(int p)
    {
        tr[p].sum = (tr[ls].sum + tr[rs].sum) % MOD;
        return;
    }

    void update(int p, int l, int r, int x, int val)
    {
        if (l == r)
        {
            add(tr[p].sum, val);
            return;
        }
        int mid = l + r >> 1;
        pushdown(p);
        if (x <= mid)
            update(ls, l, mid, x, val);
        else
            update(rs, mid + 1, r, x, val);
        pushup(p);
    }

    int query(int p, int l, int r, int x)
    {
        if (l == r)
        {
            return tr[p].sum;
        }
        int mid = l + r >> 1;
        pushdown(p);
        if (x <= mid)
            return query(ls, l, mid, x);
        else
            return query(rs, mid + 1, r, x);
    }
} seg[N];

int n, len;
int col[N];
map<pair<char, char>, int> mp;
string a, b;
int tot = 0;
int cur[N];

void solve()
{
    cin >> n;
    string tmp;
    while (n--)
    {
        cin >> tmp;
        a += tmp;
    }
    cin >> n;
    while (n--)
    {
        cin >> tmp;
        b += tmp;
    }
    cin >> len;
    n = a.size();
    rep(i, 0, n - 1)
    {
        if (!mp.count({a[i], b[i]}))
            mp[{a[i], b[i]}] = ++tot;
        col[n - i] = mp[{a[i], b[i]}];
        // cerr << col[i + 1] << ' ';
    }
    // reverse(col + 1, col + n + 1);
    seg[1].update(1, 1, tot, col[1], 1);
    rep(i, 2, n)
    {
        // mms(cur, 0);
        rep(j, 1, len) cur[j] = ((seg[j - 1].tr[1].sum - seg[j - 1].query(1, 1, tot, col[i]) + seg[j].query(1, 1, tot, col[i])) % MOD + MOD) % MOD;
        rep(j, 1, len) seg[j].tr[1].tag(i - 1);
        rep(j, 1, len) seg[j].update(1, 1, tot, col[i], cur[j]);
    }
    cout << seg[len].tr[1].sum << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
#ifndef ONLINE_JUDGE
    cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
    cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
    return 0;
}

标签：tmp,int,cin,define,P4134,dp,MOD
From： https://www.cnblogs.com/xiaruize/p/18108512