QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#658713#9477. Topological Sortucup-team3474#WA 0ms3612kbC++232.5kb2024-10-19 17:27:252024-10-19 17:27:33

Judging History

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

  • [2024-10-19 17:27:33]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3612kb
  • [2024-10-19 17:27:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std ;
const int mod = 998244353 ;
int norm(int x)
{
	if(x < 0)  x += mod ;
	if(x >= mod)  x -= mod ;
	return x ;
}
template<class T>
T power(T a , int b)
{
	T res = 1 ;
	for( ; b ; b /= 2 , a *= a)
	if(b % 2)  res *= a ;
	return res ;
}
template<class T>
T print(T a , int b)
{
	T res = 1 ;
	for( ; b ; b /= 2 , a *= a)
	if(b % 2)  res *= a ;
	return res ;
}
struct mint
{
	int x ;
	mint(int x = 0) : x(norm(x)) {}
	int val() const
	{
		return x ;
	}
	mint operator-() const
	{
		return mint(norm(mod - x)) ;
	}
	mint inv() const
	{
		assert(x != 0);
		return power(*this, mod - 2) ;
	}
	mint &operator*=(const mint &rhs)
	{
		x = (long long)x * rhs.x % mod ;
		return *this ;
	}
	mint &operator+=(const mint &rhs)
	{
		x = norm(x + rhs.x) ;
		return *this ;
	}
	mint &operator-=(const mint &rhs)
	{
		x = norm(x - rhs.x) ;
		return *this ;
	}
	mint &operator/=(const mint &rhs)
	{
		return *this *= rhs.inv() ;
	}
	friend mint operator*(const mint &lhs , const mint &rhs)
	{
		mint res = lhs ;
		res *= rhs ;
		return res ;
	}
	friend mint operator+(const mint &lhs , const mint &rhs)
	{
		mint res = lhs ;
		res += rhs ;
		return res ;
	}
	friend mint operator-(const mint &lhs , const mint &rhs)
	{
		mint res = lhs ;
		res -= rhs ;
		return res ;
	}
	friend mint operator/(const mint &lhs , const mint &rhs)
	{
		mint res = lhs ;
		res /= rhs ;
		return res ;
	}
} ;
ostream& operator<<(std::ostream& os, const mint& m) 
{
	os << m.x ;
	return os ;
}
vector<mint> fac ;
vector<mint> inv ;
void init(int n)
{
	n <<= 1 ;
	fac.resize(0) ;
	fac.resize(n + 10 , mint(1)) ;
	inv.resize(0) ;
	inv.resize(n + 10 , mint(1)) ;
	for(int i = 2 ; i <= n ; i ++)  fac[i] = fac[i - 1] * i ;
	inv[n] = fac[n].inv() ;
	for(int i = n - 1 ; i >= 1 ; i --)  inv[i] = inv[i + 1] * (i + 1) ;
}
mint C(int n , int m)
{
	if(n < 0 || m < 0 || n < m)  return mint(0) ;
	return fac[n] * inv[m] * inv[n - m] ;
}
void solve()
{
    int n ;
    cin >> n ;
    mint ans = 1 ;
    long long cnt = 1ll * n * (n - 1) / 2 ;
    int lst = 0 ;
    for(int i = 1 ; i <= n ; i ++)
    {
        int x ;
        cin >> x ;
        if(lst > x)  cnt -= 1 ;
        lst = x ;
    }
    ans = power(mint(2) , cnt % (mod - 1)) ;
    cout << ans << '\n' ;
}
int main()
{
    std::ios::sync_with_stdio(false) , cin.tie(0) ;

    int T = 1 ;
    while (T --)  solve() ;

    return 0 ;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

3
1 3 2

output:

4

result:

ok "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

5
1 2 3 4 5

output:

1024

result:

ok "1024"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

6
4 2 1 5 6 3

output:

4096

result:

ok "4096"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3608kb

input:

492
397 486 227 395 58 452 172 216 130 181 268 482 85 209 365 104 373 90 260 326 252 96 267 106 102 398 441 41 292 314 12 78 242 353 153 424 179 86 299 228 54 390 73 465 396 349 4 10 451 99 342 250 391 6 323 197 159 47 136 473 392 77 125 362 418 255 291 13 238 339 8 28 413 121 384 157 152 23 221 305...

output:

692497022

result:

wrong answer 1st words differ - expected: '73428942', found: '692497022'