#422 Div2 D

题意

假设有 n 个人比赛，每次比赛进行分组，每组人数必须相同，如果一组有 x 人，则那一组要比赛 $ \frac{x * (x - 1)}{2}$次，最终一人获胜，其它人淘汰，不同回合的 x 可以不同，设最终经过 f(n) 次比赛比赛结束（产生冠军）。给出 t, l, r 求 $t^0*f(l)+t^1*f(l+1)+...+t^{r-l}*f(r)$。

分析

通过测试几组数据可以发现，分的组越多，总比赛次数越少，那么就要 x 尽可能的小，所以对于参赛的 n 个人， n 的最小质因子 k 为每组的人数，如果 n 为素数，$f(n)=\frac{n * (n - 1)} 2$，否则 $f(n)=f(\frac n k)+\frac n k * f(k)$，。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e6 + 5;

const int INF = 2e9 + 1;

const ll MOD = 1e9 + 7;

ll dp[MAXN];

int is_prime[MAXN];

vector<int> prime;

int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

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

        if(!is_prime[i]) {

            prime.push_back(i);

            for(ll j = 1LL * i * i; j < MAXN; j += i) {

                is_prime[j] = 1;

            }

        }

    }

    ll t;

    int l, r;

    cin >> t >> l >> r;

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

        if(!is_prime[i]) {

            dp[i] = 1LL * i * (i - 1) / 2 % MOD;

        } else {

            for(auto j : prime) {

                if(i % j == 0) {

                    dp[i] = (dp[i / j] + 1LL * i / j * dp[j]) % MOD;

                    break;

                }

            }

        }

    }

    ll x = 1, ans = 0;

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

        ans = (ans + x * dp[i]) % MOD;

        x = (x * t) % MOD;

    }

    cout << ans << endl;

    return 0;

}

巴特西

#422 Div2 D

#422 Div2 D

题意

分析

code

最新文章

热门文章