首先直接暴力枚举显然是不现实的,我们不妨换个角度来处理这个问题,考虑这 \(R_i\) 个瓶子中每一瓶被哪些熊在哪一天喝过。
我们考虑对这 \(R_i\) 个瓶子各建立一个 \(q\times n\) 的 01 矩阵,第 \(j\) 行第 \(k\) 列为 \(1\) 表示第 \(k\) 只熊在第 \(j\) 天尝过了这瓶酒,反之第 \(k\) 只熊在第 \(j\) 天尝过了这瓶酒。
那么题目中的条件可表示为:
考虑设集合 \(S_i=\{(x,y)|\text{第}\ x\ \text{只熊在第}\ y\ \text{天尝过了第}\ i\ \text{个瓶子}\}\),那么上述条件又可翻译为:
条件 \(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;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章