Codeforces Round ＃100 E. New Year Garland ＆ 2021 CCPC Subpermutation

E. New Year Garland

The question ：
use $m$ Colored balls of different colors decorate $n$ Christmas tree on the first floor . The first of Christmas tree $i$ Layer just by $l_i$ A string of colored balls , And the adjacent colored balls in the same layer have different colors , At the same time, the color sets of the colored balls used in the adjacent two layers are different . Ask how many decoration schemes there are , The answer is right $p$ modulus .$(n,m<=1e6,l_i<=5000,2<=p<=1e9)$,${\sum }_1^n{l}_i<=1e7$;

Ideas ：
Don't consider the limitation of color set between two adjacent layers , Only consider how to calculate the different colors of adjacent colored balls on the same layer ; Consider using $DP$ To calculate , Definition $f[i][j]$, The representative length is $i$ And just used $1-j$ The number of color schemes （ It represents the number ！！！ Before use $j$ Color ）;
So the transfer is $f[i][j]=f[i-1][j-1]+f[i-1][j]\ast (j-1)$; The former $i-1$ Two positions are used $j-1$ Color , So the first $i$ The first position must be used $j$ One color , If the former $i-1$ Positions have been used $j$ Color , So the first $i$ As long as there is disagreement between the two positions $i-1$ Color conflict of ;
Sure $O(({\max }_1^n{l}_i{)}^2)$ Preprocessing $f$ Array ;
Next, consider the limitations of two adjacent layers , The color sets of two adjacent layers cannot be the same ;
Definition $S[i]$ representative $1-i$ The total number of schemes that meet the requirements of the layer ,$dp[i][j]$ representative $1-i$ The layer meets the requirements and the $i$ Layer used before $j$ The number of color schemes ;
Easy to get $S[i]={\sum }_1^{min(l_i,m)}dp[i][j]\ast C_m^j\ast j!$; That is, enumerate the second $i$ The number of colors of the layer , Each scheme uses $C_m^j$, Take out the color set , Multiply by the total arrangement of the number of colors to be the number of schemes ;
The next question is $dp$ Array transfer , It needs to be considered that it cannot be the same as the color selection scheme of the previous layer ：
$dp[i][j]={\sum }_1^{min(l_i,m)}f[l[i]][j]\ast (S[i-1]-dp[i-1][j]\ast j!)$
That is, enumerate the second $i$ Layers are in several colors , The number of programmes is $f[l[i]][j]$, Take the front $i-1$ Layer all legal schemes minus the same scheme as the current color set ;
Last $S[n]$ That's the answer. ;
Then the topic needs some $trick$ To get through ：
1、 It's not hard to find out ,$dp$ Arrays are scrollable , After scrolling, you can solve the problem of space ;
2、$dp$ It needs to be emptied when transferring , Or add a judgment , To avoid illegal transfer
3、 In the process of transfer , Yes $C_m^j\ast j!$, however $m$ It's big , And the modulus is uncertain , There may be no inverse , But it can be found that , This formula can be simplified , After simplification ：$\frac{m!}{(m-j)!}$, That is to say $m$ Of $j$ The power of descent , Can be pretreated to get ;

Code ：

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long 

ll mod;
ll n,m;
ll l[1000050];
ll dp[5005][5005];
ll S[1000050];
ll dpp[2][5005];
ll jie[1000050];
ll ji[5006];
int main(){
    
	scanf("%lld%lld%lld",&n,&m,&mod);
	for(int i=1;i<=n;i++)scanf("%lld",&l[i]);
	dp[0][0]=1;
	jie[0]=1;
	ji[0]=1;
	for(int i=1;i<=5000;i++)ji[i]=ji[i-1]*i%mod;
	for(int i=1;i<=m;i++)jie[i]=jie[i-1]*(m-i+1)%mod;
	for(int i=1;i<=5000;i++){
    
		for(int j=1;j<=5000;j++){
    
			dp[i][j]=(dp[i-1][j-1]%mod+dp[i-1][j]*(j-1)%mod)%mod;
		}
	}
	int now=1;
	for(int i=1;i<=min(l[1],m);i++){
    
		S[1]=(S[1]+dp[l[1]][i]*jie[i]%mod)%mod;
		dpp[now][i]=dp[l[1]][i];
	}
	for(int i=2;i<=n;i++){
    
		int to=now^1;
		for(int j=1;j<=min(l[i],m);j++){
    
			if(j<=l[i-1])dpp[to][j]=dp[l[i]][j]*((S[i-1]-dpp[now][j]*ji[j]%mod+mod)%mod)%mod;
			else dpp[to][j]=dp[l[i]][j]*S[i-1]%mod;
			S[i]=(S[i]+dpp[to][j]*jie[j]%mod)%mod;	
		}
		now=to;
	}
	printf("%lld\n",S[n]);
	return 0;
}

Subpermutation

The question ：
Sign interpretation ：

• $p_n$: n The whole arrangement . for example , $p_3$={1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1} .
• $S_n$: n The set of all permutations . for example , $S_3$={ {1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}.
• $f(s,t)$: $s$ Medium is equal to $t$ The number of consecutive subsequences of . for example , f({1,2,12,1,2},{1,2})=2.

$T$ Time to ask ,$T<=1e5$, Every time I ask , Given $n$ and $m$,$1<=m<=n<=1e6$, For each inquiry , Calculation ${\sum }_{t\in S_m}f(p_n,t)$$mod$$1e9+7$.
Ideas ：
First consider , When $m$ The elements are arranged in a $n$ The case in the meta arrangement , And $1-m$ It's in the same paragraph , Any arrangement in this paragraph is ok , Other elements can be arranged in any way , So the total number of schemes is $m!\ast (n-m+1)!$
Next , consider $m$ The meta arrangement spans two adjacent $n$ The arrangement of elements , You can consider A property of total permutation ： Assume that the current arrangement is $p_1,p_2,\cdots ,p_n$ , And meet $\exists k\in [1,n-1]$,$\forall i\in [k+1,n-1],p_i>p_{i+1}$ , And $p_k<p_{k+1}$;
Then there is the next permutation , And the arrangement of writing $p_1,p_2,\cdots ,p_{k-1},p_j,p_n,p_{n-1},\cdots ,p_{j+1},p_k,p_{j-1},\cdots ,p_{k+1}$ , among $p_j>p_k$ And is the first greater than $p_k$ The number of .
That is, when the arrangement can be written $p_1,p_2,\cdots ,p_k<p_{k+1}>p_{k+2}>\cdots >p_n$ when , There is a next permutation , And will exchange the next largest number in the back to the front , Other numbers are flipped in order .
take $k$ This position is called Change point , Next we follow the $m$ The starting position of the meta arrangement $i$ stay $k$ Discuss the left and right respectively ：
1、$i<=k$, hypothesis $m$ The elements are arranged next $n$ The end position of the meta arrangement is $j$, It's not hard to find out , Next arranged $1-j$ The position and current arrangement of $1-j$ The numbers are the same , It also needs the present $n$ The permutation of elements satisfies $1-j$ and $i-n$ All are $1-m$ Number of numbers , The number of schemes that meet this condition is $m!\ast (n-m)!$, But need to satisfy $i<=k$, therefore $m!$ The whole arrangement of is too much , Need to subtract $i-n$ There is no change point , Also and from $m$ Selected from the number $n-i+1$ Number , Arrange them in descending order , Other positions can be arranged randomly , So the number of solutions is $(n-m)!\ast (m!-C_m^{n-i+1}\ast (m-n+i-1)!)$

2、$i>=k+1$, First, consider whether the change point will be $m$ Meta permutation , And the next arrangement $p_1,p_2,\cdots ,p_{k-1},p_j,p_n,p_{n-1},\cdots ,p_{j+1},p_k,p_{j-1},\cdots ,p_{k+1}$, Exchange the next largest value $p_j$, Because what we need is $m$ Meta permutation ($1-m$) As a subsequence , If the change point of the next arrangement $p_j$ stay $m$ Meta permutation , Then the original sequence $p_k<p_j$, It must also be in the arrangement , This is related to the condition $i>=k+1$ Not in conformity with , So the change point will not be $m$ Meta permutation , hypothesis $m$ The elements are arranged next $n$ The end position of the meta arrangement is $j$, It's not hard to find out , Next arranged $1-j$ The position and current arrangement of $1-j$ The numbers are the same , It also needs the present $n$ The permutation of elements satisfies $1-j$ and $i-n$ All are $1-m$ Number of numbers .

because $i>=k+1$ therefore ($i-n$) All numbers of are in descending order , hypothesis $m$ The elements are arranged next $n$ The end position of the meta arrangement is $j$, Next sequence $1-j$ It doesn't matter in order , The number of programmes is $C_m^{n-i+1}\ast (m-n+i-1)!$, At the same time, it needs to meet the change points $k$ stay $j-i$ Between , And $i-j$ It cannot be monotonically descending , The number of programmes is $((n-m)!-1)$, So the total number of schemes in this case is $C_m^{n-i+1}\ast (m-n+i-1)!\ast ((n-m)!-1)$

So the general answer is $m!\ast (n-m+1)!+{\sum }_{i=n-m+2}^n(n-m)!\ast (m!-C_m^{n-i+1}\ast (m-n+i-1)!)+C_m^{n-i+1}\ast (m-n+i-1)!\ast ((n-m)!-1)$

Because there are many groups asking , This formula needs to be simplified , After expansion, it is found that it can offset , Readers try it on their own , Here are the results :
$m!\ast (n-m+1)!+(m-1)\ast m!\ast (n-m)!-m!\ast {\sum }_{i=n-m+2}^n\frac{1}{(n-i+1)!}$

${\sum }_{i=n-m+2}^n\frac{1}{(n-i+1)!}={\sum }_{i=1}^{m-1}\frac{1}{i!}$

This formula , It can be obtained by preprocessing ; Then the answer to each question is ok $O(1)$ We have found ;

Code ：

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long 

const ll mod=1e9+7;
ll qp(ll x,ll n){
    
	ll ans=1;
	while(n){
    
		if(n&1)ans=ans*x%mod;
		x=x*x%mod;
		n/=2;
	}
	return ans;
}
ll t,n,m;
ll jie[1000060];
ll inv[1000050];
ll dp[1000050];
int main(){
    
	scanf("%lld",&t);
	jie[0]=1;
	for(int i=1;i<=1000000;i++)jie[i]=jie[i-1]*i%mod;
	inv[1000000]=qp(jie[1000000],mod-2);
	for(int i=1000000;i>=1;i--)inv[i-1]=inv[i]*i%mod;
	for(int i=1;i<=1000000;i++)dp[i]=(dp[i-1]+inv[i])%mod;
	while(t--){
    
		scanf("%lld%lld",&n,&m);
		ll ans=jie[m]*jie[n-m+1]%mod;
		ans=(ans+(m-1)*jie[m]%mod*jie[n-m]%mod)%mod;
		ans=(ans-jie[m]*dp[m-1]%mod+mod)%mod;
		printf("%lld\n",ans);
	}
	return 0;
}