正題

題目鏈接:https://www.luogu.com.cn/problem/CF643F

---

題目大意

題目有點奇怪就直接放翻譯了

有 $n$ 只熊和若干桶果汁和恰好一桶酒，每一天每只熊會選擇一些桶（可能不選）并各喝一 杯，喝到酒的熊會去睡覺并不再回來，通過這個信息，熊們想知道哪個桶里是酒。

只有 $p$ 個睡 覺的位置，當睡覺的熊超過了 $p$ 只或者所有熊都在睡覺時熊們就失敗了。

令 $R_i$ 表示在 $i$ 天內桶的數量最多少，使得熊可以成功知道酒的位置。令 $X_i=(i\times R_i)\mathrm{m}\mathrm{o}\mathrm{d}{2}^{32}$，你需要求出 $X_1\oplus X_2\oplus \dots \oplus X_q$。

$1\le n\le 10^9$，$1\le p\le 130$，$1\le q\le 2\times 10^6$。

---

解題思路

之前在XJ雜題選講時候的神奇題目

題目比較亂但是我們發現題目問的是最多的數量，而不是最劣情況下的最多數量，所以這個東西是在最優情況下能分辨的數量。

這是我們之前很少接觸的一種形式，這里需要用到信息的概念，因為我們是最優的，相當于我們所有的情況都可以去嘗試，也就是每種信息都可以為我們選出一個答案，那么顯然我們讓選出的這些答案兩兩不同肯定就是最優的，所以這里的$R_i$就表示$i$天以內我們能夠獲取的信息的數量

那么我們現在能夠得到的信息數就是有多少頭熊睡著了，和分別在哪一天睡著的，那么有
$$R_i=\sum _{j=1}^{min\{p?1,n\}}\left(\genfrac{}{}{0ex}{}{n}{j}\right)i^j$$
也就是組合睡覺的熊，然后每個睡覺的都可以在任意天的時候睡覺

這個東西主要是$\left(\genfrac{}{}{0ex}{}{n}{j}\right)$因為沒有逆元比較麻煩，但是因為$j$比較小所以我們可以直接暴力枚舉上下的因子然后消掉他們的$gcd$就好了

時間復雜度$O(p^3\log p+q\times p)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; int n,p,q; unsigned ans,f[300]; vector<int> a,b; int main() {scanf("%d%d%d",&n,&p,&q);p=min(n-1,p);for(int i=0;i<=p;i++){a.clear();b.clear();f[i]=1;for(int j=0;j<i;j++)a.push_back(n-j);for(int j=1;j<=i;j++)b.push_back(j);for(int x=0;x<a.size();x++)for(int y=0;y<b.size();y++){int d=__gcd(a[x],b[y]);a[x]/=d;b[y]/=d;}for(int x=0;x<a.size();x++)f[i]=1u*a[x]*f[i];}for(int i=1,t=1;i<=q;i++){unsigned tmp=0,k=1;for(int j=0;j<=p;j++,k=1u*i*k)tmp+=f[j]*k;ans^=1u*i*tmp;}printf("%u",ans); }

總結

以上是生活随笔為你收集整理的CF643F-Bears and Juice【组合数学】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。