题目链接
题目大意
求 \((0,0)\) 到 \((x,y)\) 走 \(n\) 步的方案数，对 \(P\) 取模（每步上下左右 \(1\) 格）
（\(x,y,n\le 10^6\)，不保证 \(P\) 质数）
题解
法一
可以设向左的步数为 \(i\) 则向右的步数为 \(x+i\)
同理设向下的步数为 \(j\) 则向上的步数为 \(y+j\)
我们有 \(x+2i+y+2j=n\)
于是 \(j=\frac{n-x-y}{2}-i\)
方案数相当于一个多重集排列
多重集排列公式： \(\displaystyle\frac{n!}{m_1!m_2!\dots m_k!}\)
枚举 \(i\)，得方案数
\[\begin{align*} &\sum_i\frac{n!}{i!(x+i)!j!(y+j)!}\\ =&\sum_i\frac{n!}{i!(x+i)!(\frac{n-x-y}{2}-i)!(\frac{n-x+y}{2}-i)!}\\ \end{align*} \]注意到这个时候因为没有逆元不能直接做
我们继续推
\[\begin{align*} &\sum_i\frac{n!}{i!(x+i)!(\frac{n-x-y}{2}-i)!(\frac{n-x+y}{2}-i)!}\\ =&\sum_i\frac{\binom{(n-x-y)/{2}}{i}\binom{(n+x+y)/{2}}{x+i}n!}{((n-x-y)/2)!((n+x+y)/{2})!}\\ =&\binom{n}{(n+x+y)/{2}}\sum_i \binom{(n-x-y)/{2}}{i}\binom{(n+x+y)/{2}}{x+i} \end{align*} \]这边需要用到个小公式
范德蒙德卷积：
\(\displaystyle{\sum_i{\binom{n}{i}\binom{m}{k-i}}=\binom{n+m}{k}}\)
组合意义：从 \(n+m\) 选 \(k\) 个，可以枚举在 \(n\) 个中选择 \(i\) 个，则 \(m\) 个中就选择 \(k-i\) 个
也就是说
\[\begin{align*} &\binom{n}{(n+x+y)/{2}}\sum_i \binom{(n-x-y)/{2}}{i}\binom{(n+x+y)/{2}}{x+i}\\ =&\binom{n}{(n+x+y)/{2}}\sum_i \binom{(n-x-y)/{2}}{i}\binom{(n+x+y)/{2}}{(n-x+y)/{2}-i}\\ =&\binom{n}{(n+x+y)/{2}}\binom{n}{(n-x+y)/2} \end{align*} \]处理非质数模数的方法：
预处理所有数质因数分解，组合数直接处理每个指数幂
法二
坐标系转化
一个常见套路：
\((x,y)\rightarrow (x+y,x-y)\)
\((0,\pm1)\rightarrow(\pm1,\mp1)\)
\((\pm1,0)\rightarrow(\pm1,\pm1)\)
于是走 \(n\) 步可以拆成两个独立的方向，每个方向走 \(n\) 步
答案就可以直接出来是 \(\displaystyle{\binom{n}{(n+x+y)/{2}}\binom{n}{(n-x+y)/2}}\)
代码
#include <bits/stdc++.h>
#define ll long long
#define fs first
#define sc second
using namespace std;
const int N = 1e6+5;
int n,P,x,y;
map<int,int> a[N];
int qpw(int a, int b)
{
int res=1;
for(; b; b>>=1,a=(ll)a*a%P) if(b&1) res=(ll)a*res%P;
return res;
}
int work(int m)
{
// printf("m=%d\n",m);
if(m<0 or n<m) return 0;
map<int,int> res;
for(int i=n; i>=(n-m+1); i--)
{
for(auto v:a[i])
{
if(res.count(v.fs)) res[v.fs]+=v.sc;
else res.insert(v);
}
}
for(int i=1; i<=m; i++)
{
for(auto v:a[i])
{
assert(res.count(v.fs));
res[v.fs]-=v.sc;
}
}
int ans=1;
for(auto v:res) ans=(ll)ans*qpw(v.fs,v.sc)%P;
return ans;
}
int main()
{
scanf("%d%d%d%d",&n,&P,&x,&y);
for(int i=2; i<=n; i++)
{
if(!a[i].size())
{
a[i].insert({i,1});
for(int j=(i<<1); j<=n; j+=i)
{
int t=0;
for(int u=i; u<=j; u*=i,t++) if(j%u) break;
a[j].insert({i,t});
}
}
}
// for(int i=2; i<=n; i++) { for(auto v:a[i]) printf("(%d %d)",v.fs,v.sc); puts(""); }
int A=n+x-y;
if(A<0 or A&1) { puts("0"); return 0; }
A>>=1; int B=A+y;
int res=(ll)work(A)*work(B)%P;
return !printf("%d\n",res);
}