Uoj 551 [unr 4] campus stroll [good polynomial questions (FOG)]

Title Description

Link

$n$ A little bit $m$ Undirected weighted graph with edges ,$1\le$ Border right $\le V$,$Q$ Time to ask , from $x$ To $y$ How many weights sum to $w$ The path of , The path can pass through repeated edges and repeated points .

$1\le n\le 8,0\le m\le 3\ast 10^5,1\le V\le 65000,0\le Q\le 10000$

Topic analysis

violence DP：$dp[i][j][v]=\sum _{k=1}^{n}dp[i][k][v^{\prime }]\ast num[k][j][v-v^{\prime }]$

It's obviously a convolution .

• Can be divided directly NTT, regard as $F_v=F_{v^{\prime }}\ast W_{v-v^{\prime }}$,$F$ It's a matrix , such as Code1 , Stuck time limit , Complexity $O(n^{3}V\log V+n^{2}V{\log }^{2}V)$.
  
  

• You can use some black Technology , Because when divide and conquer, if $l\ne 0$ be $2l>r$, therefore $F_{0,r-l}$ All have been calculated , And then $F_{l,r}$ It's all by $F_{0,l-1}$ Contributed , So use $F_{l,r}\ast F_{0,r-l}$ As new $F_{l,r}$, It's not too heavy or too leaky .
  
  So when we divide and conquer $l\ne 0$ You don't have to continue recursion , It is directly processed at this layer . So the complexity becomes $T(V)=T(\frac{V}{2})+n^{3}V+n^{2}V\log V=O(n^{3}V+n^{2}V\log V)$
  such as Code2 .
  
  

• You can use some high technology
  Make $g_{x,y}$ by $x\to y$ Generating function of path weight and number of corresponding schemes ,$G$ by $g$ Corresponding $n\times n$ Matrix ,$W$ Is the matrix corresponding to the edge weighted polynomial , So there are $G=GW+I$, therefore $G=\frac{I}{I-W}$.
  obviously $W$ The constant term of each polynomial in the matrix is not 1, therefore $I-W$ Inverse , Find the inverse of a matrix whose element is a polynomial , Use the elementary transformation method similar to Gauss elimination , need $n$ The inverse of a polynomial of degree ,$O(n^2)$ Time DFT,$n^3$ Degree point value multiplication and polynomial addition , Complexity $O(n^{3}V+n^{2}V\log V)$, Slightly ( Big ) constant .

  Or change your mind , Make $A(z)$ It means that the weight is $i$ Matrix generating function of the path of , That is, every coefficient of a polynomial is a matrix ,$x^i$ Indicates that the sum of weights is $i$, The elements in the matrix represent the number of schemes , And order $W$ Is the corresponding edge weight matrix polynomial , So there are $A=AW+I$, therefore $A=\frac{I}{I-W}$, But this time $W$ It's a polynomial ,$I$ It is equivalent to the constant term of this polynomial , To find the inverse of a polynomial , Using Newton's iterative method , Yes $x_1=x_0(2-A{x}_0)$
  There are some things to pay attention to in the implementation , Although the polynomial coefficients are matrices , however DFT Because there are only a few times , So each element of the matrix can be DFT. Then the point value of each position is now a matrix , When doing multiplication, you should pay attention to $A{x}_0$ The order of cannot be changed , Because the matrix does not satisfy the commutative law . The formula for the initial Newton iteration is $A{x}_0-I=0$, Then the square is $A{x}_{0}A{x}_0-2A{x}_0+I=0$, namely $A{x}_0(2-A{x}_0)=I$. Because left inverse equals right inverse , So the formula can also be written as $x_{0}A-I=0$, Introduction $x_1=(2-x_{0}A)x_0$, It can be found that the two forms are the same .
  The complexity is also $O(n^{3}V+n^{2}V\log V)$

  such as Code3 .