Submission #29825351

---

Source Code Expand

// wargang

// 	Tell me why
// 	Ain't nothin' but a heartache
// 	Tell me why
// 	Ain't nothin' but a mistake
// 	Tell me why
// 	I never wanna hear you say
// 	I want it that way

#include <bits//stdc++.h>
using namespace std;

// MACROS
#define int                     long long
#define pb                      push_back
#define MAX                     2e18+5
#define MIN                     -2e18-5
#define mod                     998244353
#define eps                     1e-9
#define set(x)                  memset(x, 0, sizeof(x))
#define ff                      first
#define ss                      second
#define rep(i,a,b)              for(int i=a;i<b;i++)
#define sz(x)                   (int)x.size()
#define endl                    "\n"
#define deb(x)                  cout << #x << "=" << x << endl
#define deb2(x, y)              cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x, y, z)           cout << #x << "=" << x << "," << #y << "=" << y<< "," << #z << "=" << z << endl
#define deb4(x, y, z, a)        cout << #x << "=" << x << "," << #y << "=" << y<< "," << #z << "=" << z << "," << #a << "=" << a << endl
#define all(x)                  x.begin(), x.end()

typedef pair<int, int>          pii;
typedef vector<int>             vi;
typedef vector<pii>             vpii;
typedef map<int, int>            mpii;
typedef set<int>                seti;
template<typename T, typename T1>T amax(T &a, T1 b) {if (b > a)a = b; return a;}
template<typename T, typename T1>T amin(T &a, T1 b) {if (b < a)a = b; return a;}

int mpow(int base, int exp);


// cout << fixed << setprecision(9) <<
const int N = 1000 + 5;
int n, m;
int dp[N][12][12][12];
// dp[i][j][k][l] = no. of sequences with lis array = {j, k, l}

void wargang() {
	cin >> n >> m;
	dp[0][m + 1][m + 1][m + 1] = 1;
	for (int i = 0; i < n; i++) {
		for (int fir = 1; fir <= m + 1; fir++) {
			for (int sec = fir; sec <= m + 1; sec++) {
				for (int third = sec; third <= m + 1; third++) {
					for (int x = 1; x <= m; x++) {
						if (x <= fir) {
							dp[i + 1][x][sec][third] += dp[i][fir][sec][third];
							dp[i + 1][x][sec][third] %= mod;
						} else if (x <= sec) {
							dp[i + 1][fir][x][third] += dp[i][fir][sec][third];
							dp[i + 1][fir][x][third] %= mod;
						} else if (x <= third) {
							dp[i + 1][fir][sec][x] += dp[i][fir][sec][third];
							dp[i + 1][fir][sec][x] %= mod;
						}
					}
					// deb4(i, fir, sec, third);
					// deb(dp[i][fir][sec][third]);
				}
			}
		}
	}
	int ans = 0;
	for (int fir = 1; fir <= m; fir++) {
		for (int sec = fir + 1; sec <= m; sec++) {
			for (int third = sec + 1; third <= m; third++) {
				// deb4(fir, sec, third, dp[n][fir][sec][third]);
				ans += dp[n][fir][sec][third];
				ans %= mod;
			}
		}
	}
	cout << ans << endl;


}



int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
	// for getting input from input.txt
	freopen("input.txt", "r", stdin);
	// for writing output to output.txt
	freopen("output.txt", "w", stdout);
#endif
	int t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++) {

		// cout<<"Case #"<<i<<": ";

		wargang();


	}
	return 0;
}

int mpow(int base, int exp) {
	base %= mod;
	int result = 1;
	while (exp > 0) {
		if (exp & 1) result = ((int)result * base) % mod;
		base = ((int)base * base) % mod;
		exp >>= 1;
	}
	return result;
}

Submission Info

Judge Result