Submission #3429655

---

Source Code Expand

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = (ll)(1e+9) + 7;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
ll dp[301][3][300][300];
vector<P> v[300];
int main() {
	rep(j, 3) {
		dp[0][j][0][0] = 1;
	}
	int n, m; cin >> n >> m;
	rep(i, m) {
		int le, ri, x; cin >> le >> ri >> x; ri--;
		v[ri].push_back({ le,x });
	}
	rep(i, n) {
		rep(k, i + 1) {
			rep(l, i + 1) {
				rep(j, 3) {
					(dp[i + 1][j][k][l] += dp[i][j][k][l])%=mod;
				}
				(dp[i + 1][0][i][l] += dp[i][1][k][l]) %= mod;
				(dp[i + 1][0][k][i] += dp[i][2][k][l]) %= mod;
				(dp[i + 1][1][i][l] += dp[i][0][k][l])%=mod;
				(dp[i + 1][1][k][i] += dp[i][2][k][l])%=mod;
				(dp[i + 1][2][i][l] += dp[i][0][k][l])%=mod;
				(dp[i + 1][2][k][i] += dp[i][1][k][l]) %= mod;
			}
		}
		rep(j, (int)v[i].size()) {
			int le = v[i][j].first; int c = v[i][j].second;
			rep(k, i + 1) {
				rep(l, i + 1) {
					rep(m, 3) {
						if (c == 1) {
							if (k >= le || l >= le)dp[i + 1][m][k][l] = 0;
						}
						if (c == 2) {
							if ((k >= le && l >= le) || (k < le&&l < le))dp[i + 1][m][k][l] = 0;
						}
						if (c == 3) {
							if (k < le || l < le)dp[i + 1][m][k][l] = 0;
						}
					}
				}
			}
		}
	}
	ll out = 0;
	rep(j, 3) {
		rep(k, n) {
			rep(l, n) {
				(out += dp[n][j][k][l]) %= mod;
				//cout << j << " " << k << " " << l << " " << dp[n][j][k][l] << endl;
			}
		}
	}
	out = out * ((mod+1) / 3) % mod;
	cout << out << endl;
	return 0;
}

Submission Info

Judge Result