[20181101][模拟赛]

题面

T1

思路

裸地等比数列求和。然而考试的时候并不会。学会了一种很nb的等比数列求和的方法。

假如我们要求\(\sum\limits_{i = 1}^n{x^i}\)，那么我们设\(P=\sum\limits_{i = 1}^n{x^i}\)，容易发现，P的x进制表示就是1111....111,共m个1，然后我们考虑\(Q=x^{m+1}\)的x进制表示，就是1000....000，共m个0。然后将Q-1求出来。就是\(\overline{(x-1)(x-1)...(x-1)}_x\)然后求出\(\frac{Q-1}{x-1}\)就可以了，因为要取模，所以求个逆元就好了。

真正的等比数列求和公式

\[S_n=\frac{a_1*(1-q^n)}{(1-q)}(q为公比)\]

代码

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
ll qm(ll x,int y) {
    ll ans = 1;
    for(;y;y >>= 1,x = x * x % mod) 
        if(y & 1) ans = ans * x % mod;
    return ans;
}
int main() {
    freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    int n = read(),m = read();
    ll ans = 0;
    ans = m;
    for(int i = 2;i <= n;++i) {
        ll k = (qm(i,m + 1) - 1 + mod) % mod;
        k *= qm(i - 1,mod - 2);
        k %= mod;
        k = (k - 1) % mod;
        ans = (ans + k) % mod;
    }
    cout<<ans;
    return 0;
}

T2

思路

其实并不难，仔细一想就可以发现其实就是将整棵树的边权之和乘以2，然后减去距离根结点最远的点与根节点的距离

代码

#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 50010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
struct node{
    int v,nxt,w;
}e[N * 2];
int dis[N],ejs,head[N];
void add(int u,int v,int w) {
    e[++ejs].v = v;e[ejs].w = w; e[ejs].nxt = head[u];head[u] = ejs;
}
int ans,Max = 0;
queue<int>q;
int vis[N];
void bfs() {
    while(!q.empty()) q.pop();
    dis[1] = 0;
    q.push(1);
    vis[1] = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u];i;i = e[i].nxt) {
            int v = e[i].v;
            if(vis[v]) continue;
            dis[v] = dis[u] + e[i].w;
            Max = max(Max,dis[v]);
            q.push(v);
            vis[v] = 1;
        }
    }
}
int main() {
    freopen("tour.in","r",stdin);
    freopen("tour.out","w",stdout);
    int n = read();
    for(int i = 1;i < n;++i) {
        int u = read(),v = read(),w = read();
        add(u,v,w);
        add(v,u,w);
        ans += w * 2;
    }
    bfs();
    cout<<ans - Max;
    return 0;
}

T3

思路

发现其实只有数组中的幸运数字才是有贡献的。所以可以先把这些数字提取出来，然后dp。用f[i][j]表示前i种幸运数字中，选j种的方案数。最后统计一下答案。

代码

#include<cstdio>
#include<iostream>
#include<map>
#define int ll
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
const int mod = 1e9 + 7;
map<int,int>ma;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
ll jc[N],inv[N],tot,a[N],OK[N];
ll qm(ll x,int y) {
    ll ans = 1;
    for(;y;y >>= 1,x = x * x % mod)
        if(y & 1) ans = ans * x % mod;
    return ans;
}
ll C(ll x,ll y) {
    return (ll)jc[x] * (ll)inv[y] % mod * (ll)inv[x-y] % mod;
}
int pd(int x) {
    while(x) {
        if(x % 10 != 4 && x % 10 != 7) return 0;
        x/=10;
    }
    return 1;
}
int f[2100][2100];
signed main() {
    freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
    int n = read(),K = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    jc[0] = 1;
    for(int i = 1;i <= n;++i) jc[i] = (ll)jc[i - 1] * (ll)i % mod;
    inv[n] = qm(jc[n],mod - 2);
    for(int i = n - 1;i >= 0; --i) inv[i] = (ll)inv[i + 1] * (i + 1) % mod;
    int cnt = 0;
    for(int i = 1;i <= n;++i) {
        if(pd(a[i])) {
            if(!ma[a[i]])
            OK[++tot] = a[i];
            ma[a[i]]++;
        }
        else cnt++;
    }
    f[0][0] = 1;
    for(int i = 1;i <= tot;++i) {
        f[i][0] = 1;
        for(int j = 1;j <= tot; ++j) {
            f[i][j] = (f[i-1][j] + f[i-1][j - 1] * ma[OK[i]] % mod) % mod;
        }
    }
    ll ans = 0;
    for(int i = 0;i <= tot;++i) {
        ans += (ll)f[tot][i] * C(cnt,K-i) % mod;
        ans >= mod ? ans -= mod : 0;
    }
    cout<<ans;
    return 0;
}