CodeForces 140 E. New Year Garland(콤보 수학+dp)

Description
n열, i열 li 위치, 현재 모든 위치에 m가지 색깔로 색칠을 하려면 만족해야 합니다.
1. 한 줄씩 서로 인접한 위치마다 다른 색
2. 인접 배열에 사용되는 색상 세트가 다름
질문 시나리오 수, 결과 모드 p
Input
첫 번째 줄에 세 개의 정수 n, m, p를 입력한 후 n개의 정수 리(1≤n, m≤106, 2≤p≤109, 1≤li≤5000, ∑i=1nli≤107)를 입력한다.
Output
프로젝트 수, 결과 모드 p
Sample Input
3 2 1000 3 1 2
Sample Output
8
Solution
p[i][j]는 이미 전 i에 색을 잘 염색하고 i열에 j가지 색을 사용한 방안수를 나타낸다. f[i][j]는 j가지 색으로 i개의 위치에 염색하고 서로 인접한 두 위치의 색이 다른 방안수를 확보하는 것을 의미한다. sum[i]=∑j=1lidp[i][j]는 전 i에 색을 잘 염색한 방안수를 나타낸다.
간단하게 f[i][j]: f[0][0]=1, f[i][j]=f[i-3][j-1]+(j-1)⋅f[i-1][j]
서로 인접한 두 줄의 색 집합이 같지 않은 것을 고려하지 않고 dp[i][j]=sum[i --1] Ajm f[li][j]
만약 i>1 및 j≤li-3-1이라면 현재 색 집합과 이전 줄의 색 집합이 중복되는 비합법적인 상황이 존재합니다. dp[i][j]-3=dp[i-1][j]\j!⋅f[li][j], dp[i-3-1][j]를 구할 때 이미 선택한 색깔과 번호를 고려했기 때문에 분명히 이 선택한 j가지 색깔로 리의 위치를 염색하는 것만 고려할 수 있다. 그래서 j를 곱했다!⋅f[li][j]
정답은sum[n]입니다. 공간 제한으로 1차에서 스크롤할 수 있고 시간 복잡도 O(L)
Code

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int INF=0x3f3f3f3f,maxn=1000005;
int n,m,p,l[maxn],A[5005],fact[5005],f[5005][5005],dp[2][5005],sum[2];
int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++)scanf("%d",&l[i]);
    f[0][0]=1;
    for(int i=1;i<=5000;i++)
        for(int j=1;j<=i;j++)
            f[i][j]=(f[i-1][j-1]+(ll)f[i-1][j]*(j-1)%p)%p;
    A[0]=1;
    for(int i=1;i<=5000;i++)A[i]=(ll)A[i-1]*(m+1-i)%p;
    fact[0]=1;
    for(int i=1;i<=5000;i++)fact[i]=(ll)i*fact[i-1]%p;
    sum[0]=1;
    for(int i=1;i<=n;i++)
    {
        sum[i%2]=0;
        for(int j=1;j<=l[i];j++)
        {
            dp[i%2][j]=(ll)A[j]*sum[1-i%2]%p*f[l[i]][j]%p;
            if(i&&j<=l[i-1])dp[i%2][j]=(dp[i%2][j]-(ll)fact[j]*dp[1-i%2][j]%p*f[l[i]][j]%p+p)%p;
            sum[i%2]=(sum[i%2]+dp[i%2][j])%p; 
        }
    }
    printf("%d
",sum[n%2]);
    return 0;
}