QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#548190 | #8820. Exchanging Kubic 2 | chenxinyang2006 | WA | 0ms | 3964kb | C++20 | 4.2kb | 2024-09-05 16:18:48 | 2024-09-05 16:18:48 |
Judging History
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,m;
int valid[405][805];
Z dp[2][2][805],ndp[2][2][805];
Z slv(int v){
rep(p,0,1){
rep(q,0,1) fill(dp[p][q],dp[p][q] + m + 1,0);
}
dp[0][0][0] = 1;
rep(i,1,n){
rep(p,0,1){
rep(q,0,1){
rep(k,1,m){
dp[p][q][k] += dp[p][q][k - 1];
if(valid[i][k]) ndp[p | (k - i <= v)][q | (k - i >= v + n)][k] += dp[p][q][k];
}
}
}
rep(p,0,1){
rep(q,0,1){
copy(ndp[p][q],ndp[p][q] + m + 1,dp[p][q]);
fill(ndp[p][q],ndp[p][q] + m + 1,0);
}
}
}
Z answer = 0;
rep(k,0,m) answer += dp[1][1][k];
return answer;
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d",&n);
rep(i,1,n){
int sz,val;
scanf("%d",&sz);
while(sz--){
scanf("%d",&val);
valid[i][val] = 1;
chkmax(m,val);
}
}
Z answer = 0;
rep(i,-n,m - n) answer += slv(i);
printf("%d\n",answer.val());
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3896kb
input:
5 3 1 2 3 1 2 0 4 0 2 3 4 2 2 3
output:
0
result:
ok "0"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
5 4 1 2 3 7 4 5 7 8 9 4 2 3 6 9 5 0 1 4 7 9 8 0 1 2 3 6 7 8 9
output:
16
result:
ok "16"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
10 8 1 2 3 7 15 17 18 19 11 1 2 5 8 9 10 13 16 18 19 20 12 0 1 4 5 6 7 8 9 11 16 17 19 12 0 1 3 5 9 10 11 15 16 17 18 19 6 2 8 11 15 18 19 11 0 4 6 7 8 10 11 13 16 18 19 13 1 3 4 6 8 9 10 12 13 14 15 19 20 13 2 4 5 8 9 10 11 13 14 15 16 17 20 10 2 3 5 6 8 10 13 14 18 19 12 2 3 4 5 8 9 12 13 15 16 19...
output:
27895
result:
ok "27895"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3964kb
input:
10 12 0 3 4 5 6 7 8 13 14 17 19 20 15 0 1 2 4 5 6 8 9 11 12 13 14 15 18 19 9 2 7 8 9 13 15 16 18 19 17 0 1 2 3 4 5 6 7 8 9 10 11 15 16 17 18 19 17 0 1 2 4 6 7 8 9 10 11 12 14 15 16 17 19 20 17 0 1 2 3 6 8 10 11 12 13 14 15 16 17 18 19 20 15 1 3 4 6 7 9 10 11 12 13 14 15 17 19 20 16 0 1 2 3 5 6 8 9 1...
output:
12754
result:
wrong answer 1st words differ - expected: '625955', found: '12754'