2019牛客暑期多校训练营（第二场）

Contest Link: https://ac.nowcoder.com/acm/contest/882

A. Eddy Walker

题目描述

Eddy likes to walk around. Especially, he likes to walk in a loop called "Infinite loop". But, actually, it's just a loop with finite length(Anyway, the name doesn't matter). Eddy can walk in a fixed length. He finds that it takes him N steps to walk through the loop a cycle. Then, he puts N marks on the "Infinite loop" labeled with , where i and i+1 are a step away each other, so as 0 and N-1. After that, Eddy stands on the mark labeled 0 and start walking around. For each step, Eddy will independently uniformly randomly choose to move forward or backward. If currently Eddy is on the mark labeled i, he will on the mark labeled i+1 if move forward or i-1 if move backward. If Eddy is on the mark labeled N-1 and moves forward, he will stand on the mark labeled 0. If Eddy is on the mark labeled 0 and moves backward, he will stand on the mark labeled N-1.

Although, Eddy likes to walk around. He will get bored after he reaches each mark at least once. After that, Eddy will pick up all the marks, go back to work and stop walking around.

You, somehow, notice the weird convention Eddy is doing. And, you record T scenarios that Eddy walks around. For i-th scenario, you record two numbers where tells that in the i-th scenario, Eddy can walk through the loop a cycle in exactly steps(Yes! Eddy can walk in different fixed length for different day.). While tells that you found that in the i-th scenario, after Eddy stands on the mark labeled , he reached all the marks.

However, when you review your records, you are not sure whether the data is correct or even possible. Thus, you want to know the probability that those scenarios will happen.

Precisely, you are going to compute the probability that first i scenarios will happen sequentially for each i.

输入描述

The first line of input contains an integers T.
Following T lines each contains two space-separated integers and

输出描述

Output T lines each contains an integer representing the probability that first i scenarios will happen sequentially.

you should output the number module

Suppose the probability is , the desired output will be

示例1

输入

3
1 0
2 1
3 0

输出

1
1
0

Solve

有n个点的环, 初始在0, 可以随机的向前走一步或向后走一步. 问恰好走完所有n个点时落在点m的概率.

遇到概率问题, 可以先投点打表寻找规律.
根据问题, 我们可以很轻松的写出下面这个投点程序.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
#define pu push
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define repn(i, a, b) for (int i = (a); i <= (b); i++)
#define repv(i, v) for (auto i : v)
const int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
const int eps = 1e-7;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int maxn = 1e2;

void random() {
    srand((unsigned int)time(NULL));

    const int times = 1e8;

    int n;
    cin >> n;
    int pos;
    vector<int> cnt(n, 0);
    vector<bool> vis(n, false);

    // 总共投点times次
    for (int i = 0; i < times; i++) {
        vis = vector<bool>(n, false);
        int pos = 0;
        int vv = 1;
        // 起始位于点0, 所以开始时直接标记
        vis[pos] = true;
        while (vv < n) {
            int step = rand() % 2 ? 1 : -1;
            pos += step;
            // 处理0向前走 和 n-1向后走
            pos = (pos % n + n) % n;
            if (!vis[pos]) {
                vis[pos] = true;
                vv++;
            }
            if (vv == n) {
                cnt[pos]++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << i << ": " << cnt[i] << " P = " << (ld)cnt[i] / times << endl;
    }
}

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

    int T = 1;
    // cin >> T;
    repn(i, 1, T) { random(); }

    return 0;
}

然后可以选取较小的数字进行测试,

$ ./Random
3
0: 0 P = 0
1: 499953 P = 0.499953
2: 500047 P = 0.500047

$ ./Random
4
0: 0 P = 0
1: 330953 P = 0.330953
2: 338216 P = 0.338216
3: 330831 P = 0.330831

$ ./Random
5
0: 0 P = 0
1: 250154 P = 0.250154
2: 249830 P = 0.24983 
3: 249869 P = 0.249869
4: 250147 P = 0.250147

可以发现,

同时根据case1, 可以发现N=1时,

根据上述三个关系, 写出程序. 但同时注意答案要乘上前缀和.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
#define pu push
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define repn(i, a, b) for (int i = (a); i <= (b); i++)
#define repv(i, v) for (auto i : v)
const int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
const int eps = 1e-7;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int maxn = 1e2;

ll fastpower(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans = ans * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

ll ans = 1;

void solve() {
    ll n, m;
    cin >> n >> m;
    if (n == 1) {
        cout << (ans *= 1) << endl;
        return;
    } else if (n > 1) {
        if (m == 0) {
            cout << (ans *= 0) << endl;
            return;
        } else {
            cout << (ans = ans * fastpower(n - 1, mod - 2) % mod) << endl;
        }
    }
}

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

    int T = 1;
    cin >> T;
    repn(i, 1, T) { solve(); }

    return 0;
}

B. Eddy Walker 2

题目描述

As you may already know, Eddy likes to walk around. Especially, he likes to walk in a number line called "Infinite line". Actually, it's exactly a line with infinite length!

Eddy is at number 0 and starts to walk around. Since Eddy is a little drunk(just finished his work, make sense), he will not walk in a fixed length. Instead, he will independently uniformly randomly walk in an integer length between 1 and K. That is, he will walk for 1 unit of length in a probability of , 2 units in , , units in . If he currently stands on number i and walk for j unit of length, he will end up on number i+j.

Since Eddy is drunk, he will walk around infinitely. You, somehow, notice this weird thing and start wondering whether will Eddy ever step on the number N. However, you don't want to wait for such stupid thing. You would like to compute the probability that Eddy would ever step on number N.

输入描述

The first line of input contains an integers T.
Following T lines each contains two space-separated integers and
If , is a number approaching infinity.

输出描述

For each i, output one line containing a number representing the probability.
you should output the number module
Suppose the probability is , the desired output will be

示例1

输入

3
1 0
2 1
3 -1

输出

1
500000004
500000004

Solve

从0出发, 一次最远能走k步, 分别有&\frac{1}{k}&的几率走1步,2步,...,k步. 求走到n的概率

根据题目可以得到DP转移式

因为这个式子只与前k项有关系，所以可以进行线性递推优化，使用BM线性递推模板。

模板

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define sz(x) ((int)(x).size())
typedef long long ll;
typedef vector<int> VI;
const ll mod = 1000000007;

ll fastpower(ll a, ll b) {
    ll res = 1;
    a %= mod;
    assert(b >= 0);
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
// head

int _, n;
namespace linear_seq {
const int N = 10010;
ll res[N], base[N], _c[N], _md[N];

vector<int> Md;
void mul(ll *a, ll *b, int k) {
    rep(i, 0, k + k) _c[i] = 0;
    rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] =
        (_c[i + j] + a[i] * b[j]) % mod;
    for (int i = k + k - 1; i >= k; i--)
        if (_c[i])
            rep(j, 0, sz(Md)) _c[i - k + Md[j]] =
                (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;
    rep(i, 0, k) a[i] = _c[i];
}
int solve(ll n, VI a, VI b) {  // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
                               //        printf("%d\n",sz(b));
    ll ans = 0, pnt = 0;
    int k = sz(a);
    assert(sz(a) == sz(b));
    rep(i, 0, k) _md[k - 1 - i] = -a[i];
    _md[k] = 1;
    Md.clear();
    rep(i, 0, k) if (_md[i] != 0) Md.push_back(i);
    rep(i, 0, k) res[i] = base[i] = 0;
    res[0] = 1;
    while ((1ll << pnt) <= n) pnt++;
    for (int p = pnt; p >= 0; p--) {
        mul(res, res, k);
        if ((n >> p) & 1) {
            for (int i = k - 1; i >= 0; i--) res[i + 1] = res[i];
            res[0] = 0;
            rep(j, 0, sz(Md)) res[Md[j]] =
                (res[Md[j]] - res[k] * _md[Md[j]]) % mod;
        }
    }
    rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod;
    if (ans < 0) ans += mod;
    return ans;
}
VI BM(VI s) {
    VI C(1, 1), B(1, 1);
    int L = 0, m = 1, b = 1;
    rep(n, 0, sz(s)) {
        ll d = 0;
        rep(i, 0, L + 1) d = (d + (ll)C[i] * s[n - i]) % mod;
        if (d == 0)
            ++m;
        else if (2 * L <= n) {
            VI T = C;
            ll c = mod - d * fastpower(b, mod - 2) % mod;
            while (sz(C) < sz(B) + m) C.pb(0);
            rep(i, 0, sz(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
            L = n + 1 - L;
            B = T;
            b = d;
            m = 1;
        } else {
            ll c = mod - d * fastpower(b, mod - 2) % mod;
            while (sz(C) < sz(B) + m) C.pb(0);
            rep(i, 0, sz(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
            ++m;
        }
    }
    return C;
}
int gao(VI a, ll n) {
    VI c = BM(a);
    c.erase(c.begin());
    rep(i, 0, sz(c)) c[i] = (mod - c[i]) % mod;
    return solve(n, c, VI(a.begin(), a.begin() + sz(c)));
}
};  // namespace linear_seq

AC代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
#define pu push
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define sz(x) (int)x.size()
#define se second
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define repn(i, a, b) for (int i = (a); i <= (b); i++)
#define repv(i, v) for (auto i : v)
const int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
const int eps = 1e-7;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int maxn = 1e2;

typedef vector<ll> VI;

ll fastpower(ll a, ll b) {
    ll res = 1;
    a %= mod;
    assert(b >= 0);
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
// head

int _, n;
namespace linear_seq {
const int N = 10010;
ll res[N], base[N], _c[N], _md[N];

vector<int> Md;
void mul(ll *a, ll *b, int k) {
    rep(i, 0, k + k) _c[i] = 0;
    rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] =
        (_c[i + j] + a[i] * b[j]) % mod;
    for (int i = k + k - 1; i >= k; i--)
        if (_c[i])
            rep(j, 0, sz(Md)) _c[i - k + Md[j]] =
                (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;
    rep(i, 0, k) a[i] = _c[i];
}
int solve(ll n, VI a, VI b) {  // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
                               //        printf("%d\n",sz(b));
    ll ans = 0, pnt = 0;
    int k = sz(a);
    assert(sz(a) == sz(b));
    rep(i, 0, k) _md[k - 1 - i] = -a[i];
    _md[k] = 1;
    Md.clear();
    rep(i, 0, k) if (_md[i] != 0) Md.push_back(i);
    rep(i, 0, k) res[i] = base[i] = 0;
    res[0] = 1;
    while ((1ll << pnt) <= n) pnt++;
    for (int p = pnt; p >= 0; p--) {
        mul(res, res, k);
        if ((n >> p) & 1) {
            for (int i = k - 1; i >= 0; i--) res[i + 1] = res[i];
            res[0] = 0;
            rep(j, 0, sz(Md)) res[Md[j]] =
                (res[Md[j]] - res[k] * _md[Md[j]]) % mod;
        }
    }
    rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod;
    if (ans < 0) ans += mod;
    return ans;
}
VI BM(VI s) {
    VI C(1, 1), B(1, 1);
    int L = 0, m = 1, b = 1;
    rep(n, 0, sz(s)) {
        ll d = 0;
        rep(i, 0, L + 1) d = (d + (ll)C[i] * s[n - i]) % mod;
        if (d == 0)
            ++m;
        else if (2 * L <= n) {
            VI T = C;
            ll c = mod - d * fastpower(b, mod - 2) % mod;
            while (sz(C) < sz(B) + m) C.pb(0);
            rep(i, 0, sz(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
            L = n + 1 - L;
            B = T;
            b = d;
            m = 1;
        } else {
            ll c = mod - d * fastpower(b, mod - 2) % mod;
            while (sz(C) < sz(B) + m) C.pb(0);
            rep(i, 0, sz(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
            ++m;
        }
    }
    return C;
}
int gao(VI a, ll n) {
    VI c = BM(a);
    c.erase(c.begin());
    rep(i, 0, sz(c)) c[i] = (mod - c[i]) % mod;
    return solve(n, c, VI(a.begin(), a.begin() + sz(c)));
}
};  // namespace linear_seq

void solve() {
    ll n, k;
    cin >> k >> n;

    if (n == 0) {
        cout << "1" << endl;
        return;
    }
    if (n == -1) {
        cout << 2 * fastpower(k + 1, mod - 2) % mod << endl;
        return;
    }

    vector<ll> dp(3 * k, 0);
    vector<ll> v;
    dp[0] = 1;
    v.pb(1);
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] = (dp[i] + dp[j]) % mod;
        }
        dp[i] = dp[i] * fastpower(k, mod - 2) % mod;
        v.pb(dp[i]);
    }
    for (int i = k + 1; i <= 2 * k; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i] = (dp[i] + dp[i - j]) % mod;
        }
        dp[i] = dp[i] * fastpower(k, mod - 2) % mod;
        v.pb(dp[i]);
    }
    cout << linear_seq::gao(v, n) << endl;
}

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

    int T = 1;
    cin >> T;
    repn(i, 1, T) { solve(); }

    return 0;
}

D. Kth Minimum Clique

题目描述

Given a vertex-weighted graph with N vertices, find out the K-th minimum weighted clique.

A subset of vertices of an undirected graph is called clique if and only if every two distinct vertices in the subset are adjacent. The weight of a clique is the summation of the weight of vertices in it.

输入描述

The first line of input contains two space-separated integers N, K.
The second line of input contains N space-separated integers representing the weight of each vertex.
Following N lines each contains N characters . There's an edge between vertex i and vertex j if and only if

输出描述

Output one line containing an integer representing the answer. If there's less than K cliques, output

示例1

输入

2 3
1 2
01
10

输出

2

说明

An empty set is considered as a clique.

Solve

求第k小的团

// BeiyanPiki
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
#define pu push
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define len(x) ((int)(x).length())
#define all(x) ((x).begin(), (x).end())
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for (int i = (a)-1; i >= (b); i--)
#define repn(i, a, b) for (int i = (a); i <= (b); i++)
#define repv(i, v) for (auto i : v)
const int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
const double pi = acos(-1);
const int eps = 1e-7;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int maxn = 1e2 + 10;

int n, k;
vector<int> w;
struct node {
    ll w;
    vector<int> v;
    node(ll w, vector<int> v) : w(w), v(v) {}
    bool operator<(const node& n) const { return w > n.w; }
};

priority_queue<node> Q;
bool G[maxn][maxn];

int X = 0;

void Dij() {
    Q.pu(node(0, vector<int>()));
    while (!Q.empty()) {
        node t = Q.top();
        k--;
        Q.pop();
        if (k == 0) {
            cout << t.w << endl;
            return;
        }

        int v;
        if (t.v.empty()) {
            v = 0;
        } else {
            v = t.v.back() + 1;
        }
        rep(i, v, n) {
            bool f = true;
            for (auto j : t.v) {
                if (!G[i][j]) {
                    f = false;
                    break;
                }
            }
            if (f) {
                vector<int> v = t.v;
                v.pb(i);
                Q.pu(node(t.w + w[i], v));
            }
        }
    }
    cout << "-1" << endl;
}

void solve() {
    cin >> n >> k;
    w = vector<int>(n);
    rep(i, 0, n) { cin >> w[i]; }
    rep(i, 0, n) {
        rep(j, 0, n) {
            char x;
            cin >> x;
            G[i][j] = (x == '0' ? false : true);
        }
    }
    Dij();
}

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

    int T = 1;
    // cin >> T;
    repn(i, 1, T) { solve(); }

    return 0;
}