A. Solving equation

It is easy to do without considering the two restrictions. Use the board inserting method to divide \ (m \) balls into \ (n \) piles

It's \ (\ binom{m-1}{n-1} \)

The second limit is greater than or equal to, so you can allocate \ (a_i-1 \) to these numbers first

The first restriction is not easy to do directly, so consider inclusion and exclusion, and subtract the number of illegal schemes from the total number of schemes

The illegal restriction is \ (x > a_i \) in the same form as the second restriction

Then the rest is directly exclusive

Code

#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("%lld\n",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("%lld\n",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("%lld\n",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;
}

B. Cosmic sequence

Let's talk about violence first. The formula given in the question is a naked XOR convolution, so go directly to the \ (fwt \) violence volume

Convolution has a binding law, so the fast power of matrix (?) can be applied. This is not likely to be proved, but at least the convolution of addition and subtraction and bit operation have this property

It is found that adding at the same position in the point-to-point representation does not affect the values at other positions (it will not prove that convolution seems to have this property? I don't understand

With the above two, we can change the convolution of violence \ (fwt \)

Set \ (a_i \) as the subscript value of \ (I \) under the point value representation, and then add all values to the \ (b \) array

\(b_i=\sum\limits_{i=0}^pa_i^{2^j}\)

Finally, find \ (b \) from \ (IDFT \) again

Then the problem becomes how to find the value of each point. You can use the multiplication method or find the cyclic node

I use multiplication to achieve

Set \ (f {x, K} = \ sum \ limits {I = 0} ^ {2 ^ k-1} x ^ {2 ^ I} \)

Then there is \ (f {x, K} = f {x, k-1} + F {x ^ {2 ^ {k-1}}, k-1} \)

Just change the above \ (x \) into the item \ (2^k \) of the above formula, and then spell it together

Then calculate the final coefficient for each value. The calculation method is the same as the multiplication method. You can draw a diagram and see the code implementation

Code

#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("%lld\n",a[J]);
	return 0;
}

C. exp

It is found that for an interval, if a \ (. \) in the middle does not become \ (x \), the two intervals divided by this point do not affect each other

Consider \ (dp \) based on this property

Let \ (f(l,r) \) represent the expectation that the interval \ ([l,r-1] \) has become \ (x \) and \ (r \) is \ (. \)

\(g(l,r) \) has the same definition, but it is probability

\(p(l,r,k) \) indicates the probability that the interval \ ([l,k-1] \) and \ ([k+1,r-1] \) have become the \ (K \) position of \ (x \) and finally become \ (x \)

Then there are \ (g(l,r)=\sum\limits_{k=l}^{r-1}p(l,r,k),f(l,r)=\frac{1}{g(l,r)}\sum\limits_{k=l}^{r-1}p_{l,r,k}*(f(l,k)+f(k+1,r)+\frac{k-l}{2})\)

\(\ frac{k-l}{2} \) is the number of steps expected to be added

Simply deduce that the total number of steps increased is \ (0,1,...,k-l \) and the sum of the arithmetic sequence is \ (\ frac{(k-l)*(k-l+1)}{2} \)

Then the probability of each case is \ (\ frac{1}{(k-l+1)} \), so the last is \ (\ frac{k-l}{2} \)

The steps taken form a ring, so consider breaking the ring as a chain, enumerate where the last eliminated position is, and add the last contribution \ (\ frac{n-1}{2} \)

The answer is \ (\ frac {n-1} {2} + \ sum \ limits {I = 1} ^ ng (I, I + n-1) * f (I, I + n-1) \)

Then consider how to find \ (p(l,r,k) \)

Set \ (lc,rc \) around \ (k \) \ (. \)

There are \ ((r-l+1)^{lc+rc+1} \) cases in total

Then there are \ (\ binom{lc+rc}{lc} \) schemes to allocate and eliminate the order of \ (. \) on the left and right sides

The number of schemes to eliminate the left and right \ (. \) is \ ((k-l+1)^{lc}*g(l,k)*(r-k)^{rc}*g(k+1,r) \)

The number of legal schemes on the left of extinction is multiplied by the probability. The same is true on the right

The last time \ (k \) must be eliminated, so there is \ (k-l+1 \)

So \ (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} \)

Finally, pay attention to judge that it is all \ (x \)

Code

#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("%.10lf\n",ans);
}
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	pre();T=read();while(T--) solve();
	return 0;
}