建设网站公司浩森宇特,做sgs认证的公司网站,天津网站运营,长沙seo外包行者seo07B-Cannon
首先nnn个炮在一行操作一次的方案数为2(n−2)2(n-2)2(n−2):前面两个炮只能向右吃#xff0c;最后两个跑只能向左吃#xff0c;而其余的炮既可以向左也可以向右#xff0c;于是有42(n−4)42(n-4)42(n−4)种
于是操作mmm次的操作排列的方案数为2m(n−2)(n−3)...(…B-Cannon
首先nnn个炮在一行操作一次的方案数为2(n−2)2(n-2)2(n−2):前面两个炮只能向右吃最后两个跑只能向左吃而其余的炮既可以向左也可以向右于是有42(n−4)42(n-4)42(n−4)种
于是操作mmm次的操作排列的方案数为2m(n−2)(n−3)...(n−m−1)2m(n−2)!(n−2−m)!2^m(n-2)(n-3)...(n-m-1)2^m\frac {(n-2)!}{(n-2-m)!}2m(n−2)(n−3)...(n−m−1)2m(n−2−m)!(n−2)! 设na−2,mb−2na-2,mb-2na−2,mb−2
首先选择从kkk选择iii次操作第一行选择k−ik-ik−i次操作第二行而问题一还需要从kkk个位置选择出iii个按序放置操作序列而问题二必须强制第一行操作放置在第二行操作前面由此有
对于问题1即是求 ∑0≤i≤k(ki){2in!(n−i)!}×{2k−im![m−(k−i)]!}2k∑0≤i≤kk!i!(k−i)!⋅n!(n−i)!⋅m![m−(k−i)]!2kk!∑0≤i≤k(ni)(mk−i)2kk!(nmk)\begin{aligned} \sum_{0\leq i\leq k}\dbinom{k}{i}\{2^i\frac{n!}{(n-i)!}\}×\{2^{k-i}\frac{m!}{[m-(k-i)]!}\}\\ \\2^k\sum_{0\leq i\leq k}\frac{k!}{i!(k-i)!}·\frac{n!}{(n-i)!}·\frac{m!}{[m-(k-i)]!}\\ \\2^kk!\sum_{0\leq i\leq k} \dbinom{n}{i}\dbinom{m}{k-i}\\\\2^kk!\dbinom{nm}{k} \end{aligned}0≤i≤k∑(ik){2i(n−i)!n!}×{2k−i[m−(k−i)]!m!}2k0≤i≤k∑i!(k−i)!k!⋅(n−i)!n!⋅[m−(k−i)]!m!2kk!0≤i≤k∑(in)(k−im)2kk!(knm) 对于问题2即是求 ∑0≤i≤k{2in!(n−i)!}×{2k−im![m−(k−i)]!}2k∑0≤i≤kn!(n−i)!×m![m−(k−i)]!2kn!m!(nm−k)!∑0≤i≤k(nm−k)!(n−i)![m−(k−i)]!2kn!m!(nm−k)!∑0≤i≤k(nm−kn−i)2kn!m!(nm−k)!∑n−k≤i≤n(nm−kj)\begin{aligned} \sum_{0\leq i\leq k}\{2^i\frac{n!}{(n-i)!}\}×\{2^{k-i}\frac{m!}{[m-(k-i)]!}\}\\\\2^k\sum_{0\leq i\leq k}\frac{n!}{(n-i)!}×\frac{m!}{[m-(k-i)]!}\\\\2^k\frac{n!m!}{(nm-k)!}\sum_{0\leq i\leq k}\frac{(nm-k)!}{(n-i)![m-(k-i)]!}\\\\2^k\frac{n!m!}{(nm-k)!}\sum_{0\leq i\leq k}\dbinom{nm-k}{n-i}\\\\2^k\frac{n!m!}{(nm-k)!}\sum_{n-k\leq i\leq n}\dbinom{nm-k}{j} \end{aligned}0≤i≤k∑{2i(n−i)!n!}×{2k−i[m−(k−i)]!m!}2k0≤i≤k∑(n−i)!n!×[m−(k−i)]!m!2k(nm−k)!n!m!0≤i≤k∑(n−i)![m−(k−i)]!(nm−k)!2k(nm−k)!n!m!0≤i≤k∑(n−inm−k)2k(nm−k)!n!m!n−k≤i≤n∑(jnm−k) 其中下面一项是组合数种的连续多项之和考虑前缀和
∑n−k≤j≤n(nm−kj)∑0≤j≤n(nm−kj)−∑0≤j≤n−k−1(nm−kj)∑0≤j≤n(nm−kj)−∑0≤j≤n−k−1(nm−knm−k−j)∑0≤j≤n(nm−kj)−∑m1≤j≤nm−k(nm−kj)∑0≤j≤n(nm−kj)−{∑0≤j≤nm−k(nm−kj)−∑0≤j≤m(nm−kj)}∑0≤j≤n(nm−kj)∑0≤j≤m(nm−kj)−2nm−ksum(nm−k)\begin{aligned} \sum_{n-k\leq j\leq n}\dbinom{nm-k}{j}\\\\\sum_{0\leq j\leq n}\dbinom{nm-k}{j}-\sum_{0\leq j\leq n-k-1}\dbinom{nm-k}{j}\\\\\sum_{0\leq j\leq n}\dbinom{nm-k}{j}-\sum_{0\leq j\leq n-k-1}\dbinom{nm-k}{nm-k-j}\\\\\sum_{0\leq j\leq n}\dbinom{nm-k}{j}-\sum_{m1\leq j\leq nm-k}\dbinom{nm-k}{j}\\\\\sum_{0\leq j\leq n}\dbinom{nm-k}{j}-\{\sum_{0\leq j\leq nm-k}\dbinom{nm-k}{j}-\sum_{0\leq j\leq m}\dbinom{nm-k}{j}\}\\\\\sum_{0\leq j\leq n}\dbinom{nm-k}{j}\sum_{0\leq j\leq m}\dbinom{nm-k}{j}-2^{nm-k}\text{sum}(nm-k) \end{aligned}n−k≤j≤n∑(jnm−k)0≤j≤n∑(jnm−k)−0≤j≤n−k−1∑(jnm−k)0≤j≤n∑(jnm−k)−0≤j≤n−k−1∑(nm−k−jnm−k)0≤j≤n∑(jnm−k)−m1≤j≤nm−k∑(jnm−k)0≤j≤n∑(jnm−k)−{0≤j≤nm−k∑(jnm−k)−0≤j≤m∑(jnm−k)}0≤j≤n∑(jnm−k)0≤j≤m∑(jnm−k)−2nm−ksum(nm−k)
考虑求出Sn,m∑i0m(ni)S_{n,m}\sum_{i0}^{m}\dbinom{n}{i}Sn,m∑i0m(in)的关于nnn的递推式
Sn,m∑i0m(ni)∑i0m[(n−1i)(n−1i−1)]Sn−1,mSn−1,m−1\begin{aligned} S_{n,m}\sum_{i0}^{m}\dbinom{n}{i}\sum_{i0}^{m}[\dbinom{n-1}{i}\dbinom{n-1}{i-1}]\\S_{n-1,m}S_{n-1,m-1} \end{aligned}Sn,mi0∑m(in)i0∑m[(in−1)(i−1n−1)]Sn−1,mSn−1,m−1
而Sn−1,m∑i0m(n−1i)Sn−1,m−1(n−1m)\begin{aligned} S_{n-1,m}\sum_{i0}^{m}\dbinom{n-1}{i}S_{n-1,m-1}\dbinom{n-1}{m} \end{aligned}Sn−1,mi0∑m(in−1)Sn−1,m−1(mn−1)
带入可得出 Sn,m2Sn−1,m−(n−1m)S_{n,m}2S_{n-1,m}-\dbinom{n-1}{m} Sn,m2Sn−1,m−(mn−1) 由此可得出 sum(x)∑0≤j≤n(xj)∑0≤j≤m(xj)−2xSx,nSx,m−2x2sum(x−1)−(x−1n)−(x−1m)\begin{aligned} \text{sum}(x)\sum_{0\leq j\leq n}\dbinom{x}{j}\sum_{0\leq j\leq m}\dbinom{x}{j}-2^{x}\\\\S_{x,n}S_{x,m}-2^x\\\\2\text{sum}(x-1)-\dbinom{x-1}{n}-\dbinom{x-1}{m} \end{aligned}sum(x)0≤j≤n∑(jx)0≤j≤m∑(jx)−2xSx,nSx,m−2x2sum(x−1)−(nx−1)−(mx−1) Code
#includebits/stdc.h
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
const ll mod1e99;
ll qmi(ll a,ll b)
{ll v1;while(b){if(b1) vv*a%mod;b1;aa*a%mod;}return v;
}
int n,m;
ll inv[10000010];
void solve1()
{ll ans1;ll Two1,Fact1;ll C1;for(int i1;inm;i){TwoTwo*2%mod;FactFact*i%mod;CC*(nm-i1)%mod*inv[i]%mod;ans^((Two*Fact%mod*C%mod)mod)%mod;}printf(%lld ,ans);
}
ll sum[10000010];void solve2()
{ll Cn1,Cm1;sum[0]1;for(int i1;imin(n,m);i) sum[i]2*sum[i-1]%mod;for(int imin(n,m)1;inm;i){sum[i]2*sum[i-1]-(in?Cn:0)-(im?Cm:0);if(in) CnCn*i%mod*inv[i-n]%mod;if(im) CmCm*i%mod*inv[i-m]%mod;sum[i](sum[i]%modmod)%mod;}ll Factn1,Factm1,Two1;for(int i1;in;i) FactnFactn*i%mod;for(int i1;im;i) FactmFactm*i%mod;ll Inv1;for(int i1;inm;i) InvInv*inv[i]%mod;ll ansTwo*Factn%mod*Factm%mod*Inv%mod*sum[nm]%mod;for(int i1;inm;i){TwoTwo*2%mod;InvInv*(nm-i1)%mod;ans^((Two*Factn%mod*Factm%mod*Inv%mod*sum[nm-i]%mod)mod)%mod;}printf(%lld\n,ans);
}
int main()
{nrd()-2,mrd()-2;inv[1]1;for(int i2;inm;i) inv[i](mod-mod/i*inv[mod%i]%mod)%mod;solve1();solve2();return 0;
}看着公式写代码都写了好长时间wtcl
