QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#104798#6132. Repair the ArtworkYaoBIGAC ✓3421ms5500kbC++175.0kb2023-05-11 23:58:572023-05-11 23:59:01

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-11 23:59:01]
  • 评测
  • 测评结果:AC
  • 用时:3421ms
  • 内存:5500kb
  • [2023-05-11 23:58:57]
  • 提交

answer

#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
using namespace std;

template<class A, class B> string to_string(const pair<A, B> &p);
template<class A, class B, class C> string to_string(const tuple<A, B, C> &p);
template<class A, class B, class C, class D> string to_string(const tuple<A, B, C, D> &p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(bool x) { return x ? "true" : "false"; }
template<class A> string to_string(const A &v) {
	bool first = 1;
	string res = "{";
	for (const auto &x: v) {
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}
template<class A, class B> string to_string(const pair<A, B> &p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template<class A, class B, class C> string to_string(const tuple<A, B, C> &p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template<class A, class B, class C, class D> string to_string(const tuple<A, B, C, D> &p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(const H& h, const T&... t) {
	cerr << " " << to_string(h);
	debug_out(t...);
}
#ifndef ONLINE_JUDGE
	#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
	#define debug(...) if (0) puts("No effect.")
#endif

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

/**
 * Author: Yuhao Yao
 * Date: 23-05-11
 * Description: Modular integer with $mod \le 2^{31} - 1$. Note that there are several advantages to use this code:
   1. You do not need to keep writing $\%\, mod$;
   2. It is good to use this struct when doing Gaussian Elimination / Fast Walsh-Hadamard Transform;
   3. Sometimes the input number is greater than $mod$ and this code handles it.
  Do not write things like $mint\{1 / 3\}.pow(10)$ since $1 / 3$ simply equals $0$.
  Do not write things like $mint\{a * b\}$ where $a$ and $b$ are int since you might first have integer overflow.
 * Usage: Define the followings globally:
   const int mod = 998244353;
   using mint = MInt<mod>;
 * Status: tested on https://ac.nowcoder.com/acm/contest/33191/F.
 */
template<const unsigned &mod>
struct MInt {
	using Z = MInt;
	unsigned x; /// start-hash
	MInt(ll a = 0): x(a % mod + mod) { if (x >= mod) x -= mod; }
	explicit operator int() const { return x; }

	Z& operator +=(Z b) { x += b.x; if (x >= mod) x -= mod; return *this; }
	Z& operator -=(Z b) { x += mod - b.x; if (x >= mod) x -= mod; return *this; }
	Z& operator *=(Z b) { x = 1ll * x * b.x % mod; return *this; }
	friend Z operator +(Z a, Z b) { return a += b; }
	friend Z operator -(Z a, Z b) { return a -= b; }
	friend Z operator -(Z a) { return Z{} - a; }
	friend Z operator *(Z a, Z b) { return a *= b; }
	/// end-hash

	// the followings are for ntt and polynomials.
	Z pow(ll k) const { /// start-hash
		Z res = 1, a = *this;
		for (; k; k >>= 1, a = a * a) if (k & 1) res = res * a;
		return res;
	}
	Z& operator /=(Z b) {
		assert(b.x != 0);
		return *this *= b.pow(mod - 2);
	}
	friend Z operator /(Z a, Z b) { return a /= b; }
	friend bool operator ==(Z a, Z b) { return a.x == b.x; }
	friend bool operator !=(Z a, Z b) { return a.x != b.x; }
	friend bool operator <(Z a, Z b) { return a.x < b.x; }

	static unsigned getMod() { return mod; } // ntt need this.
	/// end-hash

	friend istream &operator >>(istream &is, Z &a) {
		ll v; is >> v;
		a = v;
		return is;
	}
	friend string to_string(Z a) { return to_string(a.x); }
};

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	static const unsigned mod = 1e9 + 7;
	using mint = MInt<mod>;

	int cas; cin >> cas; while (cas--) {
		int n, m; cin >> n >> m;
		vi as(n);
		for (auto &x: as) cin >> x;
		vector dp(n + 1, vector<mint>(n * (n + 1) / 2 + 1, 0));
		dp[0][0] = 1;
		rep(p, 0, n - 1) {
			revrep(i, 0, p) {
				if (i != p && as[i] == 1) break;
				if (as[p] == 1 || as[p] == 2) {
					rep(j, 0, p * (p + 1) / 2) if (dp[i][j] != 0) {
						dp[p + 1][j + (p - i) * (p - i + 1) / 2] += (as[p] == 2 ? -1 : 1) * dp[i][j];
					}
				}
			}
		}
		mint ans = 0;
		revrep(i, 0, n) {
			if (i != n && as[i] == 1) break;
			rep(j, 0, n * (n + 1) / 2) if (dp[i][j] != 0) {
				int nj = j + (n - i) * (n - i + 1) / 2;
				ans += mint{nj}.pow(m) * dp[i][j];
			}
		}
		printf("%d\n", (int) ans);
 	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3572kb

input:

3
2 2
2 0
3 2
2 1 0
3 1
2 1 0

output:

8
3
1

result:

ok 3 number(s): "8 3 1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

100
2 1
0 1
2 1
2 1
2 1
1 1
1 6
2
1 14
2
3 12
2 2 2
6 13
2 2 0 2 0 2
7 14
0 0 0 0 2 2 0
5 8
2 2 0 0 0
5 5
2 2 0 0 0
12 3
0 2 0 2 2 0 1 2 2 2 2 0
7 11
2 2 0 1 0 1 0
4 4
2 1 2 2
7 5
1 1 0 0 1 0 0
2 14
2 1
15 17
2 2 1 2 0 0 0 0 2 0 1 0 0 0 0
15 11
1 1 2 0 1 2 0 0 1 0 2 1 1 1 1
15 18
1 0 1 0 2 2 1 2 0 1...

output:

1
1
0
1
1
175715347
833406719
467966815
458805426
650344
2208
537089254
146
7776
1
703335050
123067364
355668256
487954758
53774922
544070885
436748805
369291507
760487845
513270785
501075264
487417783
464534262
979007529
137956839
143317512
648268264
851188473
702545117
946416372
595191705
35054850...

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 461ms
memory: 5500kb

input:

1000
20 673037423
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 774964932
2 2 2
17 730319736
2 2 1 1 2 2 2 2 2 2 2 2 2 1 2 2 1
11 893285699
2 2 2 1 2 1 2 2 2 1 2
16 98149251
1 2 1 2 1 2 1 1 2 1 2 2 2 2 1 2
7 556953277
1 2 2 1 2 2 2
3 228111342
1 1 1
11 640995044
2 2 1 1 2 2 1 1 1 1 1
19 741419324
1 1 2 ...

output:

447486147
204414804
452414918
684654914
763978130
805973365
0
922180033
214948715
401017738
0
201368027
752718484
611006275
848004989
391560729
950934074
202096866
443534870
24665646
482580424
321199514
922369975
152629767
5546104
1
194145234
1
1
1
562381239
648246425
497517379
217016206
961507095
4...

result:

ok 1000 numbers

Test #4:

score: 0
Accepted
time: 3421ms
memory: 5348kb

input:

1000
50 416236992
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
50 657728991
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
50 740461763
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

763259804
476502422
599342821
232859927
793988697
591429049
270188459
585052379
112828376
874793236
511742305
443789116
531138043
829814299
715762187
530976897
659595243
398499036
665696512
377388317
780011237
877457048
769085674
80046792
628967449
305823394
274620920
654337446
807171478
690217437
6...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 273ms
memory: 5332kb

input:

1000
50 598094879
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
50 370102582
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
50 89148477
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

799398716
932856936
764416567
57812598
711885564
231337579
355184372
128337468
66039637
243697360
95147120
522827313
427687773
11613749
119992325
840421248
552748897
2153604
854978507
598264350
888588637
168914307
64499881
640494492
442303426
759524304
392240094
936658374
641034548
250860728
8449099...

result:

ok 1000 numbers