回忆京都

洛谷月赛的一道水题。。。

似乎要比第一题还要简单一点？

https://www.luogu.org/problemnew/show/P5239

好吧，直接切入正题。。。

关于这道题，简单来说就是求一个式子：

$\sum$

那么最简单的方法就应该是先预处理出阶乘和组合数，利用二维数组储存，暴力枚举i，j，利用费马小定理求逆元直接代式子来进行求和就可以了。

写完就是这个效果：

可以看到，我们TLE了三个点，那么我们该如何解决呢？

考虑我们的程序，费马小定理基本已经最优了（经过我的测试扩展gcd好像更慢？？？），预处理也大大优化了大数据的运行速度，那么只有求和看上去并不是那么优美，于是我们考虑从求和上下手。

首先，我们知道我们求的是从1-m，1-n的组合数之和，那么我们是不是就是求记录组合数的数组中一个(n,m)大小的矩阵？

那么二维前缀和就是很显然的一件事了吧。。。

最后不要忘记了m和n的顺序，一般人的习惯可能会导致出错，我就调了好久啊。。。

还有记得二维前缀和有可能减出负数，所以记得先加后取模（常规错误）

按照这个优化写完就成了这样：（比赛时写的扩展gcd。。。）

但是赛后用费马小定理写了一下：（震惊了。。。快了这么多。。。）

后话，其实如果不带式子利用递推会更快一些，但是直接代式子也能过所以在这里就不啰嗦了。。。

最后，附上本题代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #define LL long long
 5 #define mod 19260817
 6 using namespace std;
 7 LL js[1005],f[1005][1005],sum[1005][1005];
 8 inline LL qpow(LL x,LL y)
 9 {
10     LL ans=1;
11     while(y!=0)
12     {
13         if(y&1)
14         {
15             ans=ans%mod*(x%mod)%mod;
16         }
17         x=x%mod*(x%mod)%mod;
18         y>>=1;
19     }
20     return ans;
21 }
22 inline LL inv(LL w)
23 {
24     return qpow(w,mod-2); 
25 }
26 inline void pre_fir()
27 {
28     js[0]=1;
29     js[1]=1;
30     for(register int i=1; i<=1000; i++)
31     {
32         js[i]=js[i-1]%mod*i%mod;
33         js[i]%=mod;
34     }
35     for(register int i=1; i<=1000; i++)
36     {
37         for(register int j=1; j<=i; j++)
38         {
39             f[i][j]=js[i]%mod*inv(js[j]%mod*js[i-j]%mod)%mod;
40         }
41     }
42     for(register int i=1; i<=1000; i++)
43     {
44         for(register int j=1; j<=1000; j++)
45         {
46             sum[i][j]=(((sum[i-1][j]-sum[i-1][j-1]+mod)%mod+sum[i][j-1])%mod+f[i][j])%mod;
47         }
48     }
49 }
50 int main()
51 {
52     LL q,n,m;
53     cin>>q;
54     pre_fir();
55     for(register int i=1; i<=q; i++)
56     {
57         scanf("%lld%lld",&n,&m);
58         printf("%lld
",sum[m][n]%mod);
59     }
60     return 0;
61 }