#888495 (C++14) No.2374 ASKT Subsequences

提出ソース
結果

問題	No.2374 ASKT Subsequences
ユーザー	nocturnal_1202
提出日時	2023-07-07 22:06:01
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	32 ms / 2,000 ms
コード長	14,345 bytes
コンパイル時間	1,941 ms
コンパイル使用メモリ	149,020 KB
実行使用メモリ	19,072 KB
最終ジャッジ日時	2024-07-21 18:08:05
合計ジャッジ時間	3,532 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 28
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <algorithm>
#include <bitset>
#include <complex>
#include <cassert>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <math.h>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include<regex>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,x) for(ll i=0;i<(ll)(x);i++)
#define rrep(i,x) for(ll i=1;i<=(ll)(x);i++)
#define all(v) v.begin(),v.end()
#define veci vector<int>
#define vecl vector<ll>
typedef pair<int, int> pii;
ll INF = 1e17;
ll mod998 = 998244353;
ll mod109 = 1e9 + 7;
//vector<vector<int>> a(n,vector<int>(n));

struct mint {
	const long long mod = mod998;
	long long x;
	mint(long long x_ = 0) : x((x_% mod + mod) % mod) {}

	mint& operator+=(const mint& other) {
		x += other.x;
		if (x >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint& other) {
		x -= other.x;
		if (x < 0) x += mod;
		return *this;
	}
	mint& operator*=(const mint& other) {
		x *= other.x;
		x %= mod;
		return *this;
	}

	mint& operator+=(const long long n) {
		return *this += mint(n);
	}
	mint& operator-=(const long long n) {
		return *this -= mint(n);
	}
	mint& operator*=(const long long n) {
		return *this *= mint(n);
	}

	mint& operator=(const mint& other) {
		x = other.x;
		return *this;
	}
	mint& operator=(const long long n) {
		x = n % mod;
		return *this;
	}

	bool operator==(const mint& other) const {
		return x == other.x;
	}
	bool operator!=(const mint& other) const {
		return x != other.x;
	}

	mint operator-() const {
		mint res(mod - x);
		return res;
	}

	mint operator+(const mint& other) const {
		mint res(x);
		return res += other;
	}
	mint operator-(const mint& other) const {
		mint res(x);
		return res -= other;
	}
	mint operator*(const mint& other) const {
		mint res(x);
		return res *= other;
	}

	mint operator+(const long long n) const {
		mint res(x);
		mint other(n);
		return res += other;
	}
	mint operator-(const long long n) const {
		mint res(x);
		mint other(n);
		return res -= other;
	}
	mint operator*(const long long n) const {
		mint res(x);
		mint other(n);
		return res *= other;
	}

	mint pow(long long n) const {
		if (n == 0) return mint(1);
		mint res = pow(n / 2);
		res *= res;
		if (n % 2) res *= *this;
		return res;
	}
	mint inv() const {
		return pow(mod - 2);
	}
	mint& operator/=(const mint& other) {
		*this *= other.inv();
		return *this;
	}
	mint operator/(const mint& other) const {
		mint res(x);
		return res /= other;
	}
};

struct combination {
	vector<mint> fact, ifact;
	combination(int m) :fact(m + 1), ifact(m + 1) {
		fact[0] = 1;
		for (int i = 1; i <= m; i++) fact[i] = fact[i - 1] * mint(i);
		ifact[m] = fact[m].inv();
		for (int i = m; i >= 1; i--) ifact[i - 1] = ifact[i] * mint(i);
	}
	mint operator()(int n, int k) {//for n<=m, calc nck
		if (k < 0 || k > n) return mint(0);
		return fact[n] * ifact[k] * ifact[n - k];
	}
};

/* UnionFind：素集合系管理の構造体(union by rank)
	isSame(x, y): x と y が同じ集合にいるか。 計算量はならし O(α(n))
	unite(x, y): x と y を同じ集合にする。計算量はならし O(α(n))
*/
struct UnionFind {  // The range of node number is u 0 v n-1
	vector<int> rank, parents;
	UnionFind() {}
	UnionFind(int n) {  // make n trees.
		rank.resize(n, 0);
		parents.resize(n, 0);
		for (int i = 0; i < n; i++) {
			makeTree(i);
		}
	}
	void makeTree(int x) {
		parents[x] = x;  // the parent of x is x
		rank[x] = 0;
	}
	bool isSame(int x, int y) { return findRoot(x) == findRoot(y); }
	void unite(int x, int y) {
		x = findRoot(x);
		y = findRoot(y);
		if (rank[x] > rank[y]) {
			parents[y] = x;
		}
		else {
			parents[x] = y;
			if (rank[x] == rank[y]) {
				rank[y]++;
			}
		}
	}
	int findRoot(int x) {
		if (x != parents[x]) parents[x] = findRoot(parents[x]);
		return parents[x];
	}

};
struct dsu {
public:
	dsu() : _n(0) {}
	explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}

	int merge(int a, int b) {
		assert(0 <= a && a < _n);
		assert(0 <= b && b < _n);
		int x = leader(a), y = leader(b);
		if (x == y) return x;
		if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
		parent_or_size[x] += parent_or_size[y];
		parent_or_size[y] = x;
		return x;
	}

	bool same(int a, int b) {
		assert(0 <= a && a < _n);
		assert(0 <= b && b < _n);
		return leader(a) == leader(b);
	}

	int leader(int a) {
		assert(0 <= a && a < _n);
		if (parent_or_size[a] < 0) return a;
		return parent_or_size[a] = leader(parent_or_size[a]);
	}

	int size(int a) {
		assert(0 <= a && a < _n);
		return -parent_or_size[leader(a)];
	}

	std::vector<std::vector<int>> groups() {
		std::vector<int> leader_buf(_n), group_size(_n);
		for (int i = 0; i < _n; i++) {
			leader_buf[i] = leader(i);
			group_size[leader_buf[i]]++;
		}
		std::vector<std::vector<int>> result(_n);
		for (int i = 0; i < _n; i++) {
			result[i].reserve(group_size[i]);
		}
		for (int i = 0; i < _n; i++) {
			result[leader_buf[i]].push_back(i);
		}
		result.erase(
			std::remove_if(result.begin(), result.end(),
				[&](const std::vector<int>& v) { return v.empty(); }),
			result.end());
		return result;
	}

private:
	int _n;
	// root node: -1 * component size
	// otherwise: parent
	std::vector<int> parent_or_size;
};

//DFSの基本形
/*vector<bool> seen;
void dfs(const vector<vector<int>>& G, int v) {
	seen[v] = true; // v を訪問済にする

	// v から行ける各頂点 next_v について
	for (auto next_v : G[v]) {
		if (seen[next_v]) continue; // next_v が探索済だったらスルー
		dfs(G, next_v); // 再帰的に探索
	}
}*/

//dijkstra法
struct Edge1 {
	long long to;
	long long cost;
};
using GraphE1 = vector<vector<Edge1>>;
using P = pair<long, int>;

/* dijkstra(G,s,dis)
	入力：グラフ G, 開始点 s, 距離を格納する dis
	計算量：O(|E|log|V|)
	副作用：dis が書き換えられる
*/
void dijkstra(const GraphE1& G, int s, vector<long long>& dis) {
	priority_queue<P, vector<P>, greater<P>> pq;  // 「仮の最短距離, 頂点」が小さい順に並ぶ
	dis[s] = 0;
	pq.emplace(dis[s], s);
	while (!pq.empty()) {
		P p = pq.top();
		pq.pop();
		int v = p.second;
		if (dis[v] < p.first) {  // 最短距離で無ければ無視
			continue;
		}
		for (auto& e : G[v]) {
			// 最短距離候補なら priority_queue に追加
			if (dis[e.to] > dis[v] + e.cost) {
				// 最短距離候補なら priority_queue に追加
				dis[e.to] = dis[v] + e.cost;
				pq.emplace(dis[e.to], e.to);
			}
		}
	}
}

/*
Graph G(N);
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	// BFS のためのデータ構造
	vector<int> dist(N, -1); // 全頂点を「未訪問」に初期化
	queue<int> que;

	// 初期条件 (頂点 0 を初期ノードとする)
	dist[0] = 0;
	que.push(0); // 0 を橙色頂点にする

	// BFS 開始 (キューが空になるまで探索を行う)
	while (!que.empty()) {
		int v = que.front(); // キューから先頭頂点を取り出す
		que.pop();

		// v から辿れる頂点をすべて調べる
		for (int nv : G[v]) {
			if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない

			// 新たな白色頂点 nv について距離情報を更新してキューに追加する
			dist[nv] = dist[v] + 1;
			que.push(nv);
		}
	}
*/
void yesno(bool non) {
	if (non)cout << "Yes" << endl;
	else cout << "No" << endl;
}

void noyes(bool non) {
	if (non)cout << "No" << endl;
	else cout << "Yes" << endl;
}

long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

ll gcd(ll a, ll b) {
	if (a % b == 0) {
		return b;
	}
	else {
		return gcd(b, a % b);
	}
}

ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}

//素数判定
bool is_prime(const unsigned n) {
	switch (n) {
	case 0: // fall-through
	case 1: return false;
	} // n > 1 が保証された

	// n より小さい数で n を割って余りを調べる
	// 素数ならば自分より小さい数(1以外)では割り切れない
	for (unsigned i = 2; i * i <= n; ++i) {
		if (n % i == 0) return false;
	}

	return true;
}


//mod mでaの逆元を計算.
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


//素因数分解(O(√N)).
vector<pair<long long, long long> > prime_factorize(long long N) {
	vector<pair<long long, long long> > res;
	for (long long a = 2; a * a <= N; ++a) {
		if (N % a != 0) continue;
		long long ex = 0; // 指数

		// 割れる限り割り続ける
		while (N % a == 0) {
			++ex;
			N /= a;
		}

		// その結果を push
		res.push_back({ a, ex });
	}

	// 最後に残った数について
	if (N != 1) res.push_back({ N, 1 });
	return res;
}
//aをbで何回割れるか(O(logN)).
ll factorcnt(ll a, ll b) {
	ll cnt = 0;
	while (a % b == 0) {
		a = a / b;
		cnt++;
	}
	return cnt;

}

const int MOD = mod998;
vector<long long> fact, fact_inv, inv;
/*  init_nCk :二項係数のための前処理
	計算量:O(n)
*/
void init_nCk(int SIZE) {
	fact.resize(SIZE + 5);
	fact_inv.resize(SIZE + 5);
	inv.resize(SIZE + 5);
	fact[0] = fact[1] = 1;
	fact_inv[0] = fact_inv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < SIZE + 5; i++) {
		fact[i] = fact[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
	}
}
/*  nCk :MODでの二項係数を求める(前処理 int_nCk が必要)
	計算量:O(1)
*/
long long nCk(int n, int k) {
	assert(!(n < k));
	assert(!(n < 0 || k < 0));
	return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD;
}



struct Edge {
	long long u;
	long long v;
	long long cost;
};
bool comp_e(const Edge& e1, const Edge& e2) { return e1.cost < e2.cost; } // 辺を直接比較するための関数
/* Kruskal :クラスカル法で minimum spanning tree を求める構造体
	入力: 辺のvector, 頂点数V
	最小全域木の重みの総和: sum
	計算量: O(|E|log|V|)
*/
struct Kruskal {
	UnionFind uft;
	long long sum;  // 最小全域木の重みの総和
	vector<Edge> edges;
	int V;
	Kruskal(const vector<Edge>& edges_, int V_) : edges(edges_), V(V_) { init(); }
	void init() {
		sort(edges.begin(), edges.end(), comp_e); // 辺の重みでソート
		uft = UnionFind(V);
		sum = 0;
		for (auto e : edges) {
			if (!uft.isSame(e.u, e.v)) { // 閉路にならなければ加える
				uft.unite(e.u, e.v);
				sum += e.cost;
			}
		}
	}
};
//DFSの基本形
/*vector<bool> seen;
void dfs(const vector<vector<int>>& G, int v) {
	seen[v] = true; // v を訪問済にする

	// v から行ける各頂点 next_v について
	for (auto next_v : G[v]) {
		if (seen[next_v]) continue; // next_v が探索済だったらスルー
		dfs(G, next_v); // 再帰的に探索
	}
}*/

//繰り返し二乗法
long long pow(long long a, long long n, long long m) {
	long long ret = 1;
	for (; n > 0; n >>= 1, a = a * a % m) {
		if (n % 2 == 1) {
			ret = ret * a % m;

		}
	}
	return ret;
}

//ios::sync_with_stdio(false);
//std::cin.tie(nullptr);

class BIT
{
public:

	BIT() = default;

	// 長さ size の数列で初期化
	explicit BIT(size_t size)
		: m_bit(size + 1) {}

	// 数列で初期化
	explicit BIT(const std::vector<long long>& v)
		: BIT(v.size())
	{
		for (int i = 0; i < v.size(); ++i)
		{
			add((i + 1), v[i]);
		}
	}

	// 閉区間 [1, r] の合計を返す (1-based indexing)
	long long sum(int r) const
	{
		long long ret = 0;

		for (; 0 < r; r -= (r & -r))
		{
			ret += m_bit[r];
		}

		return ret;
	}

	// 閉区間 [l, r] の合計を返す (1-based indexing)
	long long sum(int l, int r) const
	{
		return (sum(r) - sum(l - 1));
	}

	// 数列の i 番目の要素を加算 (1-based indexing)
	void add(int i, long long value)
	{
		for (; i < m_bit.size(); i += (i & -i))
		{
			m_bit[i] += value;
		}
	}

private:

	std::vector<long long> m_bit;
};

const long long  M = mod998;
typedef vector<ll> vi;
typedef vector<vi> vvi;

template <typename T>
struct RMQ {
	const T INF = numeric_limits<T>::max();
	int n;         // 葉の数
	vector<T> dat; // 完全二分木の配列
	RMQ(int n_) : n(), dat(n_ * 4, INF) { // 葉の数は 2^x の形
		int x = 1;
		while (n_ > x) {
			x *= 2;
		}
		n = x;
	}
	void update(int i, T x) {
		i += n - 1;
		dat[i] = x;
		while (i > 0) {
			i = (i - 1) / 2;  // parent
			dat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2]);
		}
	}
	// the minimum element of [a,b)
	T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
	T query_sub(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) {
			return INF;
		}
		else if (a <= l && r <= b) {
			return dat[k];
		}
		else {
			T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
			T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
			return min(vl, vr);
		}
	}
};

//行列の乗算
vvi matrix_multiply(vvi X, vvi Y) {
	vvi Z(X.size(), vi(Y[0].size()));
	rep(i, X.size()) {
		rep(k, Y.size()) {
			rep(j, Y[0].size()) {
				Z[i][j] = (Z[i][j] + X[i][k] * Y[k][j]) % M;
			}
		}
	}
	return Z;
}

//A^nの計算
vvi matrix_pow(vvi A, ll n) {
	vvi B(A.size(), vi(A[0].size()));
	//単位行列でBを初期化
	rep(i, B.size()) {
		B[i][i] = 1;
	}

	while (n > 0) {
		if (n & 1) { B = matrix_multiply(B, A); }
		A = matrix_multiply(A, A);
		n = n >> 1;
	}
	return B;
}

int main() {

	int n;
	cin >> n;

	vector<int> a(n+1);
	vector<vector<int>> cnt(2005, vector<int>(2005));
	rrep(i, n)cin >> a[i];

	for (int i = 1; i <= n; i++) {

		for (int j = 1; j <= 2000; j++) {

			cnt[i][j] = cnt[i - 1][j];
			if (j == a[i])cnt[i][j]++;
		}

	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {

			if (a[i] <= a[j])continue;
			if (a[j] - 10 <= 0)continue;
			ans += (cnt[i - 1][a[j] - 10]) * (cnt[n][a[i] + 1] - cnt[j][a[i] + 1]);

		}
	}
	cout << ans << endl;

}
yukicoder

結果

ソースコード
