首页 > 其他分享 >2024牛客多校Bit Common & Bit More Common

2024牛客多校Bit Common & Bit More Common

时间：2024-07-26 19:06:23浏览次数：7  
标签：twoFang ll 多校 Common 序列 Bit rep dp mod

A Bit Common

时间限制：3s(C++/C) / 6s
内存限制：1048576K(C++/C) / 2097152K

题目描述

Given two integers \(n\) and \(m\), among all the sequences containing \(n\) non-negative integers less than \(2^m\), you need to count the number of such sequences \(A\) that there exists a non-empty subsequence of \(A\) in which the bitwise AND of the integers is \(1\).

Note that a non-empty subsequence of a sequence \(A\) is a non-empty sequence that can be obtained by deleting zero or more elements from \(A\) and arranging the remaining elements in their original order.

Since the answer may be very large, output it modulo a positive integer \(q\).

The bitwise AND of non-negative integers \(A\) and \(B\), \(A\ \texttt{AND}\ B\) is defined as follows:

  • When \(A\ \texttt{AND}\ B\) is written in base two, the digit in the \(2^d\)'s place (\(d \ge 0\)) is \(1\) if those of \(A\) and \(B\) are both \(1\), and \(0\) otherwise.

For example, we have \(4\ \texttt{AND}\ 6\) = \(4\) (in base two: \(100\ \texttt{AND}\ 110\) = \(100\)).

Generally, the bitwise AND of \(k\) non-negative integers \(p_1, p_2, \ldots, p_k\) is defined as \((\ldots((p_1\ \texttt{AND}\ p_2)\ \texttt{AND}\ p_3)\ \texttt{AND}\ \ldots\ \texttt{AND}\ p_k)\)
and we can prove that this value does not depend on the order of \(p_1, p_2, \ldots, p_k\).

输入描述

The only line contains three integers \(n\) (\(1 \le n \le 5\,000\)), \(m\) (\(1 \le m \le 5\,000\)) and \(q\) (\(1 \le q \le 10^9\)).

输出描述

Output a line containing an integer, denoting the answer.

示例1

输入

2 3 998244353

输出

17

示例2

输入

5000 5000 998244353

输出

2274146

笔者翻译

给你两个整数\(n\)和\(m\),找一个长度为\(n\)的序列，序列中的每个元素（正整数）都小于\(2^m\),并且这个序列中存在一段子序列使得子序列的所有元素的按位与为\(1\)，请问这样的序列有多少种，由于答案特别大需要对\(q\)取模布拉布拉......

思路

关键词：按位与，小于\(2^m\)。
不难想到这道题中出现的数字不能简单的当成十进制的数字来看，当成二进制数来看比较合适。也就是说，每一个元素都当作一个长度为\(m\)的矩阵来看会比较合适。

存在一段子序列使得子序列所有的元素的按位与为\(1\)，假设这段子序列的长度为\(k\),这k个数在二进制表示中的最后一位必须都是\(1\)（有的题解中会说是奇数），这样才能保证最后一位按位与之后会得到\(1\)而不是\(0\)（如果有任何一个元素的最后一个元素存在\(0\)，那么最后按位与得到的数一定是\(0\)）。我们不妨把这k个元素合在一起看成一个k行m列的矩阵，基于上述理论，这个矩阵的第m列也就是最后一列中的所有元素都为1；而对于前m-1列来说，每一列的按位与都必须为0（和最后一列的情况恰恰相反），也就是说每一列中至少有一个元素为0。每一列所有可能的情况有\(2^k\)种，除去全为1的情况，前\(m-1\)每一列都有\((2^k-1)\)种情况，\(m-1\)列就有\((2^k-1)^{m-1}\)

下面的这张图或许能帮助你更好的理解

对于没有被选种的\(n-k\)个元素来说，每个元素的最后一位必须是\(0\)，前\(m-1\)位可以随便，故有$2^{(n-k)\times(m-1)} $种情况。把上面的答案综合在一起，同时由于从n个元素中选择k个元素的时候需要进行一次排列组合，就是说乘以 \(C_n^{k}\).

那么显而易见的，最后的答案就是：\(\sum_{k=1}^{n} \left( C_n^k (2^k - 1)^{m-1} 2^{(n-k) (m-1)} \right)\)

具体的代码实现细节

其实式子列到这个地方，这道题的关键部分就已经结束了，剩下的都是些写代码的无关紧要的小事罢。不过我还是说一些我觉得可以优化的地方。
首先是求组合数的时候，如果每个循环都单独求一次组合数，未免太浪费时间了，比较常用的做法是在主程序开始之前就用\(O(n^2)\)把所有需要的组合数算完，需要的时候\(O(1)\)查询，这样会快的很多。计算组合数的时候我们需要使用公式\(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\).用代码具体实现的话就是

 rep(i, 0, 5004) _rep(j, 0, i) if (!j) c[i][j] = 1;
    else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    //把C[i][0]标记为1，其他的用公式递推
    //rep是for循环但是i<,_rep是i<=,下同

式子中还有很多求幂的地方，使用快速幂来优化

ll binpow(ll a, ll b, ll m)
{
    a %= m;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

同时，式子中出现了许多求2的次方的地方，虽然使用快速幂可以在\(O(log)\)内完成计算，但如果我们事先把2的所有次方用\(O(nm)\)跑完，最后只需要\(O(1)\)来进行查询，用代码实现就是

twoFang[0] = 1;
_rep(i, 1, 25000006)
    twoFang[i] = twoFang[i - 1] * 2 % mod;

最后只需要代入一点点算就行了

 _rep(i, 1, n)
    {
        ll cnk = c[n][i];
        ll temp = cnk * binpow((twoFang[i] - 1), m - 1, mod) % mod;
        temp = temp * twoFang[(n - i) * (m - 1)] % mod;
        ans = (ans + temp) % mod;
    }

第一问完整代码

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define endl '\n'
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define Forget_that return
#define Just_go 0
#define Endl endl
#define ednl endl
#define eldn endl
#define dnel endl
#define enndl endl
#define Ednl endl
#define Edml endl
#define llmax 9223372036854775807
#define intmax 2147483647

int n;
ll mod;
ll twoFang[30000007];
ll c[5005][5005];

ll binpow(ll a, ll b, ll m)
{
    a %= m;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll n, m;
    cin >> n >> m;
    cin >> mod;

    rep(i, 0, 5004) _rep(j, 0, i) if (!j) c[i][j] = 1;
    else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

    twoFang[0] = 1;
    _rep(i, 1, 30000006)
        twoFang[i] = twoFang[i - 1] * 2 % mod;

    ll ans = 0;

    _rep(i, 1, n)
    {
        ll cnk = c[n][i];
        ll temp = cnk * binpow((twoFang[i] - 1), m - 1, mod) % mod;
        temp = temp * twoFang[(n - i) * (m - 1)] % mod;
        ans = (ans + temp) % mod;
    }

    cout << ans;

    Forget_that Just_go;
}

没有时间为第一问的解决感到开心，接下来到场的是第二问Orz

A-A Bit More Common

时间限制：3s(C++/C) / 6s
内存限制：1048576K(C++/C) / 2097152K

题目描述

Given two integers \(n\) and \(m\), among all the sequences containing \(n\) non-negative integers less than \(2^m\), you need to count the number of such sequences \(A\) that there exists two different non-empty subsequences of \(A\) in each of which the bitwise AND of the integers is \(1\).

Note that a non-empty subsequence of a sequence \(A\) is a non-empty sequence that can be obtained by deleting zero or more elements from \(A\) and arranging the remaining elements in their original order. Two subsequences are different if they are composed of different locations in the original sequence****.

Since the answer may be very large, output it modulo a positive integer \(q\).

The bitwise AND of non-negative integers \(A\) and \(B\), \(A\ \texttt{AND}\ B\) is defined as follows:

  • When \(A\ \texttt{AND}\ B\) is written in base two, the digit in the \(2^d\)'s place (\(d \ge 0\)) is \(1\) if those of \(A\) and \(B\) are both \(1\), and \(0\) otherwise.

For example, we have \(4\ \texttt{AND}\ 6\) = \(4\) (in base two: \(100\ \texttt{AND}\ 110\) = \(100\)).

Generally, the bitwise AND of \(k\) non-negative integers \(p_1, p_2, \ldots, p_k\) is defined as
\((\ldots((p_1\ \texttt{AND}\ p_2)\ \texttt{AND}\ p_3)\ \texttt{AND}\ \ldots\ \texttt{AND}\ p_k)\)
and we can prove that this value does not depend on the order of \(p_1, p_2, \ldots, p_k\).

示例1

输入

2 3 998244353

输出

7

示例2

输入

5000 5000 998244353

输出

530227736

笔者翻译

这一题和第一问不同的地方在于，第一问只需要找到序列中含有子序列满足题意的数列，第二问要求找到序列中存在两个子序列，使得子序列的所有元素的按位与为\(1\)，求这样的序列有多少种。一言以蔽之，第一问对于特殊的子序列的数量没有要求，第二问要求至少存在两个子序列满足题目的要求。

思路

都把第一问写完了，这第一问肯定不是白写的啊，我们不难发现，如果记序列中只含有一个子序列使得子序列的所有元素的按位与为1的序列数量为\(ans2\)的话，那么上一问的答案减去\(ans2\)就是这道题的答案。
所以，这道题的重点就成了求序列中只含有一个子序列使得子序列的所有元素的按位与为1的序列数量。

一样的，我们设该序列的这段子序列的长度为\(k\)，这段子序列的所有元素的最后一位二进制必须为\(1\)。对于前面的\(k\)行\(m-1\)列，我们必须满足这样一条性质：每一行都有\(0\)，且每一行都存在一个\(0\)，这个\(0\)是这一列中的唯一一个\(0\)；并且每一列中都有\(0\). 如此，假如删去任意一个元素（删除任意一行），将其他的元素按位与，都会至少在某一列中出现一个\(1\)（因为每一个都存在一个\(0\)使得这个\(0\)是这一列中唯一的一个\(0\)）.那么这段子序列就是符合要求的，因为这个子序列不存在一个子序列使得其元素按位与为1.也就是说，这个子序列是这个序列中唯一一个满足题意的子序列。

特别的，当这段子序列长度为\(1\)时，由于其不存在子序列，所以需要分开来单独讨论。我们不难发现，如果，这个子序列长度为\(1\)，为了满足条件，这个子序列中的唯一一个元素只能是\(1\).这个子序列从\(n\)个元素中选出，就是\(C_n^1 \times\ 1\)

剩下的，我们只需要找到满足下面性质的矩阵数量就行了

  • \(k\)行\(m-1\)列
  • 矩阵中的元素不是\(1\)就是\(0\)
  • 每行都有\(0\)是这一列中唯一一个\(0\)
  • 每行可以有很多\(0\)
  • 每一列都必须有一个0

不难发现，这个矩阵按列进行划分，可以划分成两种列

  1. 每一列含有两个以上包括两个的0
  2. 每一列只有一个0，同时所有的这些列的0会在矩阵的所有k行中出现（矩阵的每一行都有这些0中的某些）

我们设第二种情况的列有\(t\)列，相应的，第一种情况的列有\(m-1-t\)

首先对于第一种情况

对于每一列来说都有\(2^{k}\)种情况，除去一列里面全是1的情况有\(2^{k}-1\)种情况，再除去每一列种含有1个0的情况就是我们需要的答案为\(2^{k}-1-k\).由于这样的列共有\(m-1-t\)列，则共有\((2^{k}-1-k)^{m-1-t}\)种情况。

接着对于第二种情况

直接计算会有点麻烦，读者不妨自己试一下，这里我使用大家都推荐的一种方法---动态规划
我们设满足下面条件的矩阵的数量为\(dp_{ij}\)

  • i行j列
  • 每一列都只有1个0（这些0出现在所有的i行中）
  • 每一行都有0

先说结论：\(dp_{ij}=i\times\ (dp_{i-1j-1}+dp_{ij-1})\)

解释

总体思想就是：第j列的状态可以从第j-1列转化过来。
对于i行j-1列的满足条件的矩阵，可以在最右侧加入第j列，在第j列i行中的任意一行中填一个0，其他的地方填上1就可以使得新的到的这个i行j列的矩阵满足要求（i行共i种）。下面的图可能会更方便理解一些：

如图所示，将一个$3\times3$的满足题意的矩阵按照上述方式可以得到一个$3\times4$的满足题意的矩阵，这个矩阵的前3列组成的矩阵就已经满足题意。
同时，有一种前3列组成的矩阵并不满足题意的情况，即从i-1行j-1列的满足题意的矩阵转移来。
对于一个i-1行j-1列的满足题意的矩阵，我们首先在最右侧扩充第j列，并在任意行添加第一行，在这一行的最右列填上0，其他地方填上1即可。（由于共有i行，所以添加任意一行的添法共有i种）。下面的这张图可能会更方便您理解一点

如图所示，将一个$2\times3$的满足题意的矩阵变成了三个$3\times4$的满足题意的矩阵，由于前3列所组成的矩阵并不满足题意，所以显然的，这种情况和上一种情况是相互独立的。

故而\(dp_{ij}=i\times\ (dp_{i-1j-1}+dp_{ij-1})\)

综上所述，共有\(\sum_{k=2}^{n} C_n^k \sum_{t=k}^{m-1} C_{m-1}^t (2^k - k - 1)^{m-1-t} dp_{kt} + C_n^1 2^{(n-1)(m-1)}\)
最后拿第一问的答案减去上面这个就行了。

具体的代码实现细节

首先是那个动态规划的部分

  dp[1][1] = 1;
  dp[0][0] = 1;
  _rep(i, 1, 5003) _rep(j, i, 5003)
     dp[i][j] = i * (dp[i - 1][j - 1] + dp[i][j - 1]) % mod;

当子序列长度为1时的特殊情况

 ans = (((ans - n * twoFang[(n - 1) * (m - 1)] % mod) % mod) + mod) % mod;

对于非特殊情况的求解

    _rep(k, 2, n)
    {
        ll temp = c[n][k];
        ll suffix = 0;
        ll btm = 1;
        for (int t = m - 1; t >= k; t--)
        {
            ll mark = c[m - 1][t];
            mark = mark * btm % mod;
            mark = mark * dp[k][t] % mod;
            suffix = (suffix + mark) % mod;
            btm = btm * (twoFang[k] - k - 1) % mod;
        }
        temp = temp * suffix % mod * twoFang[(n - k) * (m - 1)] % mod;
        ans = ((ans - temp) % mod + mod) % mod;
    }

这里有一点需要注意，笔者在第一次写的时候，求\((2^k - k - 1)^{m-1-t}\)的时候用的是快速幂，但是给时间复杂度增加了一个\(log\)，不出意外的超时了。解决办法就是，从\(m-1\)开始算，算到\(k\)；而不是从\(k\)算到\(m-1\)，每次用\(btm\)存储那个幂数，每次对\(btm\)乘$(2^k-k- 1) $ .如此时间复杂度少了一个\(log\)，完美地解决了问题。

完整代码

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define endl '\n'
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define Forget_that return
#define Just_go 0
#define Endl endl
#define ednl endl
#define eldn endl
#define dnel endl
#define enndl endl
#define Ednl endl
#define Edml endl
#define llmax 9223372036854775807
#define intmax 2147483647

int n;
ll mod;
ll twoFang[30000007];
ll c[5005][5005];
ll dp[5005][5005];

ll binpow(ll a, ll b, ll m)
{
    a %= m;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    ll n, m;
    cin >> n >> m;
    cin >> mod;

    rep(i, 0, 5004) _rep(j, 0, i) if (!j) c[i][j] = 1;
    else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

    twoFang[0] = 1;
    _rep(i, 1, 25000006)
        twoFang[i] = twoFang[i - 1] * 2 % mod;

    ll ans = 0;

    _rep(i, 1, n)
    {
        ll cnk = c[n][i];
        ll temp = cnk * binpow((twoFang[i] - 1), m - 1, mod) % mod;
        temp = temp * twoFang[(n - i) * (m - 1)] % mod;
        ans = (ans + temp) % mod;
    }

    ans = (((ans - n * twoFang[(n - 1) * (m - 1)] % mod) % mod) + mod) % mod;

    dp[1][1] = 1;
    dp[0][0] = 1;
    _rep(i, 1, 5003) _rep(j, i, 5003)
        dp[i][j] = i * (dp[i - 1][j - 1] + dp[i][j - 1]) % mod;

    _rep(k, 2, n)
    {
        ll temp = c[n][k];
        ll suffix = 0;
        ll btm = 1;
        for (int t = m - 1; t >= k; t--)
        {
            ll mark = c[m - 1][t];
            mark = mark * btm % mod;
            mark = mark * dp[k][t] % mod;
            suffix = (suffix + mark) % mod;
            btm = btm * (twoFang[k] - k - 1) % mod;
        }
        temp = temp * suffix % mod * twoFang[(n - k) * (m - 1)] % mod;
        ans = ((ans - temp) % mod + mod) % mod;
    }

    cout << ans;

    Forget_that Just_go;
}

总结

虽然像我这么做，时空复杂度都不小，第二问花了1700多毫秒才过。但是好歹过了。具体的优化可以根据n、m来自主分配所需要的空间和常量。

标签：twoFang,ll,多校,Common,序列,Bit,rep,dp,mod
From： https://www.cnblogs.com/acidbarium/p/18324582

相关文章

  • 2024 牛客多校 4
    https://ac.nowcoder.com/acm/contest/81599gmin(x,y)没写minWA了一发。居然能过样例，应该会报warning但我从来不看。ctrlbackspace还是得看着j读完就会了但做的并不快，当时k还没读k一开始在一棵线段树上分别维护数字和符号，共用一个mdf，比较混乱，还有顺序问题。重构......
  • 2024杭电多校第一场
    菜鸡和大佬队友一起报了暑假的牛客和杭电······然而自己水平完全不够做多少题就是了。1005博弈（hdu7437）好吧赛时根本没写到它（)开始看题以为得一步一步算（是什么让我有这么离谱的思路.jpg），看了官方题解才发现自己的愚蠢呜呜，就是说有没有一种可能，A和B前\(\lfloorn/2\rfloo......
  • 2024牛客暑期多校训练营4
    Preface最赤石的一集，上来先认为D是个煞笔贪心提交了该题的第一发代码并喜提WA后面下机后祁神把L扔给我告诉我就是个煞笔线段树板，结果我写完过不去样例发现题意假了值得一提的是最后发现这两题是这场过的人最少的两题，直接开局给我干的道心破碎之后A题写不来带权并查集样......
  • HDLBits答案（1）_移位寄存器+更多电路
    前言    由于开发板教学内容部分，代码涉及到状态机内容，HDLBits题库只刷到了计数器，因此后续3至4天决定继续刷题，刷完状态机和全部HDLBits题库。今天刷完移位寄存器+更多电路，以下是书写的代码。题库Question1：构建一个4位移位寄存器（右移），具有异步复位、同步加载和使能......
  • 多校数据结构
    多校数据结构省选选手不再需要学习新数据结构，主要需要学习数据结构题目的常见套路，训练代码能力，提升思维能力。因此，此次授课主要提供各种类型的数据结构题目，点拨解题思路，为选手在比赛中处理各类数据结构问题提供参考。[CF1039D]YouAreGivenaTree题目描述有一棵\(n\)个......
  • 求教Postgresql在jdbc处理bit(1)字段的预处理解决方案
    文章目录1.建表语句：2.使用以下方式的预处理方式都报错了3.可以先用sql拼接实现功能1.建表语句：CREATETABLEpublic.h_user( idserial4notnull, usernamevarchar(50)NULL, "password"varchar(64)NULL, nicknamevarchar(60)NULL, emailvarchar(255)N......
  • 2024牛客多校3A Bridging the Gap 2
    希望更丰富的展现？来我搭建的网站看看Problem\(n\)个人乘船过河，该船容纳人的上限为\(R\)，并且需要至少\(L\)个人才能操作。每次过河时所有人都需划船，使船上所有人的耐力值减\(1\)。最初每个人的耐力值为\(h_i\)。判断是否所有人都能过河。\(1\leL<R\len\le5\times10^5......
  • 2024 牛客多校 3
    https://ac.nowcoder.com/acm/contest/81598睡到十点多起床，吃完早饭开打。。。下午倒是不困了，脑子还是不转a有个显然的贪心，没办法加速模拟，1WA1T后给zsy了。这种前期题没秒掉的话还是趁早丢出去吧h随机数据本地1.4s，牛客十连重测，以为卡卡常就行了，最后也没过。看榜很早......
  • 题解：牛客多校第三场 A
    ABridgingtheGap2时间限制：C/C++1秒，其他语言2秒空间限制：C/C++1048576K，其他语言2097152KSpecialJudge,64bitIOFormat:%lld题目描述Agroupof\(n\)walkersarrivesatariverbankatnight.Theywanttocrosstheriverusingaboat,whichisinitiallyont......
  • 题解：2024牛客多校第三场 B
    BCrashTestheader时间限制：C/C++2秒，其他语言4秒空间限制：C/C++1048576K，其他语言2097152K64bitIOFormat:%lld题目描述Afterfiveyears,themosthigh-profileeventinmotorracing,Formula1,returnstoChina.TheChineseGrandPrixwasrecentlyheldatthe......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99