广东省住房与城乡建设部网站,学生教育平台入口,学校做网站有些什么好处,网站建设维护宣传正题
题目链接:https://www.luogu.com.cn/problem/CF643F 题目大意
题目有点奇怪就直接放翻译了
有 nnn 只熊和若干桶果汁和恰好一桶酒#xff0c;每一天每只熊会选择一些桶#xff08;可能不选#xff09;并各喝一 杯#xff0c;喝到酒的熊会去睡觉并不再回来#xff…正题
题目链接:https://www.luogu.com.cn/problem/CF643F 题目大意
题目有点奇怪就直接放翻译了
有 nnn 只熊和若干桶果汁和恰好一桶酒每一天每只熊会选择一些桶可能不选并各喝一 杯喝到酒的熊会去睡觉并不再回来通过这个信息熊们想知道哪个桶里是酒。
只有 ppp 个睡 觉的位置当睡觉的熊超过了 ppp 只或者所有熊都在睡觉时熊们就失败了。
令 RiR_iRi 表示在 iii 天内桶的数量最多少使得熊可以成功知道酒的位置。令 Xi(i×Ri)mod232X_i (i\times R_i) \bmod 2^{32}Xi(i×Ri)mod232你需要求出 X1⊕X2⊕…⊕XqX_1 \oplus X_2 \oplus\ldots \oplus X_qX1⊕X2⊕…⊕Xq。
1≤n≤1091\leq n\leq 10^91≤n≤1091≤p≤1301\leq p\leq 1301≤p≤1301≤q≤2×1061\leq q \leq 2\times 10^61≤q≤2×106。 解题思路
之前在XJ杂题选讲时候的神奇题目
题目比较乱但是我们发现题目问的是最多的数量而不是最劣情况下的最多数量所以这个东西是在最优情况下能分辨的数量。
这是我们之前很少接触的一种形式这里需要用到信息的概念因为我们是最优的相当于我们所有的情况都可以去尝试也就是每种信息都可以为我们选出一个答案那么显然我们让选出的这些答案两两不同肯定就是最优的所以这里的RiR_iRi就表示iii天以内我们能够获取的信息的数量
那么我们现在能够得到的信息数就是有多少头熊睡着了和分别在哪一天睡着的那么有 Ri∑j1min{p−1,n}(nj)ijR_i\sum_{j1}^{min\{p-1,n\}}\binom{n}{j}i^jRij1∑min{p−1,n}(jn)ij 也就是组合睡觉的熊然后每个睡觉的都可以在任意天的时候睡觉
这个东西主要是(nj)\binom{n}{j}(jn)因为没有逆元比较麻烦但是因为jjj比较小所以我们可以直接暴力枚举上下的因子然后消掉他们的gcdgcdgcd就好了
时间复杂度O(p3logpq×p)O(p^3\log pq\times p)O(p3logpq×p) code
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
int n,p,q;
unsigned ans,f[300];
vectorint a,b;
int main()
{scanf(%d%d%d,n,p,q);pmin(n-1,p);for(int i0;ip;i){a.clear();b.clear();f[i]1;for(int j0;ji;j)a.push_back(n-j);for(int j1;ji;j)b.push_back(j);for(int x0;xa.size();x)for(int y0;yb.size();y){int d__gcd(a[x],b[y]);a[x]/d;b[y]/d;}for(int x0;xa.size();x)f[i]1u*a[x]*f[i];}for(int i1,t1;iq;i){unsigned tmp0,k1;for(int j0;jp;j,k1u*i*k)tmpf[j]*k;ans^1u*i*tmp;}printf(%u,ans);
}
