伊埃斯的小站
日记

日记

Tue Dec 31 2024
19 分钟
life 日记
3285 字

我是耐断更王。

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

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

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

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

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

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

设 gmg_m 表示恰好有 mm 个 2023 的方案数，那么有：

fm=∑i=mn(im)gif_m = \sum\limits_{i = m}^{n}\binom{i}{m}g_i

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

gm=∑i=mn(−1)i−m(im)fig_m = \sum\limits_{i = m}^{n}(-1)^{i - m}\binom{i}{m}f_i

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

BZOJ2839 集合计数#

还是由“至少”转到“恰好”。

设 fkf_{k} 表示钦定有 kk 个相同元素的情况，那么，剩下的 n−kn - k 个元素能够组成 2n−k2^{n - k} 个集合，而，这 2n−k2^{n - k} 个集合又能够再组成 22n−k2^{2^{n - k}} 个集合。那么显然有

fk=(nk)22n−kf_{k} = \binom{n}{k}2^{2^{n - k}}

设 gkg_{k} 表示恰好有 kk 个相同元素的情况，那么有：

fk=∑i=kn(ik)gif_{k} = \sum\limits_{i = k}^{n}\binom{i}{k}g_{i}

反演一下得到：

gk=∑i=kn(−1)i−k(ik)fig_{k} = \sum\limits_{i = k}^{n}(-1)^{i - k}\binom{i}{k}f_{i}

我们就得到了 gkg_{k}。时间复杂度 O(n)\mathcal{O}(n)。

P1450 [HAOI2008] 硬币购物#

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

核心代码：

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

P5505 [JSOI2011] 分特产#

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

fi=(ni)×∏jm(aj+n−i−1n−i−1)f_{i} = \binom{n}{i} \times \prod\limits_{j}^{m}\binom{a_{j} + n - i - 1}{n - i - 1}

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

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

gi=∑j=in(−1)j−i(ji)fjg_{i} = \sum\limits_{j = i}^{n}(-1)^{j - i}\binom{j}{i}f_{j}

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

P6521 [CEOI2010 day2] pin#

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

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

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

code:

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

P10597 BZOJ4665 小 w 的喜糖#

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

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

fi=∑j=nm(jn)gj⟺gi=∑j=nm(−1)i−n(jn)fjf_{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}

我们的答案就是 g0g_{0}

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

dpi,j=∑k=0min⁡(cnti,tmp)dpi−1,j−k×(cntik)×(tmp−jcnti−k)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}

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

code:

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

P2567 [SCOI2010] 幸运数字#

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

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

注意要开 __int128

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

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

题解里说：

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

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

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

ans=dp(st,en)−dp(st,p1)×dp(p1,en)−dp(st,p2)×dp(p2,en)+dp(st,p1)×dp(p1,p2)×dp(p2,en)\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)。我们看，麻烦之处在于只能走质数格，考虑没有这个限制如何做。类似二维的方法：dp(a,b)=(Δx+Δy+ΔzΔx)×(Δy+ΔzΔy)dp(a,b) = \binom{\Delta x + \Delta y + \Delta z}{\Delta x} \times \binom{\Delta y + \Delta z}{\Delta y}，意义很好理解，这里就不说了。

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

fi,j=∑k∈prk≤ifi−k,j−1f_{i,j} = \sum\limits_{k \in pr}^{k \le i}f_{i - k,j - 1}

其中 prpr 表示质数集合。因为 ii 最大只有 30003000，30003000 以内的质数也没有 10001000 个，所以预处理的时间是可以过的。

那依据此，我们得到了：

dp(a,b)=∑i=1Δx∑j=1Δy∑k=1Δz(i+j+ki)(j+kj)fΔx,ifΔy,jfΔz,kdp(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}

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

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

dp(a,b)=∑i=0Δx∑j=0Δy∑k=0Δz(i+j+k)!i!×j!×k!fΔx,ifΔy,jfΔz,k=∑i=0Δx∑j=0Δy∑k=0Δz(i+j+k)!×fΔx,ii!×fΔy,jj!×fΔz,kk!=∑sum=0Δx+Δy∑i=0sumfΔx,ii!×fΔy,sum−i(sum−i)!∑k=0Δz(sum+k)!×fΔz,kk!\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}

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

code:

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