组合计数(隔板法)+ 预处理阶乘逆元
固定连续段数 i 后,字符串只可能是 a 开头或 b 开头两种;每种情况下,把 x 个 a、y 个 b 分成对应段数,方案数就是 这种形式相乘。
两种开头的结果相加,就是该 i 的答案,i 从 1 到 x+y 依次算完输出。
void solve(){
int x,y;cin>>x>>y;
int n=x+y;
vll f(n+1),g(n+1);
f[0]=1;
for(int i=1;i<=n;++i){
f[i]=f[i-1]*i%MOD;
}
g[n]=qpow(f[n],MOD-2);
for(int i=n;i>=1;--i){
g[i-1]=g[i]*i%MOD;
}
auto C=[&](int N,int K)->ll{
if(K<0||K>N){
return 0;
}
return f[N]*g[K]%MOD*g[N-K]%MOD;
};
for(int i=1;i<=n;++i){
int a1=(i+1)>>1,b1=i>>1;
int a2=i>>1,b2=(i+1)>>1;
ll ans=C(x-1,a1-1)*C(y-1,b1-1)%MOD;
ans=(ans+C(x-1,a2-1)*C(y-1,b2-1))%MOD;
cout<<ans<<endl;
}
}
import sys
MOD=1000000007
def qpow(a,b):
r=1
while b:
if b&1:
r=r*a%MOD
a=a*a%MOD
b>>=1
return r
def solve():
x,y=map(int,sys.stdin.buffer.read().split())
n=x+y
fac=[1]*(n+1)
ifac=[1]*(n+1)
for i in range(1,n+1):
fac[i]=fac[i-1]*i%MOD
ifac[n]=qpow(fac[n],MOD-2)
for i in range(n,0,-1):
ifac[i-1]=ifac[i]*i%MOD
def C(N,K):
if K<0 or K>N:
return 0
return fac[N]*ifac[K]%MOD*ifac[N-K]%MOD
out=[]
for i in range(1,n+1):
a1=(i+1)>>1
b1=i>>1
a2=i>>1
b2=(i+1)>>1
ans=C(x-1,a1-1)*C(y-1,b1-1)%MOD
ans=(ans+C(x-1,a2-1)*C(y-1,b2-1))%MOD
out.append(str(ans))
sys.stdout.write('\n'.join(out)+'\n')
if __name__=='__main__':
solve()

京公网安备 11010502036488号