Участник:Kachanov vv/ADAPANEL

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/ADAPANEL/

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int max_value = 200003;
const int M = 500;
const int mod = 1000000007;
 
class Solver {
public:
    Solver(int n, int m) : n(n), m(m) {}
 
    void init() {
        f[0] = 1;
        for (int i = 1; i < M; ++i) {
            for (int j = i; j < max_value; ++j) {
                f[j] += f[j - i];
                if (f[j] >= mod)
                    f[j] -= mod;
            }
        }
        memcpy(g, f, sizeof(f));
        for (int i = 1; i < M; ++i) {
            memset(h, 0, sizeof(h));
            for (int j = i; j < max_value; ++j) {
                if (j >= M)
                    h[j] += f[j - M];
                if (j >= i)
                    h[j] += h[j - i];
                if (h[j] >= mod)
                    h[j] -= mod;
                g[j] += h[j];
                if (g[j] >= mod)
                    g[j] -= mod;
            }
            memcpy(f, h, sizeof(f));
        }
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            edges[a].push_back(b);
        }
        sz = top = scc_cnt = 0;
    }
 
    void dfs(int x, const vector<int> G[]) {
        low[x] = dfn[x] = ++sz;
        stk[++top] = x;
        for (auto &y: G[x]) {
            if (!dfn[y]) {
                dfs(y, G);
                low[x] = min(low[x], low[y]);
            } else if (col[y] == -1) {
                low[x] = min(low[x], dfn[y]);
            }
        }
        if (dfn[x] == low[x]) {
            size[scc_cnt++] = 0;
            do {
                ++size[scc_cnt - 1];
                col[stk[top]] = scc_cnt - 1;
            } while (stk[top--] != x);
        }
    }
 
    void process() {
        memset(dfn, 0, sizeof(*dfn) * n);
        memset(col, -1, sizeof(*col) * n);
        for (int i = 0; i < n; ++i) {
            if (!dfn[i])
                dfs(i, edges);
        }
    }
 
    void dump() {
        long long ret = 1;
        for (int i = 0; i < scc_cnt; ++i) {
            ret = ret * g[size[i]] % mod;
        }
        cout << ret << endl;
    }
 
private:
    int n, m, top, scc_cnt, sz;
    int f[max_value], g[max_value], h[max_value];
    int low[max_value], dfn[max_value], size[max_value], col[max_value];
    int stk[max_value];
    std::vector<int> edges[max_value];
};
 
int main() {
    int n, m;
    cin >> n >> m;
    Solver solver(n, m);
    solver.init();
    solver.process();
    solver.dump();
 
    return 0;
}