Kalorona

CH3801:Rainbow 的信号题解

主要思路

这道题挺有趣的，归根结底就是位运算。首先，一个充分的结论就是枚举长度为\(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;
}

BZOJ1101:「POI2007」Zap 题解

主要思路

这道题是一道很好的题，包含了数论里面的很多技巧。

首先，这是一道多组询问的题，询问数量非常的大，遂放弃使用欧拉函数来求。考虑可以使用莫比乌斯函数的性质来搞，开始从这方面分析。

复习一下莫比乌斯函数的定义：

\[ \mu(x) = \begin{cases} 0, 在x中存在指数大于一的质因子 \\ 1, 在x中质因子指数都为1且质因子个数为偶数 \\ -1, 在x中质因子质数都为1且质因子个数为奇数 \end{cases} \]

我们观察一下答案式子：\(\sum_{i,j} [gcd(x,y)=d]\)。我们先把\(gcd\)部分进行变换：

\[gcd(\frac{x}{d}, \frac{y}{d}) = 1\]

显然，这样的对数为\( \lfloor \frac{x}{d} \rfloor*\lfloor \frac{y}{d} \rfloor \)。我们考虑容斥：因为如果暴力累加的话，会多出很多不该存在的部分，比如说又是2的倍数又是3的倍数的部分。

所以最后答案式为：

\[\sum_{i=1}^{min\{a,b\}} \mu(i)*\lfloor \frac{x}{i} \rfloor*\lfloor \frac{y}{i} \rfloor \]

这时有个技巧，我们可以证明在整数段\([x, min\{ \lfloor \frac{a}{\lfloor \frac{a}{x} \rfloor} \rfloor, \lfloor \frac{b}{\lfloor \frac{b}{x} \rfloor} \rfloor \} ]\)上，\(\lfloor \frac{x}{i} \rfloor*\lfloor \frac{y}{i} \rfloor\)的结果是一样的，直接前缀和与之相乘即可。最后这样的段最坏情况为\(O(\sqrt{a}+\sqrt{b})\)，所以时间复杂度比较低。

代码

// BZ1101.cpp
#include <bits/stdc++.h>
#define ll int
using namespace std;
const int MAX_N = 5e4 + 200;
ll mobi[MAX_N], sum[MAX_N], n;
bool vis[MAX_N];
int main()
{
    for (int i = 1; i < MAX_N; i++)
        mobi[i] = 1;
    for (int i = 2; i < MAX_N; i++)
    {
        if (vis[i])
            continue;
        mobi[i] = -1;
        for (int j = 2; i * j < MAX_N; j++)
        {
            vis[i * j] = true;
            if (j % i == 0)
                mobi[i * j] = 0;
            else
                mobi[i * j] *= -1;
        }
    }
    for (int i = 1; i < MAX_N; i++)
        sum[i] = sum[i - 1] + mobi[i];
    scanf("%d", &n);
    while (n--)
    {
        int a, b, k, gx;
        scanf("%d%d%d", &a, &b, &k);
        a /= k, b /= k;
        int ans = 0;
        for (int i = 1; i <= min(a, b); i = gx + 1)
        {
            gx = min(a / (a / i), b / (b / i));
            ans += (sum[gx] - sum[i - 1]) * (a / i) * (b / i);
        }
        printf("%d\n", ans);
    }
    return 0;
}

Codeforces 451E:Devu and Flowers 题解

主要思路

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

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

代码

// 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，《算法竞赛进阶指南》李煜东著

POJ2480:Longge’s Problem 题解

主要思路和结论

给定一个\(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