HDU-6578

题目链接

HDU6578

思路

观察到n很小，然后只有4个数字所以我们考虑用DP，来写，状态为dp[i][j][k][l]即把{0,1,2,3}最后出现的位置排序后就是i,j,k,l,例如[0,0,1,1,2,3,1]对应的状态就是dp[2][5][6][1]，然后考虑t+1个数出现的转移方程我们可以得到

dp[i][k][m-1][m]+=dp[i][j][k][m-1]
dp[i][j][m-1][m]+=dp[i][j][k][m-1]
dp[i][j][k][m]+=dp[i][j][k][m-1]
dp[j][k][m-1][m]+=dp[i][j][k][m-1]

考虑上面那个例子在后面在上0,1,2,3就可以得到这个状态转移方程，显然这个需要n^4的空间，不够，观察到它的状态只与m-1相关，所以我们创建两个数组来更新，一个是当前的，一个是上一个状态的即可。滚动掉一维，用时间来换取空间。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 998244353;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 1e2+10;
vector<pair<int,int>>v[200];
int dp[2][N][N][N];
int main(){
	int t;scanf("%d",&t);
	while(t--){
		int n,k;
		ll ans = 0;
		scanf("%d %d",&n,&k);
		for(int i=1;i<=n;i++)v[i].clear();
		for(int i=0;i<k;i++){
			int l,r,x;
			scanf("%d %d %d",&l,&r,&x);v[r].push_back(make_pair(l,x));
		}
		dp[0][0][0][0]=1;
		for(int m=1,p=1;m<=n;m++,p^=1){
			for(int i=0;i<=m;i++){
				for(int j=0;j<=i;j++){
					for(int k=0;k<=j;k++){
						dp[p][i][j][k]=0;
					}
				}
			}
			for(int i=0;i<m;i++){
				for(int j=0;j<=i;j++){
					for(int k=0;k<=j;k++){
						dp[p][m-1][i][k]=(dp[p][m-1][i][k]+dp[p^1][i][j][k])%mod;
						dp[p][m-1][i][j]=(dp[p][m-1][i][j]+dp[p^1][i][j][k])%mod;
						dp[p][i][j][k]=(dp[p][i][j][k]+dp[p^1][i][j][k])%mod;
						dp[p][m-1][j][k]=(dp[p][m-1][j][k]+dp[p^1][i][j][k])%mod;
					}
				}
			}
			for(int i=0;i<m;i++)
			for(int j=0;j<=i;j++)
			for(int k=0;k<=j;k++)
			for(auto t:v[m])
			if (1 + (i >= t.first) + (j >= t.first) + (k >= t.first) != t.second)
            dp[p][i][j][k] = 0;
		}
		for(int i=0,p=n&1;i<n;i++)
		for(int j=0;j<=i;j++)
		for(int k=0;k<=j;k++)
		{ans=(ans+dp[p][i][j][k])%mod;}
		printf("%lld\n",ans);
	}
}