日度归档：13 10 月, 2017

洛谷 计算系数

发表评论

题号：P1313
大晚上的刷杨辉三角………………

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
#define MOD 10007
long long arr[1005][1005];
long long a, b, k, n, m;
long long quickpow(long long x, long long y){
    if (y == 0)return 1;
    long long qpsqr2 = quickpow(x, y / 2)%MOD;
    if (y % 2 == 0){
        return (qpsqr2*qpsqr2) % MOD;
    }
    else{
        return (((qpsqr2*qpsqr2) % MOD)*(x%MOD)) % MOD;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> a >> b >> k >> n >> m;
    for (int i = 0; i <= 1000; i++){
        arr[0][i] = 1;
        arr[i][i] = 1;
    }
    for (int i = 1; i <= 1000; i++){
        for (int j = 1; j < i; j++){
            arr[j][i] = (arr[j][i - 1] % MOD + arr[j - 1][i - 1] % MOD) % MOD;
        }
    }
    long long ans = arr[n][k];
    ans = (ans*quickpow(a, n)) % MOD;
    ans = (ans*quickpow(b, m)) % MOD;
    cout << ans;
    return 0;
}

20180808更新：
不用杨辉三角啦！因为我会乘法逆元啦！！！哈哈

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
#define MOD 10007
ll a,b,k,n,m;
//C(min(n,m),k)*b^m*a^n
ll quickpow(ll a, ll b) {
    if (b == 0)return 1;
    ll re = quickpow(a, b / 2) % MOD;
    re = (re*re) % MOD;
    if (b % 2 == 1)re *= a % MOD;
    return re % MOD;
}
ll inv(ll x) {
    return quickpow(x, MOD - 2) % MOD;
}
int main() {
    cin >> a >> b >> k >> n >> m;
    ll re = (quickpow(a, n)*quickpow(b, m)) % MOD;
    ll cU = 1;
    for (ll i = k; i >= k - min(n, m) + 1; i--) {
        cU *= i % MOD;
        cU %= MOD;
    }
    ll cD = 1;
    for (ll i = 1; i <= min(n, m); i++) {
        cD *= i % MOD;
        cD %= MOD;
    }
    re = ((re * cU) % MOD*inv(cD)) % MOD;
    cout << re;
}

CodeVS 1077 多源最短路 模版

发表评论

从来没写过多源最短路，明天就NOIP初赛了，今天晚上写一下。。。。

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
long long arr[105][105];
int n;
long long q;
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cin >> arr[i][j];
        }
    }
    for (int k = 1; k <= n; k++){
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
            }
        }
    }
    cin >> q;
    for (long long i = 1; i <= q; i++){
        int s, e;
        cin >> s >> e;
        cout << arr[s][e] << endl;
    }
    return 0;
}