主要思路

这道题挺有趣的，归根结底就是位运算。首先，一个充分的结论就是枚举长度为\(1\)的区间的概率为\(\frac{1}{N^2}\)，而长度大于1的概率为\(\frac{2}{N^2}\)。之后，枚举\(int\)的长度\(i \in [0,30]\)，把所有数的第\(i\)位组成一个序列进行扫描，之后枚举到第\(j\)个数进行分类讨论。

• 如果运算符是\(and\)，那么我们记\(last[0]\)为最后一个\(0\)的位置，中间一共有\(k-last[0]+1\)个与之运算得到1的数。乘上概率更新答案。
• 如果运算符是\(or\)，那么区间概率直接乘上\(i-1\)即可。
• 如果运算符是\(xor\)，我们需要把之前的\(0,1\)进行分块，记\(c_1,c_2\)为前面区间长的和，且\(c_1\)与\(c_2\)的区间不重合，交替进行。每次乘上相应的块长度即可，对于\(1\)进行块交换，\(0\)则保持原样。

代码

// CH3801.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200;
int n, arr[MAX_N];
double ans1, ans2, ans3;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    for (int k = 0; k < 30; k++)
    {
        int last[2], c1 = 0, c2 = 0;
        last[0] = last[1] = 0;
        for (int i = 1; i <= n; i++)
            if ((arr[i] >> k) & 1)
            {
                ans1 += (1 << k) * 1.0 / n / n;
                ans2 += (1 << k) * 1.0 / n / n;
                ans3 += (1 << k) * 1.0 / n / n;
                ans1 += (1 << k) * 2.0 / n / n * c1;
                ans2 += (1 << k) * 2.0 / n / n * (i - 1);
                ans3 += (1 << k) * 2.0 / n / n * (i - 1 - last[0]);
                last[1] = i;
                c1++, swap(c1, c2);
            }
            else
            {
                ans1 += (1 << k) * 2.0 / n / n * c2;
                ans2 += (1 << k) * 2.0 / n / n * (last[1]);
                last[0] = i, c1++;
            }
    }
    printf("%.3lf %.3lf %.3lf", ans1, ans3, ans2);
    return 0;
}

主要思路

这道题需要多重集的知识，如果没有学习请看这篇博客的多重集部分。

很明显，题意要求我们求出多重集的组合数，且为“增强版组合数”。所以，我们根据公式，使用二进制分解的方法来求出即可。这是一道比较裸的多重集组合数问题。

代码

// CF451E.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7, MAX_N = 25;
ll arr[MAX_N], n, inv[MAX_N], m;
ll quick_power(ll bas, ll tim)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}
ll C(ll a, ll b)
{
    if (a < 0 || b < 0 || a < b)
        return 0;
    a %= mod;
    if (a == 0 || b == 0)
        return 1;
    ll ans = 1;
    for (int i = 0; i < b; i++)
        ans = ans * (a - i) % mod;
    for (int i = 1; i <= b; i++)
        ans = ans * inv[i] % mod;
    return ans;
}
int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    inv[0] = 1;
    for (int i = 1; i < MAX_N; i++)
        inv[i] = quick_power(i, mod - 2);
    ll ans = 0;
    for (int stat = 0; stat < (1 << n); stat++)
        if (stat == 0)
            ans = (ans + C(n + m - 1, n - 1)) % mod;
        else
        {
            ll t = n + m, p = 0;
            for (int i = 0; i < n; i++)
                if ((stat >> i) & 1)
                    p++, t -= arr[i + 1];
            t -= (p + 1);
            if (p & 1)
                ans = (ans - C(t, n - 1)) % mod;
            else
                ans = (ans + C(t, n - 1)) % mod;
        }
    ans = (ans + mod) % mod;
    printf("%lld", ans);
    return 0;
}

source:Page 172，《算法竞赛进阶指南》李煜东著

主要思路和结论

给定一个\(n\)，求\(\sum_{i=1}^{n} \gcd(i,n)\)。

题意非常的小清新，然而推式子的时候很伤心。我一开始使用打表的方法，一直没成功发现其中的规律。所以推式子的能力还是相当重要的。

我们来分析一下。对于\(i\in [1,n], gcd(i,n)=1\)，它们对答案的贡献是\(\phi(n)\)。之后来看另一部分，也就是\(j\in [1,n], gcd(j,n)=k, k \neq 1\)，我们可以除下，变成\(k*gcd(\frac{j}{k},\frac{n}{k})=k, gcd(\frac{j}{k},\frac{n}{k})=1\)，其中根据欧拉定理，有\(\phi(k)\)个这样的\(gcd\)，所以推出得\(k*\phi(k)\)。答案最后只需统计\(k\)的因数乘上\(\phi(因数)\)即可。

最后可以考虑使用 map 记录已计算过的欧拉值，可获得常数优化。

代码

// POJ2480.cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#define ll long long
using namespace std;
map<ll, ll> prefix;
vector<ll> getFracted(ll x)
{
    vector<ll> res;
    for (ll i = 1; i * i <= x; i++)
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i)
                res.push_back(x / i);
        }
    return res;
}
ll phi(ll x)
{
    ll ans = x;
    for (ll i = 2; i * i <= x; i++)
        if (x % i == 0)
        {
            ans -= ans / i;
            while (x % i == 0)
                x /= i;
        }
    if (x > 1)
        ans -= ans / x;
    return ans;
}
int main()
{
    ll n;
    while (scanf("%lld", &n) != EOF)
    {
        ll ans = 0;
        vector<ll> container = getFracted(n);
        ll siz = container.size();
        for (int i = 0; i < siz; i++)
        {
            if (!prefix.count(n / container[i]))
                prefix[n / container[i]] = phi(n / container[i]);
            ll e = prefix[n / container[i]];
            ans += e * container[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

src:https://www.cnblogs.com/neopenx/p/4095691.html