【CERC2015】Frightful Formula

组合数。

就是一道推式子。

首先考虑$F[i,1]$和$F[1,i]$的贡献,这个很好求。考虑这个点到$F[n,n]$每次坐标加一走过去的方案数,显然是$C(n+n-i-2,n-i)$,在这基础上将$a$和$b$考虑进去就可以了。

然后是考虑$c$的贡献,这个式子有点长。稍微组合数推一下,大概长成这样$c\sum_{i=2}^n \sum_{j=2}^n (2\ast n-i-j)!\ast \frac {a^{n-j}}{(n-j)!}\ast \frac {b^{n-i}}{(n-i)!}$。

这里显然可以NTT,但模数很丑,要任意模数。所以正解肯定有更好的方法。

我们考虑斜对角线的贡献。我们发现每条相邻斜线之间的贡献都是有递推关系的。显然在主斜对角线之前的任意斜线的总贡献为其上一斜线的总贡献$\ast (a+b)$。同时经过主斜对角线后贡献显然会算多,于是每次减掉多余的贡献就可以了。

显然最小的斜线贡献为$1$。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//2019.2.26 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline int read(){
res s=0;
bool w=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return w?-s:s;
}
inline void _swap(res &x,res &y){
x^=y^=x^=y;
}
inline int _abs(const res &x){
return x>0?x:-x;
}
inline int _max(const res &x,const res &y){
return x>y?x:y;
}
inline int _min(const res &x,const res &y){
return x<y?x:y;
}
const int kcz=1000003;
const int N=4e5+10;
namespace MAIN{
inline int mul(const res &x,const res &y){
return 1LL*x*y%kcz;
}
inline int qpow(res x,res y){
res ret=1;
while(y){
if(y&1)ret=mul(ret,x);
y>>=1,x=mul(x,x);
}
return ret;
}
inline void add(res &x,const res &y){
x+=y,x>=kcz?x-=kcz:1,x<0?x+=kcz:1;
}
inline int Add(const res &x,const res &y){
return x+y>=kcz?x+y-kcz:(x+y<0?x+y+kcz:x+y);
}
int n,a,b,c;
int fac[N],inv[N];
inline void pre(){
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(res i=2;i<=2*n;i++)fac[i]=mul(fac[i-1],i),inv[i]=mul(inv[kcz%i],kcz-kcz/i);
for(res i=2;i<=2*n;i++)inv[i]=mul(inv[i-1],inv[i]);
}
inline int C(const res &x,const res &y){
return x<y?0:mul(fac[x],mul(inv[y],inv[x-y]));
}
int ans;
int pwa[N],pwb[N];
inline void MAIN(){
n=read(),a=read(),b=read(),c=read(),pre();
pwa[0]=pwb[0]=1;
for(res i=1;i<=n;i++)pwa[i]=mul(pwa[i-1],a),pwb[i]=mul(pwb[i-1],b);
for(res i=1;i<=n;i++)add(ans,mul(read(),i>1?mul(C(2*n-i-2,n-i),mul(pwa[n-1],pwb[n-i])):0));
for(res i=1;i<=n;i++)add(ans,mul(read(),i>1?mul(C(2*n-i-2,n-i),mul(pwa[n-i],pwb[n-1])):0));
res now=1,ab=Add(a,b);
for(res i=1;i<=n-2;i++)now=mul(now,ab),add(ans,mul(now,c));
for(res i=1;i<=n-2;i++){
res v1=mul(C(n+i-3,i-1),mul(pwa[i-1],pwb[n-2])),v2=mul(C(n+i-3,i-1),mul(pwa[n-2],pwb[i-1]));
now=Add(mul(Add(now,-Add(v1,v2)),ab),Add(mul(v1,a),mul(v2,b))),add(ans,mul(now,c));
}
printf("%d\n",Add(ans,c));
}
}
int main(){
MAIN::MAIN();
return 0;
}

以上代码轻松跑了LG和bzoj的rnk1.