2287. [HZOI 2015] Crazy robot

The question : Starting from the origin , go n Time , Every time up and down, left and right , Only in the first quadrant , Finally, back to the origin, the number of solutions


That's not to mention , The combination number is written to find convolution NTT, And then I didn't think about the first quadrant gg




In fact, that is Carter LAN number

It's just here \(C(i)\) It's No \(\frac{i}{2}\) term , The odd number is 0

Make \(f[n]\) To go n The number of times to go back to the origin ,$$

f[n]=\sum_{i=0}{n}C(i)C(n-i)\binom{n}{i}=n!\sum_{i=0}{n}C(i)\frac{1}{i!}C(n-i)\frac{1}{(n-i)!}

\[
Pay attention to factorial and factorial inverse, don't multiply wrong , Don't lose anything !!!

```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=(1<<18)+5, INF=1e9;
const ll P=998244353;
inline int read(){
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}

ll Pow(ll a, ll b, ll P) {
ll ans=1;
for(; b; b>>=1, a=a*a%P)
if(b&1) ans=ans*a%P;
return ans;
}
namespace NTT{
int n, rev[N], g;
void ini(int lim) {
g=3;
n=1; int k=0;
while(n<lim) n<<=1, k++;
for(int i=0; i<n; i++) rev[i] = (rev[i>>1]>>1) | ((i&1)<<(k-1));
}
void dft(ll *a, int flag) {
for(int i=0; i<n; i++) if(i<rev[i]) swap(a[i], a[rev[i]]);
for(int l=2; l<=n; l<<=1) {
int m=l>>1;
ll wn=Pow(g, flag==1 ? (P-1)/l : P-1-(P-1)/l, P);
for(ll *p=a; p!=a+n; p+=l) {
ll w=1;
for(int k=0; k<m; k++) {
ll t = w*p[k+m]%P;
p[k+m] = (p[k] - t + P)%P;
p[k] = (p[k] + t)%P;
w = w*wn%P;
}
}
}
if(flag==-1) {
ll inv=Pow(n, P-2, P);
for(int i=0; i<n; i++) a[i] = a[i]*inv%P;
}
}
void mul(ll *a, ll *b) {
dft(a, 1);
for(int i=0; i<n; i++) a[i]=a[i]*a[i]%P;
dft(a, -1);
}
}using NTT::dft; using NTT::ini; using NTT::mul;

int n;
ll inv[N], fac[N], facInv[N];
ll a[N], b[N];
ll C(int n, int m) {return fac[n]*facInv[m]%P*facInv[n-m]%P;}
int main() {
//freopen("in","r",stdin);
freopen("crazy_robot.in","r",stdin);
freopen("crazy_robot.out","w",stdout);
n=read(); ini(n+n+1);
inv[1]=1; fac[0]=facInv[0]=1;
for(int i=1; i<=n; i++) {
if(i!=1) inv[i] = (P-P/i)*inv[P%i]%P;
fac[i] = fac[i-1]*i%P;
facInv[i] = facInv[i-1]*inv[i]%P;
}
a[0]=b[0]=1;
for(int i=2; i<=n; i+=2) a[i]=b[i]= C(i, i>>1) * inv[(i>>1)+1] %P * facInv[i] %P;

mul(a, b);
for(int i=0; i<=n; i++) a[i]=a[i]*fac[i]%P;
ll ans=0;
for(int m=0; m<=n; m+=2) (ans += C(n, m) * a[m]%P) %=P;
printf("%lld\n", ans);
}
```\]

BZOJ 2287. [HZOI 2015] Crazy robot [FFT Combination count ] More articles about

  1. 【COGS】2287:[HZOI 2015] Crazy robot FFT+ Carter LAN number + Permutation and combination

    [ The question ][COGS 2287][HZOI 2015] Crazy robot [ Algorithm ]FFT+ Carter LAN number + Permutation and combination [ Answer key ] Consider the one-dimensional case first , Support +1 and -1, Prefix sum cannot be negative , It's in the form of Cartesian numbers . set up C(n) It means the first one ...

  2. [COGS 2287][HZOI 2015] Crazy robot

    Description Question bank link Now there's a robot at the origin in the two-dimensional plane , He can choose to go right every time , turn left , Go down , Go up or not ( You can only walk one space at a time ). The robot can't go to the point where the abscissa is negative or the ordinate is negative . to ...

  3. [HZOI 2015] Crazy robot

    [ Title Description ] Now there's a robot at the origin in the two-dimensional plane He can choose to go right every time , turn left , Go down , Go up or not ( You can only walk one space at a time ) But because of the magic of konjac , The robot can't go to the abscissa is negative or the ordinate is negative ...

  4. COGS2287 [HZOI 2015] Crazy robot

    [ Title Description ] Now there's a robot at the origin in the two-dimensional plane He can choose to go right every time , turn left , Go down , Go up or not ( You can only walk one space at a time ) But because of the magic of konjac , The robot can't go to the abscissa is negative or the ordinate is negative ...

  5. HDU4609 FFT+ Combination count

    HDU4609 FFT+ Combination count Portal :http://acm.hdu.edu.cn/showproblem.php?pid=4609 The question : find n The probability that three sticks from one stick can form a triangle Answer key : ...

  6. BZOJ 4555: [Tjoi2016&amp;Heoi2016] Sum up [ Divide and conquer FFT Combination count | Polynomial inverse ]

    4555: [Tjoi2016&Heoi2016] Sum up The question : seek \[ \sum_{i=0}^n \sum_{j=0}^i S(i,j)\cdot 2^j\cdot j! \\ S It's the second kind of Stirling ...

  7. BZOJ 4555: [Tjoi2016&amp;Heoi2016] Sum up [FFT Combination count Principle of tolerance and exclusion ]

    4555: [Tjoi2016&Heoi2016] Sum up The question : seek \[ \sum_{i=0}^n \sum_{j=0}^i S(i,j)\cdot 2^j\cdot j! \\ S It's the second kind of Stirling ...

  8. 【BZOJ 3027】 3027: [Ceoi2004]Sweet ( Principle of tolerance and exclusion + Combination count )

    3027: [Ceoi2004]Sweet Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 71  Solved: 34 Description John ...

  9. cojs Crazy center of gravity Crazy robot Problem solving report

    Crazy center of gravity It should be easy for people who have played fantasy country strategy games to cut off this topic Let's consider a tree with a leaf , Then the center of gravity moves towards the leaf at most 1 Distance of We only need to record the number of points in the subtree to judge whether to move or not That is to say ...

Random recommendation

  1. firefox flash plug-in unit

    1. Unzip the file : tar -xzvf ***.tar.gz It will work out a file :libflashplayer.so And a directory usr 2. Will file libflashplayer.so Copy to directory   /us ...

  2. JavaScript String practical common operations

    String interception 1. substring()xString.substring(start,end)substring() Is the most commonly used string interception method , It can take two parameters ( Parameter cannot be negative ), They are the beginning of interception ...

  3. Deploy the project to weblogic Prompt that the file is locked , Result in an error

    Deploy the project to weblogic One of them “ Yellow sigh !”. An error is as follows : (1) Deployment is out of date due to changes in the underlying projec ...

  4. JDK Installation and configuration of detailed graphic tutorial

    Purpose : I'm forgetful , It's inevitable that the system will be re installed in the future , It's common for software to be unloaded , Here is a detailed tutorial , First, it's convenient for you to have a look when you reload later : Second, if a beginner is lucky enough to come , You can also give a little reference . I'll start with JDK The download . install . Environmental change ...

  5. linux --&gt; Get the system start time

    Get the system start time One . Preface Time is very important to the operating system , From the kernel level to the application layer , The expression and precision of time are the same .linux The kernel uses a jiffes To calculate the time stamp . The application layer has time.getdaytim ...

  6. Use .net core efcore Automatically generate entity class according to database structure

    Source code github, Updated code https://github.com/leoparddne/GenEntities/ The use of DB yes mysql, All first nuget once mysql.data establish t4 Templates ...

  7. ISP PIPLINE ( 6、 ... and ) AWB

    What is WB(white balance)? When the human visual and nervous systems see white objects , Basically not affected by changes in the environment and serious illusion . Like cloudy days , a sunny day , indoor , Outside , Fluorescent lamp , Incandescent lamp, etc , People still regard white paper as ...

  8. Understand thoroughly Scrapy Middleware ( One )

    Middleware is Scrapy One of the core concepts . Middleware can be used to customize the data before the request of the crawler is initiated or after the request is returned , So we can develop crawlers that can adapt to different situations . " middleware " This Chinese name is the same as the previous chapter ...

  9. lxde Installation and uninstall of and precautions ,lubuntu

    install : $ sudo apt install lxde $ sudo apt install lxde-common After installation , May not be able to shut down and logout, You can use the following installation : $ sudo apt ...

  10. No blowing, no beating ,Python Programming 【315+ Problem 】

    Write it at the front It's graduation season , At the end of the course, everyone “ expect + Helpless pain ” There is no better time than the content review and interview question and answer section every morning [ Near graduation, every day before class 40-60 Minutes to review the previous content . Questions and supplements , Select the students who don't like to talk and answer ]. expect ...