日记

Tue Dec 31 2024

19 分钟

life 日记

3285 字

我是耐断更王。

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

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

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$ 的常数嘛。

核心代码：

CPP

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] 分特产 #

还是一道很板的二项式反演。首先设 $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$ 位相同的方案数。这个可以用哈希求解。我们设哈希函数：

CPP

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

code:

CPP

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 的喜糖 #

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

还是从“至少”做起。设 $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:

CPP

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 \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

CPP

#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)$ 表示从 $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:

CPP

#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;
}

日记

https://nahida.cfd/blog/2024-12-31日记/

日记

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

BZOJ2839 集合计数 #

P1450 [HAOI2008] 硬币购物 #

P5505 [JSOI2011] 分特产 #

P6521 [CEOI2010 day2] pin #

P10597 BZOJ4665 小 w 的喜糖 #

P2567 [SCOI2010] 幸运数字 #

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

日记