QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#781923 | #5530. No Zero-Sum Subsegment | ASnown | WA | 30ms | 19464kb | C++17 | 4.0kb | 2024-11-25 18:01:58 | 2024-11-25 18:01:58 |
Judging History
answer
#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popc(x) (__builtin_popcountll((x)))
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
using ll=long long;
using uint=uint32_t;
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
namespace asnown {
using i32=int32_t;
using u32=uint32_t;
using i64=int64_t;
using u64=uint64_t;
using i128=__int128_t;
using u128=__uint128_t;
constexpr i32 inverse(i32 a,i32 m) {
i64 r=1;
while(a>1) { r=r*(m-m/a)%m,a=m%a; }
return r;
}
template<i32 m>
class static_modint {
using mint=static_modint;
public:
constexpr static_modint() : v(0) {}
constexpr static_modint(i32 v) : v(normal(v%m)) {}
constexpr static_modint(u32 v) : v(v%m) {}
constexpr static_modint(i64 v) : v(normal(v%m)) {}
constexpr static_modint(u64 v) : v(v%m) {}
constexpr static_modint(i128 v) : v(normal(v%m)) {}
constexpr static_modint(u128 v) : v(v%m) {}
constexpr u32 normal(i32 v) { if(v>=m) v-=m; return v+((v>>31)&m); }
constexpr u32 val() const { return v; }
constexpr static u32 mod() { return m; }
constexpr explicit operator bool() const { return v; }
constexpr mint inv() const { assert(v!=0); return mint(inverse(v,m)); }
constexpr mint pow(i64 b) const { assert(b>=0);
mint a=*this,res=1; for(;b;b>>=1,a*=a) if(b&1) res*=a; return res; }
constexpr mint operator+() const { return *this; }
constexpr mint operator-() const { return mint()-*this; }
constexpr mint& operator+=(const mint &p) { return v=normal(v+p.v),*this; }
constexpr mint& operator-=(const mint &p) { return v=normal(v-p.v),*this; }
constexpr mint& operator++() { return (*this)+=1; }
constexpr mint& operator--() { return (*this)-=1; }
constexpr mint& operator++(i32) { auto tmp=*this; return ++*this,tmp; }
constexpr mint& operator--(i32) { auto tmp=*this; return --*this,tmp; }
constexpr mint& operator*=(const mint &p) { v=i64(v)*p.v%m; return *this; }
constexpr mint& operator/=(const mint &p) { return *this *= p.inv(); }
constexpr friend mint operator+(const mint &p,const mint &q) { return mint(p)+=q; }
constexpr friend mint operator-(const mint &p,const mint &q) { return mint(p)-=q; }
constexpr friend mint operator*(const mint &p,const mint &q) { return mint(p)*=q; }
constexpr friend mint operator/(const mint &p,const mint &q) { return mint(p)/=q; }
constexpr friend std::istream& operator>>(std::istream &is,mint &a) { i64 v; is>>v; a=v; return is; }
constexpr friend std::ostream& operator<<(std::ostream &os,const mint &a) { os<<a.val(); return os; }
constexpr bool operator==(const mint& p) const { return val()==p.val(); }
constexpr bool operator!=(const mint& p) const { return val()!=p.val(); }
private:
u32 v;
};
using modint998244353=static_modint<998244353>;
using modint107=static_modint<1000000007>;
};
using mint=asnown::modint998244353;
const int N = 2e6+26;
mint fac[N],ivf[N];
void Init() {
fac[0]=1;
for(int i=1;i<=2000000;i++) fac[i]=fac[i-1]*i;
ivf[2000000]=fac[2000000].inv();
for(int i=2000000;i>=1;i--) ivf[i-1]=ivf[i]*i;
}
inline mint C(int n,int m) { return n<m||m<0?0:fac[n]*ivf[m]*ivf[n-m]; }
inline mint calc(int b,int c,int d) {
return b+b<=d&&b>=0&&c>=0&&d>=0?C(c+d-b,b)*C(c+d-b-b,c):0;
}
signed main() {
#ifndef ONLINE_JUDGE
#endif
cin.tie(nullptr)->sync_with_stdio(false);
Init();
int T; cin>>T; while(T--)
Solve();
}
void Solve() {
int a,b,c,d; cin>>a>>b>>c>>d;
int s=-a-a-b+c+d+d;
if(s==0) return void(puts("0"));
if(s<0) swap(a,d),swap(b,c),s=-s;
mint ans=calc(b-2,c,d-a-2)*(a+1)+calc(b-1,c-1,d-a-1)*a*2;
if(a>=1) ans+=calc(b,c-2,d-a)*(a-1)+calc(b-1,c,d-a-1)*2+calc(b,c-1,d-a)*2;
ans+=(a==0?calc(b,c,d):0);
printf("%d\n",ans.val());
}
詳細信息
Test #1:
score: 100
Accepted
time: 18ms
memory: 19464kb
input:
5 69 0 0 0 1 1 1 1 0 0 3 3 6 1 0 6 10000 10000 1000000 1000000
output:
1 0 20 2 480402900
result:
ok 5 number(s): "1 0 20 2 480402900"
Test #2:
score: -100
Wrong Answer
time: 30ms
memory: 19400kb
input:
83520 13 1 6 8 13 9 3 14 1 16 13 0 8 12 7 16 10 5 9 15 16 16 15 1 5 11 0 4 12 4 11 15 16 7 1 10 2 6 3 3 15 14 12 0 0 8 12 12 3 0 6 7 16 2 16 15 16 16 16 13 8 13 2 14 7 9 7 0 9 8 4 6 13 16 4 11 11 1 12 4 7 9 4 16 12 13 0 4 5 0 9 1 11 11 0 3 1 11 14 3 3 3 7 3 8 5 4 4 6 7 12 14 2 11 5 6 15 4 9 14 15 11...
output:
0 0 0 0 0 0 52 0 26784 0 0 0 392 0 0 0 0 0 0 0 0 478686 0 136136 0 0 0 0 0 0 0 1680 0 821 0 24024 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8994258 0 0 0 0 0 293930 0 0 156637 166 0 0 0 0 0 0 0 0 0 54 0 0 1248 126 0 0 0 344 0 9867 9520 272 0 0 0 0 0 92820 0 0 4620 0 0 0 0 0 45045 0 0 0 10 0 72442440 0 10854738 ...
result:
wrong answer 83rd numbers differ - expected: '10880', found: '9520'