BUPT2017 springtraining(16) #4 —

A.手动打表找规律得组合数

n -= 2, m -= 2, ans = C(n, m)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Mod = 1e9 + ;

ll fac[];

ll calc(ll x, int k = Mod - ) {

    ll ret = ;

    for(;k;k >>= , x = x * x % Mod)

        if(k & ) ret = ret * x % Mod;

    return ret;

}

int main() {

    ios::sync_with_stdio(false);

    int n, m;

    fac[] = fac[] = ;

    for(int i = ;i <= ;i ++)

        fac[i] = fac[i - ] * i % Mod;

    while(cin >> n >> m) {

        if(n > m) swap(n, m);

        cout << fac[m + n - ] * calc(fac[n - ]) % Mod * calc(fac[m - ]) % Mod << endl;

    }

    return ;

}

C.裸快速幂

#include <cstdio>

using namespace std;

double x = 1.000000011;

double n;

long long k;

int main() {

    scanf("%lf %lld", &n, &k);

    for(;k;k >>= , x = x * x)

        if(k & ) n = n * x;

    printf("%.8f\n", n);

    return ;

}

D.递推式那么明显当然是矩阵快速幂啦

唯一需要注意的是，自乘矩阵的填充方式...

开始时，a1 对应 f(d) ， a2 对应 f(d - 1) ...

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int d, n, m;

struct  matrix1{

    ll c[][];

    matrix1() {

        memset(c, , sizeof c);

    }

    void init() {

        memset(c, , sizeof c);

        for(int i = ;i < d;i ++) cin >> c[d -  - i][d - ], c[d -  - i][d - ] %= m;

        for(int i = ;i < d;i ++) c[i][i - ] = ;

    }

    matrix1 operator *(const matrix1 &a) const {

        matrix1 ret;

        for(int k = ;k < d;k ++)

            for(int i = ;i < d;i ++)

                if(c[i][k])

                    for(int j = ;j < d;j ++)

                        ret.c[i][j] = (ret.c[i][j] + c[i][k] * a.c[k][j]) % m;

        return ret;

    }

};

struct  matrix2{

    ll c[];

    matrix2() {

        memset(c, , sizeof c);

    }

    void init() {

        memset(c, , sizeof c);

        for(int i = ;i < d;i ++) cin >> c[i], c[i] %= m;

    }

    matrix2 operator *(const matrix1 &a) const {

        matrix2 ret;

        for(int i = ;i < d;i ++)

            for(int j = ;j < d;j ++)

                ret.c[i] = (ret.c[i] + c[j] * a.c[j][i]) % m;

        return ret;

    }

};

int main() {

    matrix1 c1;

    matrix2 c2;

    while(cin >> d >> n >> m, d != ) {

        c1.init(), c2.init();

        for(n --;n;n >>= , c1 = c1 * c1)

            if(n & ) c2 = c2 * c1;

        cout << c2.c[] << endl;

    }

    return ;

}

E.参考 CodeForces - 785D

F.看样例猜结论就好了

输出所有质数的幂就好了

#include <iostream>

using std::cin;

using std::endl;

using std::cout;

int n, v[], p[];

int main() {

    cin >> n;

    for(int i = ;i <= n;i ++) {

        if(!v[i]) {

            for(int j = i;j <= n;j *= i)

                p[++ p[]] = j;

        }

        for(int j = i << ;j <= n;j += i)

            v[j] = ;

    }

    cout << p[] << endl;

    for(int i = ;i <= p[];i ++)

        cout << p[i] << " ";

    return ;

}

G.参考 CodeForces - 785C

I.能被 6 整除一定能被 2 和 3 整除，8 和 9 同理

于是就是求 1 - n 内2 3 5 7的倍数之和

容斥原理即可

#include <iostream>

using namespace std;

int main() {

    long long n;

    cin >> n;

    cout << n - n /  - n /  - n /  - n /  + n /  + n /  + n /  + n /  + n /  + n /  - n /  - n /  - n /  - n /  + n / ;

    return ;

}

K.对于n 的每一个因数 t

它对答案贡献为 t * phi(n / t)

效率玄学吧

#include <cstdio>

int v[], p[];

int phi(int x) {

    int ret = x;

    for(int i = ;1ll * p[i] * p[i] <= x;i ++)

        if(x % p[i] == ) {

            ret = ret - ret / p[i];

            while(x % p[i] == ) x /= p[i];

        }

    if(x != ) ret -= ret / x;

    return ret;

}

int main() {

    long long n, ans;

    for(int i = ;i < ;i ++) {

        if(!v[i]) p[++ p[]] = i;

        for(int j = ;j <= p[] && p[j] * i < ;j ++) {

            v[p[j] * i] = ;

            if(i % p[j] == ) break;

        }

    }

    while(scanf("%lld", &n) != EOF) {

        ans = ;

        for(long long i = ;i * i <= n;i ++) {

            if(n % i)  continue;

            ans += i * phi(n / i);

            if(i * i != n) ans += n / i * phi(i);

        }

        printf("%lld\n", ans);

    }

    return ;

}

L.和式加一项减一项变成了C(n + m, n)

n,m 大 p 小且 p 保证为质数，使用卢卡斯定理

Lucas(n，m) % p = Lucas(n / p，m / p) * Comb(n % p，m % p) % p

注意lucas里面的取模后计算组合数，可能会出现 C(n，m) 里 n < m

所以Comb函数里需要判断的

考虑 p 为读入的不能预处理，所以我们有两种解决方案

1.每组数据 O(p) 预处理处阶乘 fac

Comb就可以 O(logn) 回答，理论效率 O(p + logn * log(p)(n + m))

大概就是 O(p)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t, n, m, p;

ll fac[];

ll calc(ll x, int k = p - ) {

    ll ret = ;

    for(;k;k >>= , x = x * x % p)

        if(k & ) ret = ret * x % p;

    return ret;

} 

ll C(int n, int m) {

    if(n < m) return ;

    return fac[n] * calc(fac[m]) % p * calc(fac[n - m]) % p;

}

ll lucas(int n, int m) {

    if(!m) return ;

    return C(n % p, m % p) * lucas(n / p, m / p) % p;

}

int main() {

    ios::sync_with_stdio(false);

    fac[] = ;

    cin >> t;

    while(t --) {

        cin >> n >> m >> p;

        for(int i = ;i < p;i ++) fac[i] = fac[i - ] * i % p;

        cout << lucas(n + m, n) << endl;

    }

    return ;

}

2.不进行预处理，Comb直接 O(p + logn) 回答

理论效率O(p * log(p)(n + m))

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int t, n, m, p;

ll calc(ll x, int k = p - ) {

    ll ret = ;

    for(;k;k >>= , x = x * x % p)

        if(k & ) ret = ret * x % p;

    return ret;

} 

ll C(int n, int m) {

    if(n < m) return ;

    ll ret1 = , ret2 = ;

    for(int i = , j = n;i <= m;i ++, j --) {

        ret1 = ret1 * i % p;

        ret2 = ret2 * j % p;

    }

    return ret2 * calc(ret1) % p;

}

ll lucas(int n, int m) {

    if(!m) return ;

    return C(n % p, m % p) * lucas(n / p, m / p) % p;

}

int main() {

    ios::sync_with_stdio(false);

    cin >> t;

    while(t --) {

        cin >> n >> m >> p;

        cout << lucas(n + m, n) << endl;

    }

    return ;

}

然而第二种的表现更好...因为都是最坏时间估计

而第一种稳定在O(p)，第二种实际是几倍优于最坏效率的

巴特西

BUPT2017 springtraining(16) #4 ——基础数论

最新文章

热门文章