题解：P7618 [COCI 2011/2012 #2] FUNKCIJA

· · 题解

\gdef \dp{\mathrm{dp}} \gdef \son{\operatorname{son}} \gdef \ssum{\operatorname{sum}}

建图，对于两个有关联的循环（假设是第 i 个和第 j 个），我们连一条边 (i, j)；如果这个循环的上下界都是常数而非变量，朝结点 0 连边。由于上下界最多只有一个变量，所以容易证明这是一个树。

然后我们开始 dp。设 \dp _ {u, i} 表示第 u 个循环的循环变量的值为 i 时子树循环的次数，容易得到转移：

\dp _ {u, i} = \prod _ {v \in \son(u)} \sum _ {j = X _ v} ^ {Y _ v} \dp _ {v, j}

记 V = 10 ^ 5，直接按照这个式子转移是 O(nV ^ 2) 的，时间复杂度显然承受不了，我们考虑用前缀和预处理后面那一坨和式，每次 O(V) 地去维护即可，时间复杂度 O(nV)，然后就做完了。

#include<iostream>
#include<vector>
#include<utility>
#include<cctype>

#define x first
#define y second

constexpr int N = 26 + 5;
constexpr int V = 1e5 + 5;
constexpr int MOD = 1000000007;
typedef std::pair<int, int> Range;

int n; Range r[N]; std::vector<int> G[N];
int sum[N][V]; bool calc_ed[N];

inline int gsum(int u, int l, int r) {
    return l > r ? 0 : (sum[u][r] - sum[u][l - 1] + MOD) % MOD;
}

int solve_dp(int u, int i) {
    int ret = 1;
    for(const auto& v : G[u]) {
        if(!calc_ed[v] && (calc_ed[v] = true)) {
            int pL = r[v].x ? r[v].x : 1, pR = r[v].y ? r[v].y : V - 1;
            for(int j = pL; j <= pR; ++j) {
                sum[v][j] = (1ull * sum[v][j - 1] + solve_dp(v, j)) % MOD; 
            }
        }
        int L = (r[v].x ? r[v].x : i), R = (r[v].y ? r[v].y : i);
        ret = (1ull * ret * gsum(v, L, R)) % MOD;
    }
    return ret;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0), std::cout.tie(0);

    std::cin >> n;
    for(int i = 1; i <= n; ++i) {
        std::string a, b; std::cin >> a >> b;
        bool ia = std::isalpha(a[0]), ib = std::isalpha(b[0]);
        r[i].x = ia ? 0 : std::stoi(a), r[i].y = ib ? 0 : std::stoi(b);
        int ati = a[0] - 'a' + 1, bti = b[0] - 'a' + 1;
        G[ia ? ati : ib ? bti : 0].push_back(i);
    }
    std::cout << solve_dp(0, 0) << "\n";

    return 0;
}