Solution：P9108 [PA2020] Malowanie płotu

不会简单容斥/ll

显然有一个暴力的 \Theta(nm^2) DP，但是我不会优化。

两个区间 [l_{i-1},r_{i-1}],[l_i,r_i] 如果相交，需要两个条件同时不满足：

如果只需要管一个条件多好啊！这样就只需要记录其中一个端点（条件 1. 需要记录右端点，2. 需要记录左端点）的位置，状态就只有二维了。

于是我们考虑对于每个 1\leq i<n，钦定 i 与 i+1 之间只需要不满足 1. 和 2. 中的某一个，这样就有 2^{n-1} 种条件选取方案。如果某个区间选取方案满足了 k 个位置上的条件那么认为这个方案的权值为 (-1)^k。可以发现所有方案（一共 2^{n-1}\binom m2^n 种）的权值和即为 2^{n-1} 倍的合法方案数。

容易发现如果某个方案不合法，那么在不合法的位置一定恰好满足了一个条件，所以就可以将它的贡献一正一负抵消；合法的方案无论怎么选取条件都是合法的所以会被算恰好 2^{n-1} 次。这样就起到了容斥的效果。

于是设 f_{1/2,i,j} 代表当前在第 i 列，这一列与下一列需要满足条件 1. 或 2.，要记录的端点的位置为 j 的方案权值和。容易用两次差分优化转移。

可以发现 f_1 和 f_2 是对称的，可以合并成一个数组。

#include <algorithm>
#include <iostream>
#include <vector>
#include <bitset>
#include <string>
#include <array>

#define rgall(arr) (arr).begin(),(arr).end()
#define rgcnt(arr,cnt) (arr).begin(),(arr).begin()+(cnt)
#define rgo1(arr,cnt) (arr).begin()+1,(arr).begin()+1+(cnt)
#define rgany(arr,cnt,offset) (arr).begin()+(offset),(arr).begin()+(offset)+(cnt)

using namespace std;

long long fast_pow(long long base,long long exp,long long moder)
{
    long long result;
    for(result=1;exp;exp&1?result=result*base%moder:true,base=base*base%moder,exp>>=1);
    return result;
}

vector<long long> dp,dp0;

int main(int argc,char* argv[],char* envp[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n,m,moder;
    cin>>n>>m>>moder;
    dp.resize(m+4),dp[m]=1;
    for(int i=1;i<=n;i++)
    {
        dp0=dp,fill(rgall(dp),0);
        for(int j=1;j<=m;j++)
        {
            long long a=dp0[m-j+1];
            dp[j]+=a*j%moder,dp[j+1]-=a*(j-1)%moder,dp[m-j+2]-=a;
        }
        for(int j=1;j<=m;j++)
            (dp[j]+=dp[j-1])%=moder;
        for(int j=1;j<=m;j++)
            (dp[j]+=dp[j-1]+moder*2)%=moder;
    }
    long long answer=0;
    for(int j=1;j<=m;j++)
        answer+=dp[j];
    cout<<answer%moder;
    return 0;
}