Hi, CodeForces! I recently found a way to calculate Riordan Array $T(n,k)$ in $\Theta(1)$ time. So I'm going to share it with you :D↵
↵
#### Definition of 'Riordan Array' in this blog↵
↵
In this blog, Riordan array **doesn't have much to do with generating functions**. I would choose to define it as [A201780 in OEIS](https://oeis.org/A201780), or as the following formula:↵
↵
$$↵
T(n,k)=\begin{cases}↵
0,&k\le 0;\\↵
0,&n<k;\\↵
1,&n=k=1;\\↵
2T(n-1,k)+T(n-1,k-1),&\text{otherwise}.↵
\end{cases}↵
$$↵
↵
It is clear enough that the OEIS page gave only the $\Theta(n^2)$ method to calculate it, as above shows.↵
↵
#### How did I become interested in it?↵
↵
Recently I solved an interesting problem. In the problem it needs to calculate $T(n,k)$ in $\Theta(1)$ time, if we can calculate the binomial coefficient $\binom{x}{y}$ in $\Theta(1)$'s time.↵
↵
<spoiler summary="problem">↵
Given a grid graph sized $10^5\times10^5$, with every original node split into 4 different nodes, as the following shows.↵
↵
<img src="https://cdn.luogu.com.cn/upload/image_hosting/e90ymrrb.png" style="zoom:80%;" />↵
↵
After splitting every node, now we get the graph like this.↵
↵
<img src="https://cdn.luogu.com.cn/upload/image_hosting/cnbzm6w0.png" style="zoom:50%;" />↵
↵
In this way, every node in the new graph can be identified as $(a,b)c$, which means the $c(0\le c\le 3)$-th splitted node of the original node $(a,b)$, as the image above.↵
↵
It is required to calculate the length of the shortest path from $(0,0)c$ to $(a,b)d$, and count the ways, modulo $998,244,353$, of doing so. There are $T$ test cases, and $T,a,b\le 10^5$, so we should solve it in $\Theta(1)$'s time. Note that every edge's length is $1$.↵
↵
</spoiler>↵
↵
I transferred this problem into an easier version: $c=0,2\le d\le 3,a\ge 1,b\ge 1$. Because it is easy to get the shortest path, so we are going to focus on the number of ways. I solved $d=3$, but when $d=2$ it needs to use Riordan Array defined above.↵
↵
Before starting to solve this, let's focus on an important property.↵
↵
**Property S**: the answer of $(0,0)c$ to $(a,b)d$ is just the same as the answer of $(0,0)c'$ to $(b,a)d'$, where $c \oplus c'=d\oplus d'=1$. Here $\oplus$ means `xor`. You may think of symmetry to proof it.↵
↵
**All the observations down are based on a brute force code's output. So you may write a `bfs` one as well.**↵
↵
#### Solving $d=3$↵
↵
When $a>b$, you can observe the output of the bf code, or you can OEIS. When $b=5$, it's [A006975](https://oeis.org/A006975). You can summarize the formulas, and find the answer is:↵
$$↵
\left(3a+b-1,2^{a-b-1}\frac{a+b}{b}\binom{a-1}{b-1}\right)↵
$$↵
(I put the length of the shortest path in it, too).↵
↵
When $a=b$, the answer is $0$.↵
↵
When $a<b$, the answer is the same as the answer for $(b,a)$. This is easy to see, too.↵
↵
#### Solving $d=2$ and $a\ge b$↵
↵
The answer when $d=2$ and $a<b$ can be represented as a formula and has nothing to do with Riordan Array. So I'm going to discard it. When $a\ge b$, the answer is $T(a+2,b+1)$. You can use brute force to check it. So, it leads to the calculation of $T(x,y)$.↵
↵
**I don't know why it has something to do with Riordan arrays, if you know the answer, please comment under this blog or DM me. I will post it as soon as I received the answer.**↵
↵
#### How to get rid of it?↵
↵
We can try to move $(0,0)0$ a little bit. The most optimal way of moving when $a\ge b$ and $d=2$ is either move to $(0,0),1$ using $1$ edge, or move to $(0,1),1$ using $2$ edges, both with only one way to do so. We can first get the shortest path (which is easy), and then use the shorter one to calculate the answer. According to Property S, the answer is among $(a',b')=(b,a)$ and $(a',b')=(b-1,a)$.↵
↵
More formally, we can define an 'add operation' on the answer (length and ways), and a 'multiplying operation'.↵
↵
$$↵
\begin{aligned}↵
&(a,b)+(c,d)=(a+c,bd)\\↵
&(a,b)+(c,d)=\begin{cases}↵
(a,c),&a<c\\↵
(a,c+d),&a=c\\↵
(b,d),&a>c↵
\end{cases}↵
\end{aligned}↵
$$↵
↵
Then the answer can be showed as $\left(S_1+(1,1)\right)\left(+S_2+(2,1)\right)$.↵
↵
And then I solved the problem. Thus, $T(x,y)(0<y\le x,x+y>2)$ can be calculated as follows:↵
↵
1. Solve the problem above with $(a,b,c,d)=(x-2,y-1,0,2)$.↵
2. The number of ways is the answer.↵
↵
It's perfectly $\Theta(1)$.↵
↵
#### Full code for the original problem↵
↵
<spoiler summary="Code">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)↵
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)↵
using namespace std;↵
using ll = long long;↵
constexpr ll mod=998244353;↵
↵
ll fac[6000010], ifac[6000010];↵
ll qpow(ll x, ll y) {↵
if (y < 0)↵
y += mod - 1;↵
ll res = 1;↵
for (; y; y >>= 1) {↵
if (y & 1) {↵
res *= x;↵
res %= mod;↵
}↵
x *= x;↵
x %= mod;↵
}↵
return res;↵
}↵
void init() {↵
fac[0] = 1;↵
rep(i, 1, 6000005)↵
fac[i] = fac[i-1] * i % mod;↵
ifac[6000005] = qpow(fac[6000005], -1);↵
drep(i, 6000005, 1)↵
ifac[i-1] = ifac[i] * i % mod;↵
}↵
ll choose(int x, int y) {↵
return fac[x] * ifac[y] % mod * ifac[x - y] % mod;↵
}↵
ll F(int x,int y){↵
return qpow(2,y)*choose(x+y,y)%mod;↵
}↵
ll G(int x,int y){↵
return qpow(2,y-1)*choose(x+y-1,x-1)%mod*(y+2*x)%mod*qpow(x,-1)%mod;↵
}↵
pair<int,ll> s0(int b,int c,int d){↵
int dis=(b-1)*2+b+(c!=0)+(c==2)+(d!=2)+(d==0);↵
int cnt=b-1+(c==2)+(d==0);↵
return {dis,qpow(2,cnt)};↵
}↵
pair<int,ll>C3(int a,int b){↵
if (!a||!b)return s0(a^b,a?1:0,a?2:3);↵
else if (a>b)return {3*a+b-1,G(b,a-b)};↵
else return {a+3*b-1,G(a,b-a)};↵
}↵
pair<int,ll>C2(int a,int b){↵
if (a>=b){ // T(a+2,b+1)↵
auto [d1,c1]=C3(b,a);↵
auto [d2,c2]=C3(b-1,a);↵
++d1,++++d2;↵
ll cc=0;↵
if (d1==min(d1,d2))cc+=c1;↵
if (d2==min(d1,d2))cc+=c2;↵
return {min(d1,d2),cc%mod};↵
}↵
else return {a+3*b-2,F(a,b-a-1)};↵
}↵
pair<int,ll>calc0(int a,int b,int d){↵
return d==2?C2(a,b):C3(a,b);↵
}↵
pair<int,ll>calc(int a,int b,int d){↵
if (d==2||d==3)return calc0(a,b,d);↵
auto [d1,c1]=calc0(a,b,2);↵
auto [d2,c2]=calc0(a,b,3);↵
d1+=(d!=2)+(d==0);↵
d2+=(d!=3)+(d==1);↵
ll cc=0;↵
if (d1==min(d1,d2))cc+=c1;↵
if (d2==min(d1,d2))cc+=c2;↵
// cout<<c1<<' '<<c2<<' '<<cc<<'\n';↵
return {min(d1,d2),cc%mod};↵
}↵
void solve(){↵
int a,b,c,d;↵
scanf("%d%d%d%d",&a,&b,&c,&d);↵
if (!a&&!b){↵
if (!(c^d))puts("0 1");↵
else if ((c^d)==2)puts("2 2");↵
else puts("1 1");↵
return ;↵
}else if (!a||!b){↵
if (!b)c^=1,d^=1,swap(a,b);↵
auto [dis,cnt]=s0(b,c,d);↵
printf("%d %lld\n",dis,cnt);↵
return ;↵
}↵
if (c&1)c^=1,d^=1,swap(a,b);↵
if (!c){↵
auto [dis,cnt]=calc(a,b,d);↵
printf("%d %lld\n",dis,cnt);↵
return ;↵
}↵
if (c==2){↵
// cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n';↵
auto [d1,c1]=calc(b,a,d^1);↵
auto [d2,c2]=calc(a,b,d);↵
++d1,++++d2;↵
ll cc=0;↵
if (d1==min(d1,d2))cc+=c1;↵
if (d2==min(d1,d2))cc+=c2;↵
printf("%d %lld\n",min(d1,d2),cc%mod);↵
}↵
}↵
int main() {↵
init();↵
int tt;↵
for (scanf("%d",&tt);tt--;solve());↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
#### After reading↵
↵
Thanks for [user:ZifanWang,2024-02-19] for correcting the definition formula and giving a generating function of Riordan Array.↵
Thanks for [user:MatrixGroup,2024-02-19] for giving advice on generating function & the $(a,b)$ operations.↵
↵
<spoiler summary="Chinese editorial for the problem">↵
<img src="https://cdn.luogu.com.cn/upload/image_hosting/3ern48sc.png" alt="picture" style="zoom:150%;" />↵
</spoiler>↵
↵
I would say that it's just magical to connect a math sequence with a CP problem ^=^!↵
↵
If you have any questions or new ideas, you can comment or DM.↵
↵
Forgive my poor English please :D
↵
#### Definition of 'Riordan Array' in this blog↵
↵
In this blog, Riordan array **doesn't have much to do with generating functions**. I would choose to define it as [A201780 in OEIS](https://oeis.org/A201780), or as the following formula:↵
↵
$$↵
T(n,k)=\begin{cases}↵
0,&k\le 0;\\↵
0,&n<k;\\↵
1,&n=k=1;\\↵
2T(n-1,k)+T(n-1,k-1),&\text{otherwise}.↵
\end{cases}↵
$$↵
↵
It is clear enough that the OEIS page gave only the $\Theta(n^2)$ method to calculate it, as above shows.↵
↵
#### How did I become interested in it?↵
↵
Recently I solved an interesting problem. In the problem it needs to calculate $T(n,k)$ in $\Theta(1)$ time, if we can calculate the binomial coefficient $\binom{x}{y}$ in $\Theta(1)$'s time.↵
↵
<spoiler summary="problem">↵
Given a grid graph sized $10^5\times10^5$, with every original node split into 4 different nodes, as the following shows.↵
↵
<img src="https://cdn.luogu.com.cn/upload/image_hosting/e90ymrrb.png" style="zoom:80%;" />↵
↵
After splitting every node, now we get the graph like this.↵
↵
<img src="https://cdn.luogu.com.cn/upload/image_hosting/cnbzm6w0.png" style="zoom:50%;" />↵
↵
In this way, every node in the new graph can be identified as $(a,b)c$, which means the $c(0\le c\le 3)$-th splitted node of the original node $(a,b)$, as the image above.↵
↵
It is required to calculate the length of the shortest path from $(0,0)c$ to $(a,b)d$, and count the ways, modulo $998,244,353$, of doing so. There are $T$ test cases, and $T,a,b\le 10^5$, so we should solve it in $\Theta(1)$'s time. Note that every edge's length is $1$.↵
↵
</spoiler>↵
↵
I transferred this problem into an easier version: $c=0,2\le d\le 3,a\ge 1,b\ge 1$. Because it is easy to get the shortest path, so we are going to focus on the number of ways. I solved $d=3$, but when $d=2$ it needs to use Riordan Array defined above.↵
↵
Before starting to solve this, let's focus on an important property.↵
↵
**Property S**: the answer of $(0,0)c$ to $(a,b)d$ is just the same as the answer of $(0,0)c'$ to $(b,a)d'$, where $c \oplus c'=d\oplus d'=1$. Here $\oplus$ means `xor`. You may think of symmetry to proof it.↵
↵
**All the observations down are based on a brute force code's output. So you may write a `bfs` one as well.**↵
↵
#### Solving $d=3$↵
↵
When $a>b$, you can observe the output of the bf code, or you can OEIS. When $b=5$, it's [A006975](https://oeis.org/A006975). You can summarize the formulas, and find the answer is:↵
$$↵
\left(3a+b-1,2^{a-b-1}\frac{a+b}{b}\binom{a-1}{b-1}\right)↵
$$↵
(I put the length of the shortest path in it, too).↵
↵
When $a=b$, the answer is $0$.↵
↵
When $a<b$, the answer is the same as the answer for $(b,a)$. This is easy to see, too.↵
↵
#### Solving $d=2$ and $a\ge b$↵
↵
The answer when $d=2$ and $a<b$ can be represented as a formula and has nothing to do with Riordan Array. So I'm going to discard it. When $a\ge b$, the answer is $T(a+2,b+1)$. You can use brute force to check it. So, it leads to the calculation of $T(x,y)$.↵
↵
**I don't know why it has something to do with Riordan arrays, if you know the answer, please comment under this blog or DM me. I will post it as soon as I received the answer.**↵
↵
#### How to get rid of it?↵
↵
We can try to move $(0,0)0$ a little bit. The most optimal way of moving when $a\ge b$ and $d=2$ is either move to $(0,0),1$ using $1$ edge, or move to $(0,1),1$ using $2$ edges, both with only one way to do so. We can first get the shortest path (which is easy), and then use the shorter one to calculate the answer. According to Property S, the answer is among $(a',b')=(b,a)$ and $(a',b')=(b-1,a)$.↵
↵
More formally, we can define an 'add operation' on the answer (length and ways), and a 'multiplying operation'.↵
↵
$$↵
\begin{aligned}↵
&(a,b)
&(a,b)+(c,d)=\begin{cases}↵
(a,c),&a<c\\↵
(a,c+d),&a=c\\↵
(b,d),&a>c↵
\end{cases}↵
\end{aligned}↵
$$↵
↵
Then the answer can be showed as $
↵
And then I solved the problem. Thus, $T(x,y)(0<y\le x,x+y>2)$ can be calculated as follows:↵
↵
1. Solve the problem above with $(a,b,c,d)=(x-2,y-1,0,2)$.↵
2. The number of ways is the answer.↵
↵
It's perfectly $\Theta(1)$.↵
↵
#### Full code for the original problem↵
↵
<spoiler summary="Code">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)↵
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)↵
using namespace std;↵
using ll = long long;↵
constexpr ll mod=998244353;↵
↵
ll fac[6000010], ifac[6000010];↵
ll qpow(ll x, ll y) {↵
if (y < 0)↵
y += mod - 1;↵
ll res = 1;↵
for (; y; y >>= 1) {↵
if (y & 1) {↵
res *= x;↵
res %= mod;↵
}↵
x *= x;↵
x %= mod;↵
}↵
return res;↵
}↵
void init() {↵
fac[0] = 1;↵
rep(i, 1, 6000005)↵
fac[i] = fac[i-1] * i % mod;↵
ifac[6000005] = qpow(fac[6000005], -1);↵
drep(i, 6000005, 1)↵
ifac[i-1] = ifac[i] * i % mod;↵
}↵
ll choose(int x, int y) {↵
return fac[x] * ifac[y] % mod * ifac[x - y] % mod;↵
}↵
ll F(int x,int y){↵
return qpow(2,y)*choose(x+y,y)%mod;↵
}↵
ll G(int x,int y){↵
return qpow(2,y-1)*choose(x+y-1,x-1)%mod*(y+2*x)%mod*qpow(x,-1)%mod;↵
}↵
pair<int,ll> s0(int b,int c,int d){↵
int dis=(b-1)*2+b+(c!=0)+(c==2)+(d!=2)+(d==0);↵
int cnt=b-1+(c==2)+(d==0);↵
return {dis,qpow(2,cnt)};↵
}↵
pair<int,ll>C3(int a,int b){↵
if (!a||!b)return s0(a^b,a?1:0,a?2:3);↵
else if (a>b)return {3*a+b-1,G(b,a-b)};↵
else return {a+3*b-1,G(a,b-a)};↵
}↵
pair<int,ll>C2(int a,int b){↵
if (a>=b){ // T(a+2,b+1)↵
auto [d1,c1]=C3(b,a);↵
auto [d2,c2]=C3(b-1,a);↵
++d1,++++d2;↵
ll cc=0;↵
if (d1==min(d1,d2))cc+=c1;↵
if (d2==min(d1,d2))cc+=c2;↵
return {min(d1,d2),cc%mod};↵
}↵
else return {a+3*b-2,F(a,b-a-1)};↵
}↵
pair<int,ll>calc0(int a,int b,int d){↵
return d==2?C2(a,b):C3(a,b);↵
}↵
pair<int,ll>calc(int a,int b,int d){↵
if (d==2||d==3)return calc0(a,b,d);↵
auto [d1,c1]=calc0(a,b,2);↵
auto [d2,c2]=calc0(a,b,3);↵
d1+=(d!=2)+(d==0);↵
d2+=(d!=3)+(d==1);↵
ll cc=0;↵
if (d1==min(d1,d2))cc+=c1;↵
if (d2==min(d1,d2))cc+=c2;↵
// cout<<c1<<' '<<c2<<' '<<cc<<'\n';↵
return {min(d1,d2),cc%mod};↵
}↵
void solve(){↵
int a,b,c,d;↵
scanf("%d%d%d%d",&a,&b,&c,&d);↵
if (!a&&!b){↵
if (!(c^d))puts("0 1");↵
else if ((c^d)==2)puts("2 2");↵
else puts("1 1");↵
return ;↵
}else if (!a||!b){↵
if (!b)c^=1,d^=1,swap(a,b);↵
auto [dis,cnt]=s0(b,c,d);↵
printf("%d %lld\n",dis,cnt);↵
return ;↵
}↵
if (c&1)c^=1,d^=1,swap(a,b);↵
if (!c){↵
auto [dis,cnt]=calc(a,b,d);↵
printf("%d %lld\n",dis,cnt);↵
return ;↵
}↵
if (c==2){↵
// cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n';↵
auto [d1,c1]=calc(b,a,d^1);↵
auto [d2,c2]=calc(a,b,d);↵
++d1,++++d2;↵
ll cc=0;↵
if (d1==min(d1,d2))cc+=c1;↵
if (d2==min(d1,d2))cc+=c2;↵
printf("%d %lld\n",min(d1,d2),cc%mod);↵
}↵
}↵
int main() {↵
init();↵
int tt;↵
for (scanf("%d",&tt);tt--;solve());↵
return 0;↵
}↵
```↵
↵
</spoiler>↵
↵
#### After reading↵
↵
Thanks for [user:ZifanWang,2024-02-19] for correcting the definition formula and giving a generating function of Riordan Array.↵
Thanks for [user:MatrixGroup,2024-02-19] for giving advice on generating function & the $(a,b)$ operations.↵
↵
<spoiler summary="Chinese editorial for the problem">↵
<img src="https://cdn.luogu.com.cn/upload/image_hosting/3ern48sc.png" alt="picture" style="zoom:150%;" />↵
</spoiler>↵
↵
I would say that it's just magical to connect a math sequence with a CP problem ^=^!↵
↵
If you have any questions or new ideas, you can comment or DM.↵
↵
Forgive my poor English please :D
