Codeforces Round #818 (Div. 2)

D. Madoka and The Corruption Scheme

题目大意

给定一场比赛，有\(2^n\)个参赛者。赞助商有k次机会可以调整某一局的结果。而我们想要知道不管赞助商如何调整，我们能得到的获胜者的编号最小值，即为让我们求在k次调整机会下，我们能获得的获胜者的编号最大值的最小编号。

分析

可以考虑赞助商是跟我们对着干的，因此，能让大的编号赢，其一定会让大的赢。那我们就是避免较大的编号赢。

那我们考虑一下，在k次调整下，编号能赢的条件是什么。

即为，从该点向上，输边数量小于等于k，这样我们可以通过调整使得其获胜。

我们再转换一下题意。

我们要求，所有输边小于等于k的点的数量。

先说结论，我只需要算一个\(\sum_{i=1}^{min(k,n)}C(n,i)\)。

我们来简单说明一下为什么这样算，看到的时候还是有点蒙。

我们先拿\(n=3\)举个例子。

接下来，我们枚举一下败场计数、

[1] (1 0) (1 0) (1 0) (1 0)
[2] ((2 1)  (1 0)) ((2 1)  (1 0))
[3] (((3 2)  (2 1)) ((2 1)  (1 0)))

其中，在每一轮内的集合都是等价的。例如在第一轮时的(1,0)，第二轮的((2 1) (1 0))都是其中的集合，此时我们可以发现其即为二叉树，第一轮的集合即为叶节点有两个的二叉树，第二轮的集合即为叶节点有四个的二叉树，依次类推。其中等价的概念，要理解。

依托于等价的概念，我们可以知道，从根节点走到子节点的所有路径，包含了所有的败场的排布可能

我们简单证明一下。用数学归纳法。

• 首先我们假设层高为i以内的二叉树都合法。
• 接下来，对于层高为i+1，对于其根节点，其连接了两个等价的层高为i二叉树，同时分别连接的两个边，任选其中一个是胜利，则另一个为失败。这样对于第i+1条边的选择来说胜负两种选择都有，同时因为i层高的二叉树已经包含了所有情况了，并且这两个i层高的二叉树等价，因此对于第i+1层高的二叉树，其也包含了所有情况。

因为等价的问题，因此我们要求从叶节点走到根节点，n条边中有i场失败的节点数量，我们可以直接用C(n,i)求得，因为不管哪种排布一定都会在我们构建的二叉树中出现。

这就结束啦，我们来看看代码。

Ac_code

#include <bits/stdc++.h>
#define fi first    
#define se second    
#define endl '\n'
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
typedef long long LL;
using namespace std;
const int N = 1e5 + 10,M = N*2,mod = 1e9 + 7;

int fact[N],infact[N];

int ksm(int a,int b)
{
    int res = 1;
    while(b)
    {
        if(b&1) res = 1ll*res*a%mod;
        b>>=1;
        a = 1ll*a*a%mod;
    }
    return res;
}

int C(int a,int b)
{
    return 1ll*fact[a]*infact[b]%mod*infact[a-b]%mod;
}

void solve() {
    int n,k;cin>>n>>k;
    fact[0] = infact[0] = 1;
    for(int i=1;i<=n;i++) fact[i] = 1ll*fact[i-1]*i%mod;
    infact[n] = ksm(fact[n],mod-2);
    for(int i=n-1;i;i--) infact[i] = 1ll*infact[i+1]*(i+1)%mod;
    if(k>=n) 
    {
        cout<<ksm(2,n)<<'\n';
        return ;
    }
    int ans = 0;
    for(int i=0;i<=min(k,n);i++) ans = (1ll*ans + C(n,i))%mod;
    cout<<ans<<'\n';
}
 
int main() 
{
    ios;
    int T=1;
    // cin>>T;
 
    while(T -- ) {
        solve();
    }
 
    return 0;
}

E. Madoka and The Best University

题目大意

求\(\sum_{a+b+c=n}lcm(c,gcd(a,b))\)

分析

考虑枚举gcd(a,b)，我们再枚举a+b的取值为(x+y)i其中要求gcd(x,y)=1，同时x+y=j。此时我们就能知道lcm(c,gcd(a,b))的值了。

因为gcd(x,y)=gcd(x,j-x)=gcd(x,j)=1，这里用到了这个性质gcd(a,b) = gcd(a, a+b) = gcd(a, ka+b)。

所以x的取值个数就是小于j且与j互质的数的个数，欧拉函数。

#include <bits/stdc++.h>
#define fi first    
#define se second    
#define endl '\n'
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
typedef long long LL;
using namespace std;
const int N = 1e5 + 10,M = N*2,mod = 1e9 + 7;

template<int T>
struct ModInt {
    const static int mod = T;
    int x;
    ModInt(int x = 0) : x(x % mod) {}
    int val() { return x; }
    ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < mod ? x0 + mod : x0); }
    ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
    ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
    void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }
    void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }
    void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }
    void operator /= (const ModInt &a) { *this = *this / a; }
    friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}
    
    ModInt pow(LL n) const {
        ModInt res(1), mul(x);
        while(n){
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    
    ModInt inv() const {
        int a = x, b = mod, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        if (u < 0) u += mod;
        return u;
    }
    
};
typedef ModInt<mod> mint;
int phi[N],Primes[N],cnt;
bool st[N];
int n;
void get_eulers()
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) Primes[cnt++]=i,phi[i]=i-1;
        for(int j=0;Primes[j]<=n/i;j++)
        {
            st[Primes[j]*i]=1;
            if(i%Primes[j]==0)
            {
                phi[Primes[j]*i]=phi[i]*Primes[j];
                break;
            }
            else phi[i*Primes[j]]=phi[i]*Primes[j]*(Primes[j]-1)/Primes[j];
        }
    }
}

mint lcm(int a,int b)
{
    return mint(a/__gcd(a,b))*mint(b);
}

void solve() {
    cin>>n;
    get_eulers();
    mint ans = 0;
    for(int i=1;i<=n;i++)//i为a,b的gcd
        for(int j=2*i;j<n;j+=i)//j为a+b
            ans += lcm(i,n-j)*mint(phi[j/i]);
    cout<<ans<<'\n';
}
 
int main() 
{
    ios;
    int T=1;
    // cin>>T;
 
    while(T -- ) {
        solve();
    }
 
    return 0;
}