脚本宝典收集整理的这篇文章主要介绍了专项测试 数学3，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
不考虑两种限制很好做，用插板法，把 (m) 个球分成 (n) 堆
就是 (binom{m-1}{n-1})
第二种限制是大于等于的于是可以先给这些数分配 (a_i-1) 就行
第一种限制不好直接做，于是考虑容斥，用全部的方案数减去不合法的方案数
不合法的限制是 (x>a_i) 形式和第二种限制一样
然后剩下的直接容斥
#include<bits/stdc++.h>
#define int long long
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int T,p,n,n1,n2,m,U,ans;
int a[20];
inline void sc(){
n=read(),n1=read(),n2=read(),m=read();
for(int i=1;i<=n1+n2;i++) a[i]=read();
}
namespace P1{
#define mod 10007
int fac[10010],inv[10010];
inline int qpow(int x,int k){
int res=1,base=x;
while(k){if(k&1) res=res*base%mod;base=base*base%mod;k>>=1;}
return res;
}
inline void pre(){fac[0]=inv[0]=1;for(int i=1;i<=10006;i++) fac[i]=fac[i-1]*i%mod,inv[i]=inv[i-1]*qpow(i,mod-2)%mod;}
inline int C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline int Lucas(int n,int m){
if(n<0||m>n) return 0;if(!m) return 1;if(n<mod&&m<mod) return C(n,m);
return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
inline void solve(){
sc();ans=0;for(int i=n1+1;i<=n1+n2;i++) m-=a[i]-1;U=(1<<n1)-1;
if(m-1<n-1) return puts("0"),void();
for(int sta=0,sum,r;sta<=U;sta++){
sum=m;r=(__builtin_popcount(sta)&1)?-1:1;
for(int i=1;i<=n1;i++) if(sta&(1<<(i-1))) sum-=a[i];
ans=(ans+r*Lucas(sum-1,n-1)+mod)%mod;
}
printf("%lldn",ans);
}
#undef mod
}
namespace P2{
#define mod 262203414
int A[10],pA[10],B[10];//2*3*11*397*10007
int f[10010][10];
inline int qpow(int x,int k,int p){
int res=1,base=x;
while(k){if(k&1) res=res*base%p;base=base*base%p;k>>=1;}
return res;
}
inline void pre(){
A[1]=2,pA[1]=2;
A[2]=3,pA[2]=3;
A[3]=11,pA[3]=11;
A[4]=397,pA[4]=397;
A[5]=10007,pA[5]=10007;
for(int i=1,r;i<=5;i++){
f[0][i]=r=1;
for(int j=1,x;j<=A[i];j++){
x=j;while(x%pA[i]==0) x/=pA[i];
r=r*x%A[i];f[j][i]=r;
}
}
}
void exgcd(int a,int b,int &x,int &y){
if(!b) return x=1,y=0,void();
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 F(int n,int x){
if(n<=A[x]) return f[n][x];
int rou=1,rem=1,P=pA[x],PK=A[x];
for(int i=1;i<=PK;i++) if(i%P) rou=rou*i%PK;
rou=qpow(rou,n/PK,PK);
for(int i=PK*(n/PK);i<=n;i++) if(i%P) rem=rem*(i%PK)%PK;
return (F(n/P,x)*rou%PK*rem%PK);
}
inline int G(int n,int P){if(n<P) return 0;return G(n/P,P)+(n/P);}
inline int C_PK(int n,int m,int x){
int P=pA[x],PK=A[x];
int fz=F(n,x),fm1=INV(F(m,x),PK),fm2=INV(F(n-m,x),PK);
int mi=qpow(P,G(n,P)-G(m,P)-G(n-m,P),PK);
return fz*fm1%PK*fm2%PK*mi%PK;
}
inline int exLucas(int n,int m){
if(n<0||m>n) return 0;if(!m) return 1;
for(int i=1;i<=5;i++) B[i]=C_PK(n,m,i);
int res=0;
for(int i=1,M,T;i<=5;i++){
M=mod/A[i];T=INV(M,A[i]);
res=(res+B[i]*M%mod*T%mod)%mod;
}
return res;
}
inline void solve(){
sc();ans=0;for(int i=n1+1;i<=n1+n2;i++) m-=a[i]-1;U=(1<<n1)-1;
if(m-1<n-1) return puts("0"),void();
for(int sta=0,sum,r;sta<=U;sta++){
sum=m;r=(__builtin_popcount(sta)&1)?-1:1;
for(int i=1;i<=n1;i++) if(sta&(1<<(i-1))) sum-=a[i];
ans=(ans+r*exLucas(sum-1,n-1)+mod)%mod;
}
printf("%lldn",ans);
}
#undef mod
}
namespace P3{
#define mod 437367875
int A[10],pA[10],B[10];//5*5*5*7*7*7*101*101
int f[10300][5];
inline int qpow(int x,int k,int p){
int res=1,base=x;
while(k){if(k&1) res=res*base%p;base=base*base%p;k>>=1;}
return res;
}
inline void pre(){
A[1]=125,pA[1]=5;
A[2]=343,pA[2]=7;
A[3]=10201,pA[3]=101;
for(int i=1,r;i<=3;i++){
f[0][i]=r=1;
for(int j=1,x;j<=A[i];j++){
x=j;while(x%pA[i]==0) x/=pA[i];
r=r*x%A[i];f[j][i]=r;
}
}
}
void exgcd(int a, int b, int &x, int &y){
if(!b) return x=1,y=0,void();
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 F(int n,int x){
if(n<=A[x]) return f[n][x];
int rou=1,rem=1,P=pA[x],PK=A[x];
for(int i=1;i<=PK;i++) if(i%P) rou=rou*i%PK;
rou=qpow(rou,n/PK,PK);
for(int i=PK*(n/PK);i<=n;i++) if(i%P) rem=rem*(i%PK)%PK;
return (F(n/P,x)*rou%PK*rem%PK);
}
inline int G(int n,int P){if(n<P) return 0;return G(n/P,P)+(n/P);}
inline int C_PK(int n,int m,int x){
int P=pA[x],PK=A[x];
int fz=F(n,x),fm1=INV(F(m,x),PK),fm2=INV(F(n-m,x),PK);
int mi=qpow(P,G(n,P)-G(m,P)-G(n-m,P),PK);
return fz*fm1%PK*fm2%PK*mi%PK;
}
inline int exLucas(int n,int m){
if(n<0||m>n) return 0;if(!m) return 1;
for(int i=1;i<=3;i++) B[i]=C_PK(n,m,i);
int res=0;
for(int i=1,M,T;i<=3;i++){
M=mod/A[i];T=INV(M,A[i]);
res=(res+B[i]*M%mod*T%mod)%mod;
}
return res;
}
inline void solve(){
sc();ans=0;for(int i=n1+1;i<=n1+n2;i++) m-=a[i]-1;U=(1<<n1)-1;
if(m-1<n-1) return puts("0"),void();
for(int sta=0,sum,r;sta<=U;sta++){
sum=m;r=(__builtin_popcount(sta)&1)?-1:1;
for(int i=1;i<=n1;i++) if(sta&(1<<(i-1))) sum-=a[i];
ans=(ans+r*exLucas(sum-1,n-1)+mod)%mod;
}
printf("%lldn",ans);
}
#undef mod
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
T=read(),p=read();
if(p==10007){P1::pre();while(T--) P1::solve();}
if(p==262203414){P2::pre();while(T--) P2::solve();}
if(p==437367875){P3::pre();while(T--) P3::solve();}
return 0;
}
先说暴力，题里给的式子时裸的异或卷积式，所以直接上 (fwt) 暴力卷
卷积具有结合律所以可以应用矩阵快速幂（？这个不太会证明，但至少加减的卷积和位运算的都具有这个性质
发现在点值表示法下同一个位置做加法并不影响其他位置的值(一样不会证明，卷积好像都有这个性质？不懂
有了上面两条就可以把暴力的 (fwt) 卷积变一变了
设 (a_i) 为点值表示法下 (i) 这个下标的值，然后把所有的值都累加到 (b) 数组里
(b_i=sumlimits_{i=0}^pa_i^{2^j})
最后再一次 (IDFT) 求出 (b) 就行
那么问题变成了如何求出每个点的值，可以使用倍增法，也可以找循环节
我用的倍增实现
设 (f_{x,k}=sumlimits_{i=0}^{2^k-1}x^{2^i})
那么有 (f_{x,k}=f_{x,k-1}+f_{x^{2^{2^{k-1}}},k-1})
就是把上面的 (x) 变成上面的式子的第 (2^k) 项然后再拼起来就行
然后再对于每个值求出他最后的系数，求法和倍增的方法一样，可以画个图意会一下然后看看代码实现
#include<bits/stdc++.h>
#define int long long
#define rint signed
#define mod 10007
#define i2 5004
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,p,J,len,ans;
int a[262200];
int f[10010][40],F[10010],k2[40];
inline void md(int &x){x=(x>=mod)?x-mod:x;}
inline int qpow(int x,int k,int p){
int res=1,base=x;
while(k){if(k&1) res=res*base%p;base=base*base%p;k>>=1;}
return res;
}
inline void fwt(int tx){
for(int d=1;d<len;d<<=1) for(int i=0;i<len;i+=(d<<1)) for(int j=0;j<d;j++){
int x=a[i+j],y=a[i+j+d];
md(a[i+j]=(x+y));md(a[i+j+d]=(x-y+mod));
if(tx==-1) a[i+j]=a[i+j]*i2%mod,a[i+j+d]=a[i+j+d]*i2%mod;
}
}
inline void pre(){
k2[0]=1;for(int i=1;i<=35;i++) k2[i]=k2[i-1]*2;
for(int i=0;i<mod;i++) f[i][0]=i;
for(int j=1;j<=35;j++) for(int i=0,to;i<mod;i++){
to=qpow(i,qpow(2,k2[j-1],mod-1),mod);
f[i][j]=(f[i][j-1]+f[to][j-1])%mod;
}
for(int i=0,x,k,to;i<mod;i++){
x=i,k=p+1;
for(int j=35;~j;j--) if((1ll<<j)<=k){
k-=(1ll<<j);
F[i]=(F[i]+f[x][j])%mod;
x=qpow(x,qpow(2,k2[j],mod-1),mod);
}
}
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
n=read(),p=read(),J=read();len=1<<n;pre();
for(int i=0;i<len;i++) a[i]=read();
fwt(1);for(int i=0;i<len;i++) a[i]=F[a[i]];fwt(-1);
printf("%lldn",a[J]);
return 0;
}
发现对于一段区间，如果中间的某一个 (.) 没有变成 (x) 那么他被这个点分成的两个区间互不影响
考虑根据这个性质进行 (dp)
设 (f(l,r)) 表示把区间 ([l,r-1]) 都变成了 (x) 并且 (r) 为 (.) 的期望
(g(l,r)) 定义相同只不过为概率
(p(l,r,k)) 表示区间 ([l,k-1]) 和 ([k+1,r-1]) 已经变成 (x) 第 (k) 个位置最后变成 (x) 的概率
那么有 (g(l,r)=sumlimits_{k=l}^{r-1}p(l,r,k),f(l,r)=frac{1}{g(l,r)}sumlimits_{k=l}^{r-1}p_{l,r,k}*(f(l,k)+f(k+1,r)+frac{k-l}{2}))
(frac{k-l}{2}) 为期望增加的步数
简单推导一下总共增加的步数的情况有 (0,1,...,k-l) 等差数列求和为 (frac{(k-l)*(k-l+1)}{2})
然后每种情况的概率都是 (frac{1}{(k-l+1)}) 所以最后就是 (frac{k-l}{2})
走的步数成环，于是考虑破环为链，去枚举最后一个消掉的位置在哪里再加上最后一次的贡献 (frac{n-1}{2}) 即可
答案为 (frac{n-1}{2}+sumlimits_{i=1}^ng(i,i+n-1)*f(i,i+n-1))
然后考虑怎么求 (p(l,r,k))
设 (k) 左右各有 (lc,rc) 个 (.)
那么总共有 ((r-l+1)^{lc+rc+1}) 种情况
然后一共有 (binom{lc+rc}{lc}) 种方案来分配消去左右两边的 (.) 的顺序
消去左右的 (.) 的方案数为 ((k-l+1)^{lc}*g(l,k)*(r-k)^{rc}*g(k+1,r))
进左边消再乘上概率就是消光左边的合法方案数，右边的同理
最后一次必须消掉 (k) 于是有 (k-l+1)
所以 (p(l,r,k)=binom{lc+rc}{lc}*(frac{k-l+1}{r-l+1})^{lc}*g(l,k)*(frac{r-k}{r-l+1})^{rc}*g(k+1,r)*frac{k-l+1}{r-l+1})
最后注意判断全是 (x) 的情况
#include<bits/stdc++.h>
#define int long long
#define rint signed
#define eps 1e-8
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int T,n;
int cnt[410];
double C[410][410];
double f[410][410],g[410][410],ans;
char st[410];
inline void pre(){for(int i=0;i<=400;i++) for(int j=C[i][0]=1;j<=i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j];}
inline double qpow(double x,int k){
double res=1,base=x;
while(k){if(k&1) res=res*base;base=base*base;k>>=1;}
return res;
}
inline double p(int l,int r,int k){
int lc=cnt[k-1]-cnt[l-1],rc=cnt[r-1]-cnt[k];
return C[lc+rc][lc]*qpow(1.0*(k-l+1)/(r-l+1),lc)*g[l][k]*qpow(1.0*(r-k)/(r-l+1),rc)*g[k+1][r]*1.0*(k-l+1)/(r-l+1);
}
inline void solve(){
scanf("%s",st+1);n=strlen(st+1);for(int i=1;i<=n;i++) st[i+n]=st[i];n<<=1;
memset(f,0,sizeof(f));memset(g,0,sizeof(g));memset(cnt,0,sizeof(cnt));ans=0;
for(int i=1;i<=n;i++) cnt[i]=cnt[i-1]+(st[i]=='.');
for(int len=1;len<=(n>>1);len++) for(int l=1,r,fg;l+len-1<=n;l++) {
r=l+len-1;
fg=1;for(int i=l;i<r;i++) if(st[i]=='.') fg=0;
if(fg&&st[r]=='.'){
g[l][r]=1,f[l][r]=0;
}else{
for(int k=l;k<r;k++){
double res=p(l,r,k);
g[l][r]+=res;
f[l][r]+=res*(f[l][k]+f[k+1][r]+(k-l)/2.0);
}
if(g[l][r]>eps) f[l][r]/=g[l][r];
}
}
n>>=1;for(int i=1;i<=n;i++) ans+=(g[i][i+n-1]*f[i][i+n-1]);if(cnt[n]) ans=ans+(n-1)/2.0;
printf("%.10lfn",ans);
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
pre();T=read();while(T--) solve();
return 0;
}
以上是脚本宝典为你收集整理的专项测试 数学3全部内容，希望文章能够帮你解决专项测试 数学3所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。