ABC 385G(Counting Buildings-多项式)

求有多少个长度为 n 的分列 P，其从左往右的单调栈长度L§ 和从右往左的单调栈长度R§之差为 k。
Fi,jF_{i,j}Fi,j​ 体现长度为i且差值为j的答案。
Fi,j=Fi−1,j−1+Fi−1,j+1+(i−2)Fi−1,jF_{i,j}=F_{i-1,j-1}+F_{i-1,j+1}+(i-2)F_{i-1,j}Fi,j​=Fi−1,j−1​+Fi−1,j+1​+(i−2)Fi−1,j​
令fi(x)f_i(x)fi​(x)体现[xk][x^k][xk]的系数为Fi,kF_{i,k}Fi,k​的情势幂级数，则有
fi(x)=fi−1(x+1/x+i−2),f1=1f_i(x)=f_{i-1}(x+1/x+i-2),f_1=1fi​(x)=fi−1​(x+1/x+i−2),f1​=1
fi(x)=xn−1∗f1Πi=1n−1(1+(i−1)x+x2)f_i(x)=x^{n-1}*f_1\Pi_{i=1}^{n-1}(1+(i-1)x+x^2)fi​(x)=xn−1∗f1​Πi=1n−1​(1+(i−1)x+x2)

3. int n,k;
4. poly work(int l,int r) {
5.         if(l==r) {
6.                 vector<mi> c(3,1);
7.                 c[1]=l-1;
8.                 return poly(c);
9.         }
10.         else{
11.                 int m=l+r>>1;
12.                 poly ans=work(l,m)*work(m+1,r);
13.                 return ans;
14.         }
15. }
16. int main()
17. {
18.         cin>>n>>k;
19.         if(n==1) return puts("1"),0;
20.         vector<mi> v(1,1);
21.         auto w=poly(v);
22.         poly ans=work(1,n-1);
23. //        ans.dump();
24.         cout<<ans.get(n-1+k)<<endl;
25.        
26. }```

复制代码