日记 - 伊埃斯的博客站

我是耐断更王。

至于我为啥又开始更了呢？因为我发现，不把解题思路记下来真的会忘。

因为今天要把所有的没写解题思路的题补上，所以就不分上午下午的了。

P10986 [蓝桥杯 2023 国 Python A] 2023↗

我们看到“恰好”两个字，就想到先推“至少”的情况，再用二项式反演的式子推到“恰好”。

设 $f_m$ 表示至少有 $m$ 个 2023 的方案数。我们钦定有 $m$ 个 2023，再用插板法↗，在这些 2023 的缝里插入那些乱七八糟的数。因为插入的时候会再凑出一些 2023，所以是“至少”。那么，在 $m$ 个 2023 中插入 $n - 4m$ 个数的方案是

f_m = \binom{(n - 4m) + (m + 1) - 1}{(n - 4m) - 1}

设 $g_m$ 表示恰好有 $m$ 个 2023 的方案数，那么有：

f_m = \sum\limits_{i = m}^{n}\binom{i}{m}g_i

根据二项式反演公式，我们得到：

g_m = \sum\limits_{i = m}^{n}(-1)^{i - m}\binom{i}{m}f_i

那么我们就求得了 $g_m$ ，就是答案。时间复杂度 $\mathcal{O}(n)$

我们先考虑没有限制的情况： $dp_{i}$ 表示没有限制的情况下买价格为 $i$ 的物品的方案数，容易发现这就是一个完全背包，可以在 $\mathcal{O}(val)$ 的复杂度下预处理，其中 $val$ 表示最大价格。然后接下来考虑限制的情况。发现正着考虑不超过限制的情况不太好做，正难则反。
我们考虑超过限制的情况。超过限制就是第 $i$ 个硬币强制选 $d_{i} + 1$ 个，剩下的依然随便选，那么情况数就是 $dp_{s - (d_{i} + 1) \times c_{i}}$ ，答案就要减去 $\sum\limits_{i = 1}^{4}dp_{s - (d_{i} + 1) \times c_{i}}$ 。这是单个硬币超出限制的情况，如果有多个硬币，就得请出我们的容斥原理了。但是，容斥原理的公式要求任意两个集合的交集和并集大小相等，这很明显不相等啊，我们又发现：只有 $4$ 种硬币，那我们直接枚举不就行了吗？无非就是带一个 $16$ 的常数嘛。

核心代码：

1
int ans = dp[s];//dp是预处理好的完全背包
2
for (int k = 1; k < (1 << 4); k++)
3
{
4
    int tmp = s;
5
    for (int i = 0; i < 4; i++)
6
        if (k & (1 << i))
7
            tmp -= (d[i] + 1) * c[i];
8
    if (tmp >= 0)
9
        ans += (__builtin_popcount(k) & -1 : 1) * dp[tmp];//容斥
10
}

P5505 [JSOI2011] 分特产↗

还是一道很板的二项式反演。首先设 $f_{i}$ 表示至少有 $i$ 个同学没有拿到特产的方案数，那么有：

f_{i} = \binom{n}{i} \times \prod\limits_{j}^{m}\binom{a_{j} + n - i - 1}{n - i - 1}

后面那坨表示将 $a_{j}$ 个物品分成 $n - i$ 个可空集的方案数，而前面的是因为我们并没有钦定哪几个人没有，所以要乘一个在 $n$ 个人里面选 $i$ 个的方案数。

接下来我们开始反演。设 $g_{i}$ 表示正好有 $i$ 个人没有，那么有反演公式：

g_{i} = \sum\limits_{j = i}^{n}(-1)^{j - i}\binom{j}{i}f_{j}

而我们要让每一个人都拿到，答案就是 $g_{0}$ 。这样，我们就做完了。时间复杂度 $\mathcal{O}(n)$

P6521 [CEOI2010 day2] pin↗

发现考虑不同的方案数有点难，正难则反。
依然先考虑“至少”。我们设 $cnt_i$ 为至少有 $i$ 位相同的方案数。这个可以用哈希求解。我们设哈希函数：

1
int hsh(char ch){return isdigit(ch) ? ch - '0' : ch - 'a' + 10;}
2
int hsh(char ch1,char ch2){return hsh(ch1) * 36 + hsh(ch2);}
3
int hsh(char ch1,char ch2,char ch3)
4
{return hsh(ch1) * 36 * 36 + hsh(ch2) * 36 + hsh(ch3);}

分别用于求解一个字符，两个字符，三个字符的哈希值。很明显，这个哈希函数生成的哈希值不会超过 $6 \times 10 ^ 4$ 。那么我们记录 $tmp_{i}$ 表示有多少个字符序列的哈希值是 $i$ ，然后要求解方案数呢，就相当于求解“在 $tmp_{i}$ 个元素里随便取两个不同元素的方案数”，很明显是 $\frac{tmp_{i} \times (tmp_{i} - 1)}{2}$ 。最后，我们求得了至少有 $i$ 个元素相同的方案数，因为最多有 $4$ 个元素相同，所以我们直接暴力容斥就行。

code:

1
for (int x = 1; x <= 4; x++)//一个字符相同的
2
{
3
    memset(tmp,0,sizeof tmp);
4
    for (int i = 1; i <= n; i++)
5
        tmp[hsh(s[i][x])] ++;
6
    for (int i = 0; i <= 6e4; i++)
7
        cnt[1] += (tmp[i] * (tmp[i] - 1)) >> 1;
8
}
9
for (int x = 1; x <= 4; x++)//两个字符相同
10
{
11
    for (int y = x + 1; y <= 4; y++)
12
    {
13
        memset(tmp,0,sizeof tmp);
14
        for (int i = 1; i <= n; i++)
15
            tmp[hsh(s[i][x],s[i][y])] ++;
16
        for (int i = 0; i <= 6e4; i++)
17
            cnt[2] += (tmp[i] * (tmp[i] - 1)) >> 1;
18
    }
19
}
20
for (int x = 1; x <= 4; x++)//三个字符相同
21
{
22
    for (int y = x + 1; y <= 4; y++)
23
    {
24
        for (int z = y + 1; z <= 4; z++)
25
        {
26
            memset(tmp,0,sizeof tmp);
27
            for (int i = 1; i <= n; i++)
28
                tmp[hsh(s[i][x],s[i][y],s[i][z])] ++;
29
            for (int i = 0; i <= 6e4; i++)
30
                cnt[3] += (tmp[i] * (tmp[i] - 1)) >> 1;
31
        }
32
    }
33
}
34
//以下是暴力容斥
35
ans[3] = cnt[3];
36
ans[2] = cnt[2] - 3 * ans[3];
37
ans[1] = cnt[1] - ans[2] * 2 - ans[3] * 3;
38
ans[0] = ((n * (n - 1)) >> 1) - ans[1] - ans[2] - ans[3];
39
printf("%lld",ans[4 - d]);//由于求解的是相同的，所以不同的就是4 - d个

P10597 BZOJ4665 小 w 的喜糖↗

依然是正难则反+二项式反演 ~~演都不带演~~

还是从“至少”做起。设 $f_{i}$ 表示至少有 $i$ 个位置相同， $g_{i}$ 表示正好 $i$ 个位置相同。那么有反演：

f_{i} = \sum\limits_{j = n}^{m}\binom{j}{n}g_{j} \Longleftrightarrow g_{i} = \sum\limits_{j = n}^{m}(-1)^{i - n}\binom{j}{n}f_{j}

我们的答案就是 $g_{0}$

现在的问题就在于怎么求 $f_{i}$ 。发现初始数组的顺序对于答案来说没有影响，那么我们就记录每种颜色的数量并去重，然后开始 dp。设 $dp_{i,j}$ 表示循环到第 $i$ 个颜色，钦定有 $j$ 个元素相同的方案数。那么有

dp_{i,j} = \sum\limits_{k = 0}^{\min(cnt_{i},tmp)}dp_{i - 1,j - k} \times \binom{cnt_{i}}{k} \times \binom{tmp - j}{cnt_{i} - k}

很明显， $f_{i} = dp_{m,i}$ ，其中 $m$ 表示颜色总数。然后我们就得出了答案，时间复杂度为 $\mathcal{O}(n^2)$ 。

code:

1
sort(a + 1,a + n + 1);
2
int m = unique(a + 1,a + n + 1) - a - 1,tmp = 0;
3
dp[0][0] = 1;
4
for (int i = 1; i <= m; i++)
5
{
6
    tmp += cnt[a[i]];
7
    for (int j = 0; j <= tmp; j++)
8
        for (int k = 0; k <= min(j,cnt[a[i]]); k++)
9
            dp[i][j] = (dp[i][j] + dp[i - 1][j - k] * c(tmp - j,cnt[a[i]] - k) % mod * c(cnt[a[i]],k) % mod) % mod;
10
}
11
int ans = 0;
12
for (int i = 0; i <= n; i++)
13
    ans = ((ans + (i & 1 ? -1 : 1) * dp[m][i]) % mod + mod) % mod;

P2567 [SCOI2010] 幸运数字↗

我们看完题先看数据范围： $1 \le a \le b \le 10^{10}$ ，直接枚举肯定不现实，我们看：欸☝，数位 dp。你要是这么想，那么恭喜你，跑偏了。

直接枚举每一个数不现实，那么我就枚举每个幸运号码呗，虽然也不现实，但是好歹比直接枚举每一个快吧。枚举每一个幸运号码，然后把是它倍数的都计算一下，可以证明 $10^{10}$ 范围内的幸运号码不是很多，枚举的完。然后我们不出意外的发现，他 WA 了，究其原因是有些算重了。现在就该我们容斥出场了。发现第 $i$ 个属性就是能不能被第 $i$ 个幸运号码整除。设第 $i$ 个号码为 $x$ ，那么 $|S_{i}| = \lfloor \frac{b}{x} \rfloor - \lceil \frac{a}{x}\rceil$ ，直接套公式容斥就好了。但是这样还是过不了。我们发现当有一个幸运号码是其他幸运号码的倍数时，这个幸运号码没有贡献。 ~~用脚趾都想的出来~~

注意要开 __int128

1
#include<bits/extc++.h>
2
#define int __int128
3
#define lcm(x,y) (x == 0 ? y : x * y / __gcd(x,y))
4
using namespace std;
5
void read(int &x)
6
{
7
    x = 0;
8
    short f = 1;
9
    char ch = getchar();
10
    while (!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
11
    while (isdigit(ch)){x = x * 10 + ch - '0'; ch = getchar();}
12
    x *= f;
13
}
14
void write(int x)
15
{
16
    if (x > 9)
17
        write(x / 10);
18
    putchar(x % 10 + '0');
19
}
20
int a,b,ans;
21
map<vector<int>::iterator,bool>vis;
22
vector<int>pending,num;
23
void dfs1(int x)
24
{
25
    if (x > b)
26
        return;
27
    if (x)
28
        pending.push_back(x);
29
    dfs1(x * 10 + 6);
30
    dfs1(x * 10 + 8);
31
}
32
void dfs2(vector<int>::iterator idx,int cnt,int x)
33
{
34
    if (x > b)
35
        return;
36
    if (idx == num.end())
37
    {
38
        if (x == 0)
39
            return;
40
        ans += (cnt & 1 ? 1 : -1) * (floor(1.0 * b / x) - ceil(1.0 * a / x) + 1);
41
        return;
42
    }
43
    dfs2(idx + 1,cnt + 1,lcm(x,*idx));
44
    dfs2(idx + 1,cnt,x);
45
}
46
signed main()
47
{
48
    read(a),read(b);
49
    dfs1(0);
50
    for (auto i = pending.begin(); i != pending.end(); i++)
51
    {
52
        if (!vis[i])
53
            num.push_back(*i);
54
        for (auto j = i + 1; j != pending.end(); j++)
55
            if (*j % *i == 0)
56
                vis[j] = 1;
57
    }
58
    sort(num.begin(),num.end(),greater<int>());
59
    dfs2(num.begin(),0,0);
60
    write(ans);
61
    return 0;
62
}

P8737 [蓝桥杯 2020 国 B] 质数行者↗

题解↗里说：

看到题目限制不能经过给定的两个点，自然想到容斥。

至于怎么自然而然想到容斥，我也不知道。多做点题就好了。

设 $dp(a,b)$ 表示从 $a(x_{1},y_{1},z_{1})$ 走到 $b(x_{2},y_{2},z_{2})$ 的方案数。设 $st(1,1,1),en(n,m,w)$ ， $p_{1},p_{2}$ 分别为不能走到的两个点。那么根据容斥原理，有：

\begin{aligned} ans & = dp(st,en) \\ & - dp(st,p_{1}) \times dp(p_{1},en) \\ & - dp(st,p_{2}) \times dp(p_{2},en) \\ & + dp(st,p_{1}) \times dp(p_{1},p_{2}) \times dp(p_{2},en) \end{aligned}

现在我们想：如何计算 $dp(a,b)$ 。我们看，麻烦之处在于只能走质数格，考虑没有这个限制如何做。类似二维的方法： $dp(a,b) = \binom{\Delta x + \Delta y + \Delta z}{\Delta x} \times \binom{\Delta y + \Delta z}{\Delta y}$ ，意义很好理解，这里就不说了。

现在再考虑烦人的质数限制。发现一步走多远不重要，重要的是走这么远要多少步。设 $f_{i,j}$ 表示用 $j$ 个质数走 $i$ 格的方案数，那么这就是一个完全背包：

f_{i,j} = \sum\limits_{k \in pr}^{k \le i}f_{i - k,j - 1}

其中 $pr$ 表示质数集合。因为 $i$ 最大只有 $3000$ ， $3000$ 以内的质数也没有 $1000$ 个，所以预处理的时间是可以过的。

那依据此，我们得到了：

dp(a,b) = \sum\limits_{i = 1}^{\Delta x}\sum\limits_{j = 1}^{\Delta y}\sum\limits_{k = 1}^{\Delta z}\binom{i + j + k}{i}\binom{j + k}{j}f_{\Delta x,i}f_{\Delta y,j}f_{\Delta z,k}

时间复杂度 $\mathcal{O}(nmw)$ 。~~立即发生爆炸~~

我们看这三个 $\sum$ 就不顺眼，想想能不能优化掉一个。
我们看能不能在枚举 $i$ 的同时计算 $j$ 呢？好像可以。设 $sum = i + j$ ，那么有：

\begin{aligned} dp(a,b) & = \sum\limits_{i = 0}^{\Delta x}\sum\limits_{j = 0}^{\Delta y}\sum\limits_{k = 0}^{\Delta z}\frac{(i + j + k)!}{i! \times j! \times k!}f_{\Delta x,i}f_{\Delta y,j}f_{\Delta z,k} \\ & = \sum\limits_{i = 0}^{\Delta x}\sum\limits_{j = 0}^{\Delta y}\sum\limits_{k = 0}^{\Delta z}(i + j + k)! \times \frac{f_{\Delta x,i}}{i!} \times \frac{f_{\Delta y,j}}{j!} \times \frac{f_{\Delta z,k}}{k!} \\ & = \sum\limits_{sum = 0}^{\Delta x + \Delta y}\sum\limits_{i = 0}^{sum}\frac{f_{\Delta x,i}}{i!} \times \frac{f_{\Delta y,sum - i}}{(sum - i)!}\sum\limits_{k = 0}^{\Delta z}(sum + k)! \times \frac{f_{\Delta z,k}}{k!} \end{aligned}

时间复杂度 $\mathcal{O}(n(m + w))$ ，就可以过了。

code:

1
#include<bits/extc++.h>
2
#define int long long
3
#define Inv(x) binpow(x,mod - 2)
4
using namespace std;
5
const int maxn = 3005;
6
const int mod = 1e9 + 7;
7
int n,m,w;
8
int fac[maxn],inv[maxn];
9
int f[maxn][maxn];
10
bool ipr[maxn];
11
vector<int>pr;
12
struct node
13
{
14
    int x,y,z;
15
}st,en,p1,p2;
16
int binpow(int x,int y)
17
{
18
    int ret = 1;
19
    while (y)
20
    {
21
        if (y & 1)
22
            ret = ret * x % mod;
23
        x = x * x % mod;
24
        y >>= 1;
25
    }
26
    return ret;
27
}
28
void init()
29
{
30
    for (int i = 2; i <= 3000; i++)
31
    {
32
        if (!ipr[i])
33
            pr.push_back(i);
34
        for (auto j = pr.begin(); j != pr.end() && *j * i <= 3000; j++)
35
        {
36
            ipr[*j * i] = 1;
37
            if (i % *j == 0)
38
                break;
39
        }
40
    }
41
    int up = max(max(n,m),w);
42
    f[0][0] = 1;
43
    for (int i = 1; i <= up; i++)
44
        for (int j = 1; j <= i >> 1; j++)
45
            for (auto k = pr.begin(); k != pr.end() && *k <= i; k++)
46
                f[i][j] = (f[i][j] + f[i - *k][j - 1]) % mod;
47
    up *= 3;
48
    fac[0] = 1;
49
    for (int i = 1; i <= up; i++)
50
        fac[i] = fac[i - 1] * i % mod;
51
    inv[up] = Inv(fac[up]);
52
    for (int i = up - 1; i >= 0; i--)
53
        inv[i] = inv[i + 1] * (i + 1) % mod;
54
}
55
int dp(node x,node y)
56
{
57
    int dx = y.x - x.x;
58
    int dy = y.y - x.y;
59
    int dz = y.z - x.z;
60
    if (dx < 0 || dy < 0 || dz < 0)
61
        return 0;
62
    int ret = 0;
63
    for (int sum = 0; sum <= (dx >> 1) + (dy >> 1); sum++)
64
    {
65
        int sum1 = 0;
66
        for (int i = 0; i <= sum; i++)
67
            if (int j = sum - i; i <= (dx >> 1) && j <= (dy >> 1))
68
                sum1 = (sum1 + f[dx][i] * inv[i] % mod * f[dy][j] % mod * inv[j] % mod) % mod;
69
        int sum2 = 0;
70
        for (int k = 0; k <= (dz >> 1); k++)
71
            sum2 = (sum2 + f[dz][k] * inv[k] % mod * fac[sum + k] % mod) % mod;
72
        ret = (ret + sum1 * sum2 % mod) % mod;
73
    }
74
    return ret;
75
}
76
signed main()
77
{
78
    scanf("%lld%lld%lld",&n,&m,&w);
79
    st = {1,1,1};
80
    en = {n,m,w};
81
    scanf("%lld%lld%lld",&p1.x,&p1.y,&p1.z);
82
    scanf("%lld%lld%lld",&p2.x,&p2.y,&p2.z);
83
    init();
84
    if (p2.x <= p1.x && p2.y <= p1.y && p2.z <= p1.z)
85
    swap(p1, p2);
86
    int ans1 = dp(st,en);
87
    int ans2 = dp(st,p1) * dp(p1,en) % mod;
88
    int ans3 = dp(st,p2) * dp(p2,en) % mod;
89
    int ans4 = dp(st,p1) * dp(p1,p2) % mod * dp(p2,en) % mod;
90
    int ans = (((ans1 + ans4) % mod - (ans2 + ans3) % mod) % mod + mod) % mod;
91
    printf("%lld",ans);
92
    return 0;
93
}

Thanks for reading!

日记

周二 12月 31 2024

3253 字 · 18 分钟

life 日记

日记

P10986 [蓝桥杯 2023 国 Python A] 2023↗

BZOJ2839 集合计数↗

P1450 [HAOI2008] 硬币购物↗

P5505 [JSOI2011] 分特产↗

P6521 [CEOI2010 day2] pin↗

P10597 BZOJ4665 小 w 的喜糖↗

P2567 [SCOI2010] 幸运数字↗

P8737 [蓝桥杯 2020 国 B] 质数行者↗

日记