QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#226596#5408. 计数鸡chenxinyang20060 1ms4044kbC++144.1kb2023-10-26 09:36:322023-10-26 09:36:33

Judging History

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

  • [2023-10-26 09:36:33]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4044kb
  • [2023-10-26 09:36:32]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}

template <int P>
class mod_int
{
    using Z = mod_int;

private:
    static int mo(int x) { return x < 0 ? x + P : x; }

public:
    int x;
    int val() const { return x; }
    mod_int() : x(0) {}
    template <class T>
    mod_int(const T &x_) : x(x_ >= 0 && x_ < P ? static_cast<int>(x_) : mo(static_cast<int>(x_ % P))) {}
    bool operator==(const Z &rhs) const { return x == rhs.x; }
    bool operator!=(const Z &rhs) const { return x != rhs.x; }
    Z operator-() const { return Z(x ? P - x : 0); }
    Z pow(long long k) const
    {
        Z res = 1, t = *this;
        while (k)
        {
            if (k & 1)
                res *= t;
            if (k >>= 1)
                t *= t;
        }
        return res;
    }
    Z &operator++()
    {
        x < P - 1 ? ++x : x = 0;
        return *this;
    }
    Z &operator--()
    {
        x ? --x : x = P - 1;
        return *this;
    }
    Z operator++(int)
    {
        Z ret = x;
        x < P - 1 ? ++x : x = 0;
        return ret;
    }
    Z operator--(int)
    {
        Z ret = x;
        x ? --x : x = P - 1;
        return ret;
    }
    Z inv() const { return pow(P - 2); }
    Z &operator+=(const Z &rhs)
    {
        (x += rhs.x) >= P && (x -= P);
        return *this;
    }
    Z &operator-=(const Z &rhs)
    {
        (x -= rhs.x) < 0 && (x += P);
        return *this;
    }
    Z operator-()
    {
        return -x;
    }
    Z &operator*=(const Z &rhs)
    {
        x = 1ULL * x * rhs.x % P;
        return *this;
    }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
#define setO(T, o)                                  \
    friend T operator o(const Z &lhs, const Z &rhs) \
    {                                               \
        Z res = lhs;                                \
        return res o## = rhs;                       \
    }
    setO(Z, +) setO(Z, -) setO(Z, *) setO(Z, /)
#undef setO
    
    friend istream& operator>>(istream& is, mod_int& x)
    {
        long long tmp;
        is >> tmp;
        x = tmp;
        return is;
    }
    friend ostream& operator<<(ostream& os, const mod_int& x)
    {
        os << x.val();
        return os;
    }
};

using Z = mod_int<mod>;
Z power(Z p,ll k){
    Z ans = 1;
    while(k){
        if(k % 2 == 1) ans *= p;
        p *= p;
        k /= 2;
    }
    return ans;
}
int n;
int q[305],h[305];

Z M[305][305];
Z calc(){
    Z ans = 1;
    rep(j,1,n){
        int pos = -1;
        rep(i,j,n) if(M[i][j].val()) pos = i;
        if(pos == -1) return 0;

        if(pos != j){
            ans *= -1;
            rep(k,1,n) swap(M[j][k],M[pos][k]);
        }
        Z r = Z(1) / M[j][j];
        rep(k,1,n) M[j][k] *= r;
        rep(i,j + 1,n){
            r = M[i][j];
            rep(k,1,n) M[i][k] -= M[j][k] * r;
        }
    }
    rep(i,1,n) ans *= M[i][i];
    return ans;
}

int main(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%d",&q[i]);
    rep(i,1,n) scanf("%d",&h[i]);
    rep(i,1,n){
        rep(j,1,n) M[i][j] = 1;
    }
    rep(i,1,n){
        rep(j,i + 1,n){
            rep(k,max(1,q[j] - h[i]),n) M[i][k] *= -1;
        }
    }
    Z ans = calc(),prd = 1;
    rep(i,1,n) prd *= i;
    ans = (ans + prd) / 2;
    printf("%d\n",ans.val());
	return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 20
Accepted
time: 1ms
memory: 3952kb

input:

20
20 4 15 16 11 3 7 18 9 5 13 8 6 12 2 10 1 17 14 19
-7 -11 9 -3 -20 -13 -18 15 0 8 0 12 -16 -19 8 -9 -4 -2 6 -10

output:

699910446

result:

ok 1 number(s): "699910446"

Test #2:

score: -20
Wrong Answer
time: 1ms
memory: 4020kb

input:

20
11 6 3 18 17 19 4 8 10 15 12 16 1 13 7 14 5 20 9 2
13 9 -1 1 9 -11 -19 8 -5 -11 -4 3 17 1 8 1 0 -11 -16 -10

output:

200788270

result:

wrong answer 1st numbers differ - expected: '694405422', found: '200788270'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 30
Accepted
time: 0ms
memory: 3972kb

input:

15
14 4 15 10 11 3 7 1 9 5 13 8 6 12 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

output:

985377138

result:

ok 1 number(s): "985377138"

Test #12:

score: -30
Wrong Answer
time: 1ms
memory: 4044kb

input:

15
1 2 12 4 8 13 6 5 9 3 11 10 7 14 15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

output:

486254961

result:

wrong answer 1st numbers differ - expected: '985385330', found: '486254961'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%