今天是警察节,不值得庆祝一下吗
exLucas 板子题
一开始我还想预处理,但是发现这并不是多组询问,遂板子一点没改,然后略作调整即可通过
判断无解很简单,就是当送出的礼物太多,超过 \(n\) 自然就是无解了,维护 \(sum\) 求和就行
然后求每个赠的礼物 \(ans=ans\times exLucas(n,w_i,p)\) 就行
因为送完一次礼物后显然总数会下降,所以每次求完结果后 \(n-=w_i\)
写的很烂的 exLucas 板子
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6;
int n,m,p;
inline int read()
{
int s = 0,w = 1;char ch = getchar();
while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}
while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}
return s*w;
}
inline int qpow(int a, int b,int p)
{
int ans=1;a%=p;
while(b)
{
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
inline void exgcd(int a,int b,int &x,int &y)
{
if(!b)
return (void)(x=1,y=0);
exgcd(b,a%b,x,y);
int tmp=x;x=y;y=tmp-a/b*y;
}
inline int inv(int a,int p)
{
int x,y;
exgcd(a,p,x,y);
return (x+p)%p;
}
inline int fac(int n,int p,int pk)
{
if(n==0) return 1;
int ans=1,mo=1;
for(int i=1;i<=pk;++i)
if(i%p)
ans=ans*i%pk;
ans=qpow(ans,n/pk,pk);
for(int i=pk*(n/pk);i<=n;++i)
if(i%p)
mo=mo*(i%pk)%pk;
return ans%pk*fac(n/p,p,pk)*mo%pk;
}
inline int G(int n,int p)
{
if(n<p) return 0;
return G(n/p,p)+(n/p);
}
inline int C(int n,int m,int p,int pk)
{
int f1=fac(n,p,pk),f2=inv(fac(m,p,pk),pk),f3=inv(fac(n-m,p,pk),pk);
int b=qpow(p,G(n,p)-G(m,p)-G(n-m,p),pk);
return f1*f2%pk*f3%pk*b%pk;
}
int a[N],b[N];
int cnt;
inline int exlucas(int n,int m,int p)
{
int P=p,tot=0;
int Genshin=sqrt(p);
for(int i=2;i<=Genshin;i++)
{
if(!(P%i))
{
int pk=1;
while(!(P%i))
{
pk*=i;P/=i;
}
a[++tot]=pk;b[tot]=C(n,m,i,pk);
}
}
if(P!=1)
{
a[++tot]=P;b[tot]=C(n,m,P,P);
}
int ans=0;
for(int i=1;i<=tot;++i)
{
int M=p/a[i],t=inv(M,a[i]);
ans=(ans+b[i]*M%p*t%p)%p;
}
return ans;
}
int w[N],sum,ans=1;
signed main()
{
int p=read(),n=read(),m=read();
for(int i=1;i<=m;++i) {w[i]=read(),sum+=w[i];}
if(sum>n) {cout<<"Impossible";return 0;}
for(int i=1;i<=m;++i)
{
ans=ans*exlucas(n,w[i],p)%p;
n-=w[i];
}
cout<<ans<<endl;
}
jjdw 玩 cnblogs 的人机验证,卡了 10 分钟才过。
lty 玩 cnblogs 的人机验证,卡了 5 分钟才过。
ljk 玩 cnblogs 的人机验证,卡了 3 分钟才过。
我玩 cnblogs 的人机验证,一下子就进去了!
因此得出结论:通过人机验证的时间与 OI 强度成正比,越不是人机的人机反而会长时间的卡在人机验证界面,而‘人’反而会迅速地通过,这才是人机验证的真正意义!人机验证的目的不是让人机通不过人机验证,而是让人机们提高自己的 OI 能力,使得卡在人机验证的时间更长从而使 AI 发展更加强大!
从另一个角度思考,可能身边所有人都是 bot,jjdw 是bot,lty 是bot,ljk 是bot,我是 bot。
这个世界将被机器人取代,终有一天。
太可怕了吧,博客园抓紧取消人机验证吧,这样就没人知道身边人是 bot 了。
大家都不知道身边的人是 bot,自然也不会慌乱,有点自欺欺人的意味。
今天没图也没学科学术,因为我没素材了(
不忘初心。