月度归档：2019年10月

洛谷 P4777 【模板】扩展中国剩余定理（EXCRT）

发表评论

照着教程想了一下午，终于A了。。。
参考文章：
https://www.luogu.org/blog/niiick/solution-p4777
https://www.luogu.org/problemnew/solution/P4777
https://blog.csdn.net/xiaobian_/article/details/87949337

扩展欧几里得算法与中国剩余定理


https://www.cnblogs.com/yangsongyi/p/9867057.html
（快速乘规避溢出）
https://www.cnblogs.com/jt2001/p/6129914.html
https://blog.csdn.net/qq_39599067/article/details/81118467

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
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;
ll b[100005], a[100005]; //b是余数，a是模数
ll quickmultiply(ll a, ll b,ll mod) {
    if (b == 0)return 0;
    ll result = quickmultiply(a, b / 2, mod) % mod;
    result = 2*result%mod;
    if (b & 1)result = (result+a)%mod;
    return result;
}
ll ngcd(ll a, ll b) {
    return b == 0 ? a : ngcd(b, a % b);
}
ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
ll excrt() {
    ll lcm = a[1], ans = b[1];
    for (int i = 2; i <= n; i++) {
        ll k1, k2, K, mod = lcm;
        ll gcd = exgcd(lcm, a[i], k1, k2);
        ll minus = ((b[i] - ans) % a[i] + a[i]) % a[i];
        if ((minus % ngcd(lcm, a[i]) != 0))return -1;
        K = (quickmultiply(k1,(minus / gcd),(a[i] / gcd)) + a[i] / gcd) % (a[i] / gcd);
        lcm *= a[i] / gcd, ans = (K * mod + ans) % lcm;
    }
    return (ans % lcm + lcm) % lcm;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    cout<<excrt();
}

洛谷 P3381 【模板】最小费用最大流

发表评论

参考链接：https://www.cnblogs.com/widerg/p/9394929.html

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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int eN = 100005;
const int vN = 10005;
const int INF = 0x7f7f7f7f;
int n, m, s, t;
int ePtr = -1; //e的实际存储只能从偶数号顶点开始，奇数号顶点存储反向边
int to[eN << 1], nxt[eN << 1], value[eN << 1], cost[eN << 1];
int head[vN], dis[vN], minV[vN];
int preID[eN << 1], preNode[eN << 1];
bool inqueue[vN];
inline void createEdge(int u, int v, int w, int c) {
    to[++ePtr] = v;
    value[ePtr] = w;
    cost[ePtr] = c;
    nxt[ePtr] = head[u];
    head[u] = ePtr;
}
bool SPFA(int s, int t) {
    queue<int> q;
    memset(dis, 0x7f, sizeof(dis));
    memset(inqueue, false, sizeof(inqueue));
    memset(preID, -1, sizeof(preID));
    memset(preNode, -1, sizeof(preNode));
    memset(minV, 0x7f, sizeof(minV));
    dis[s] = 0;
    inqueue[s] = true;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        inqueue[x] = false;
        for (int i = head[x]; ~i; i = nxt[i]) {
            int dest = to[i];
            if (dis[dest] > dis[x] + cost[i] && value[i]) {
                dis[dest] = dis[x] + cost[i];
                minV[dest] = min(minV[x], value[i]);
                preID[dest] = i;
                preNode[dest] = x;
                if (!inqueue[dest]) {
                    inqueue[dest] = true;
                    q.push(dest);
                }
            }
        }
    }
    return dis[t] != INF;
}
void MinCostMaxFlow(int s, int t, int& maxflow, int& mincost) {
    while (SPFA(s, t)) {
        for (int i = t; i != s; i = preNode[i]) {
            value[preID[i]] -= minV[t];
            value[preID[i] ^ 1] += minV[t];
        }
        maxflow += minV[t];
        mincost += minV[t] * dis[t];
    }
}
int main() {
    memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, w, f;
        scanf("%d%d%d%d", &u, &v, &w, &f);
        createEdge(u, v, w, f);
        createEdge(v, u, 0, -f);//第0号边被占用，这条语句为反向边留下空间
    }
    int maxflow = 0, mincost = 0;
    MinCostMaxFlow(s, t, maxflow, mincost);
    printf("%d %d\n", maxflow, mincost);
}

洛谷 P3376 【模板】网络最大流

发表评论

参考链接：https://www.cnblogs.com/widerg/p/9387909.html

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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int eN = 100005;
const int vN = 10005;
const int INF = 0x7f7f7f7f;
int n, m, s, t;
int ePtr = -1; //e的实际存储只能从偶数号顶点开始，奇数号顶点存储反向边
int to[eN<<1], nxt[eN<<1], value[eN<<1];
int head[vN], dis[vN];
inline void createEdge(int u, int v, int w) {
    to[++ePtr] = v;
    value[ePtr] = w;
    nxt[ePtr] = head[u];
    head[u] = ePtr;
}
bool bfs(int s, int t) {
    queue<int> q;
    memset(dis, 0x7f, sizeof(dis));
    dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; ~i; i = nxt[i]) {
            int dest = to[i];
            if (dis[dest] == INF && value[i] != 0) {
                dis[dest] = dis[x] + 1;
                q.push(dest);
            }
        }
    }
    return dis[t] != INF;
}
int dfs(int x, int t, int maxflow) {
    if (x == t)return maxflow;
    int ans = 0;
    for (int i = head[x]; ~i; i = nxt[i]) {
        int dest = to[i];
        if (dis[dest] != dis[x] + 1 || value[i] == 0 || ans >= maxflow)continue;
        int f = dfs(dest, t, min(value[i], maxflow - ans));
        value[i] -= f;
        value[i ^ 1] += f;
        ans += f;
    }
    return ans;
}
int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t))ans += dfs(s, t, INF);
    return ans;
}
int main() {
    memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        createEdge(u, v, w);
        createEdge(v, u, 0);//第0号边被占用，这条语句为下一个边留下空间
    }
    printf("%d", dinic(s, t));
}

Codeforces 102346 problem K Keep Calm and Sell Balloons

发表评论

这道题重点要说矩阵快速幂，公式不会推。用了一个Berlekamp-Massey algorithm的模板。最主要想将一般情况下线性递推式怎么用矩阵快速幂优化。
本题目的递推公式是：F(n)=6*F(n-1)-8*F(n-2)-8*F(n-3)+16*F(n-4)。
故构造矩阵递推公式：
\begin{bmatrix}
F(n) \\
F(n-1) \\
F(n-2) \\
F(n-3)
\end{bmatrix} =
\begin{bmatrix}
6 & -8 & -8 & 16 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix} *
\begin{bmatrix}
F(n-1) \\
F(n-2) \\
F(n-3) \\
F(n-4)
\end{bmatrix}
得
\begin{bmatrix}
F(n) \\
F(n-1) \\
F(n-2) \\
F(n-3)
\end{bmatrix} =
\begin{bmatrix}
6 & -8 & -8 & 16 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix}^{n-4} *
\begin{bmatrix}
F(4) \\
F(3) \\
F(2) \\
F(1)
\end{bmatrix}
。
对于一般的线性递推公式F(n)=a_1*F(n-1)+a_2*F(n-2)+…+a_{k-1}*F(n-k+1)+a_k*F(n-k)，
可以构造一长宽都为k的矩阵，满足：
\begin{bmatrix}
F(n) \\
F(n-1) \\
… \\
F(n-k+2) \\
F(n-k+1)
\end{bmatrix} =
\begin{bmatrix}
a_1 & a_2 & … & a_{n-k+1} & a_{n-k} \\
1 & 0 & … & 0 & 0 \\
0 & 1 & … & 0 & 0 \\
… & … & … & … & … \\
0 & 0 & … & 1 & 0
\end{bmatrix} *
\begin{bmatrix}
F(n-1) \\
F(n-2) \\
… \\
F(n-k+1) \\
F(n-k)
\end{bmatrix}
因此只需对该矩阵做快速幂，即可以以O(k^3logn)的复杂度推出任意n情况下的数列的值。
本题代码如下：

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
#include <iostream>
using namespace std;
const long long MOD = 1e9 + 7;
const int maxtrixN=4;
struct matrix {
    long long arr[maxtrixN][maxtrixN];
    matrix operator * (matrix m2) {
        matrix result;
        long long(&arr)[maxtrixN][maxtrixN] = result.arr;
        const long long(&arr1)[maxtrixN][maxtrixN] = this->arr;
        const long long(&arr2)[maxtrixN][maxtrixN] = m2.arr;
        for (int i = 0; i < maxtrixN; i++) {
            for (int j = 0; j < maxtrixN; j++) {
                arr[i][j] = 0;
                for (int k = 0; k < maxtrixN; k++) {
                    arr[i][j] += arr1[i][k] * arr2[k][j] % MOD;
                    arr[i][j] += MOD;
                    arr[i][j] %= MOD;
                }
            }
        }
        return result;
    }
};
const matrix c = { 6,-8,-8,16,1,0,0,0,0,1,0,0,0,0,1,0 };
matrix quickpow(long long n) {
    if (n == 1)return c;
    matrix half = quickpow(n / 2);
    matrix result = half * half;
    if (n & 1)result = result * c;
    return result;
}
long long getValue(long long n) {
    matrix result = quickpow(n);
    long long(&arr)[4][4] = result.arr;
    return (arr[0][0] * 1536 % MOD + arr[0][1] * 416 % MOD + arr[0][2] * 96 % MOD + arr[0][3] * 24 % MOD +MOD) % MOD;
}
int main() {
    int n;
    long long a1[] = { 0,2,24,96,416,1536 };
    cin >> n;
    if (n < 6)cout << a1[n];
    else cout << getValue(n-5);
}

洛谷 P3386 【模板】二分图匹配

发表评论
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
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<list>
#include<cmath>
#include<queue>
#include<unordered_set>
#include<unordered_map>
using namespace std;
int n, m, e;
vector<int> edges[2005];
bool visited[2005];
int match[2005];
bool biFind(int node) {
    if (visited[node])return false;
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (!match[edges[node][i]] || biFind(match[edges[node][i]])) {
            match[node] = edges[node][i];
            match[edges[node][i]] = node;
            return true;
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> e;
    for (int i = 1; i <= e; i++) {
        int u, v;
        cin >> u >> v;
        if (u > n || v > m)continue;
        edges[u].push_back(v + n);
        edges[v + n].push_back(u);
    }
    int cnter = 0;
    for (int i = 1; i <= n; i++) {
        memset(visited, false, sizeof(visited));
        if (biFind(i))cnter++;
    }
    cout << cnter;
}