T1: 等比数列の合計計算

数列$ \sum_{i=1}^n x^i $を効率的に求めます。この問題ではx進法の特性を利用した新しいアプローチを採用しました。

変数Pを$x^1 + x^2 + ... + x^n$と定義すると、x進法で表現する際は連続する1の並びになります。この性質を活かし、$Q = x^{m+1}$のx進法表現から$Q-1$を導出し、$(x-1)$で割ることで最終的な合計値を得ます。

以下に数式を示します：

$$S_n = \frac{a_1(1-q^n)}{1-q}$$

実装ではモジュロ演算に対応する逆元計算を用いています。

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
ll input() {
    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 mod_pow(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 = input(),m = input();
    ll result = 0;
    result = m;
    for(int i = 2;i <= n;++i) {
        ll temp = (mod_pow(i,m + 1) - 1 + MOD) % MOD;
        temp *= mod_pow(i - 1,MOD - 2);
        temp %= MOD;
        temp = (temp - 1) % MOD;
        result = (result + temp) % MOD;
    }
    cout<<result;
    return 0;
}

T2: 木構造の辺合計処理

ツリー構造の全辺の合計値を求める問題です。根からの最大距離を除いた値が解答となります。

BFSアルゴリズムを使用して各ノードまでの距離を計算し、最大値を取得します。その後、全辺合計値から最大距離を引くことで結果を求めます。

#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 50010;
struct Edge {
    int to, weight, next;
}edges[N*2];
int distance[N], edge_count = 0, head[N];
void add_edge(int u,int v,int w) {
    edges[++edge_count].to = v;
    edges[edge_count].weight = w;
    edges[edge_count].next = head[u];
    head[u] = edge_count;
}
int total_sum = 0, max_dist = 0;
bool visited[N];
queue<int>q;
void bfs() {
    q.pop();
    distance[1] = 0;
    q.push(1);
    visited[1] = true;
    while(!q.empty()) {
        int current = q.front();
        q.pop();
        for(int i = head[current];i;i = edges[i].next) {
            int neighbor = edges[i].to;
            if(visited[neighbor]) continue;
            distance[neighbor] = distance[current] + edges[i].weight;
            max_dist = max(max_dist, distance[neighbor]);
            q.push(neighbor);
            visited[neighbor] = true;
        }
    }
}
int main() {
    freopen("tour.in","r",stdin);
    freopen("tour.out","w",stdout);
    int node_count = input();
    for(int i = 1;i < node_count;++i) {
        int u = input(),v = input(),w = input();
        add_edge(u,v,w);
        add_edge(v,u,w);
        total_sum += w * 2;
    }
    bfs();
    cout<<total_sum - max_dist;
    return 0;
}

T3: 幸運数字の組み合わせ計算

特定の条件を満たす数字のみを考慮した動的計画法による解法です。

まず幸運数字を抽出し、組み合わせ数を求めるDPテーブルを作成します。組み合わせ数の計算には前計算された階乗と逆元を使用しています。

#include<cstdio>
#include<iostream>
#include<map>
#define int long long
using namespace std;
typedef long long ll;
const int MAX = 100000 + 100;
const int MOD = 1000000007;
map<int,int>lucky_map;
ll factorial[MAX], inv_factorial[MAX], total = 0, valid_count = 0;
ll mod_pow(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 combination(ll n,ll k) {
    return factorial[n] * inv_factorial[k] % MOD * inv_factorial[n-k] % MOD;
}
bool is_lucky(int x) {
    while(x) {
        if(x % 10 != 4 && x % 10 != 7) return false;
        x /= 10;
    }
    return true;
}
int dp[2100][2100];
int main() {
    freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
    int n = input(), K = input();
    int numbers[n];
    for(int i = 0;i < n;++i) numbers[i] = input();
    factorial[0] = 1;
    for(int i = 1;i <= n;++i) factorial[i] = factorial[i-1] * i % MOD;
    inv_factorial[n] = mod_pow(factorial[n], MOD-2);
    for(int i = n-1;i >= 0;--i) inv_factorial[i] = inv_factorial[i+1] * (i+1) % MOD;
    int unique_count = 0;
    for(int i = 0;i < n;++i) {
        if(is_lucky(numbers[i])) {
            if(lucky_map[numbers[i]] == 0) {
                valid_count++;
                lucky_map[numbers[i]] = 1;
            }
            else lucky_map[numbers[i]]++;
        }
    }
    dp[0][0] = 1;
    for(int i = 1;i <= valid_count;++i) {
        dp[i][0] = 1;
        for(int j = 1;j <= valid_count;++j) {
            dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] * lucky_map[unique_numbers[i]] % MOD) % MOD;
        }
    }
    ll answer = 0;
    for(int i = 0;i <= valid_count;++i) {
        answer = (answer + dp[valid_count][i] * combination(valid_count, K-i)) % MOD;
    }
    cout<<answer;
    return 0;
}