Codeforces 643F - Bears and Juice(思维题)
阅读原文时间:2023年07月08日阅读:3

Codeforces 题目传送门 & 洛谷题目传送门

首先直接暴力枚举显然是不现实的,我们不妨换个角度来处理这个问题,考虑这 \(R_i\) 个瓶子中每一瓶被哪些熊在哪一天喝过。

我们考虑对这 \(R_i\) 个瓶子各建立一个 \(q\times n\) 的 01 矩阵,第 \(j\) 行第 \(k\) 列为 \(1\) 表示第 \(k\) 只熊在第 \(j\) 天尝过了这瓶酒,反之第 \(k\) 只熊在第 \(j\) 天尝过了这瓶酒。

那么题目中的条件可表示为:

  • 每一个表格里 \(1\) 的个数不能超过 \(\min(p,n-1)\),因为假设该表格里里 \(1\) 的个数超过 \(\min(p,n-1)\),那么万一这个瓶子里装的是酒,就会出现要么出现有熊没有床睡,要么所有熊都醉倒了的情况,这显然是不行的。
  • 不能存在两个瓶子,喝过它的熊的集合相同,且对应熊喝的天数也相同,则一旦这些熊喝醉了,剩下的熊就无论怎样也无法知道到底哪一桶是酒,哪一桶是饮料,因此这是非法的。

考虑设集合 \(S_i=\{(x,y)|\text{第}\ x\ \text{只熊在第}\ y\ \text{天尝过了第}\ i\ \text{个瓶子}\}\),那么上述条件又可翻译为:

  • 对于任意 \(i\) 都有 \(|S_i|\leq\min(p,n-1)\)
  • \(\forall i,j\in[1,R_i],S_i\neq S_j\)

条件 \(2\) 显然可以用抽屉原理进一步转化为求满足 \(|S|\leq\min(p,n-1)\) 的 \(S\) 的个数,而这个数又显然可以用组合数求出,\(ans_q=\sum\limits_{i=0}^{\min(p,n-1)}\dbinom{n}{i}q^i\),到此为止我们推导出了答案的式子。

算下复杂度,\(p\) 的范围只有 \(130\),故对于每个 \(q\) 暴力计算上式的值都没问题。还有个小问题,就是这题模数为 \(2^{32}\) 不是质数,这意味着不是所有数都有逆元,故我们不能用预处理阶乘+阶乘的逆元的方式计算组合数,不过这个问题显然难不住我们,由于这题 \(p\) 范围如此小,把组合数的式子暴力展开并暴力去分母的方法都能过,复杂度 \(p^3\log p\),当然有神仙想写 exLucas 那也没人拦着你,复杂度大约可以做到 \(p\log p\),反正我是太懒不想写了(

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
namespace fastio{
    #define FILE_SIZE 1<<23
    char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;
    inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}
    inline void putc(char x){(*p3++=x);}
    template<typename T> void read(T &x){
        x=0;char c=getchar();T neg=0;
        while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
        while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
        if(neg) x=(~x)+1;
    }
    template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}
    template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}
    void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}
}
typedef unsigned int u32;
const int MAXN=130;
u32 gcd(int x,int y){return (!y)?x:gcd(y,x%y);}
int n,p,q;u32 c[MAXN+5];
u32 calc(int x){
    vector<u32> a,b;
    for(int i=1;i<=x;i++) a.pb(n-i+1),b.pb(i);
    for(int i=0;i<a.size();i++) for(int j=0;j<b.size();j++){
        u32 d=gcd(a[i],b[j]);a[i]/=d;b[j]/=d;
    } u32 prod=1;
    for(int i=0;i<a.size();i++) prod*=a[i];
    return prod;
}
int main(){
    scanf("%d%d%d",&n,&p,&q);p=min(n-1,p);
    for(int i=0;i<=p;i++) c[i]=calc(i);u32 ans=0;
    for(int i=1;i<=q;i++){
        u32 prod=1,sum=0;
        for(int j=0;j<=p;j++){
            sum+=prod*c[j];
            prod*=i;
        } ans^=i*sum;
    } printf("%u\n",ans);
    return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章