QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#227071 | #4842. Rectangle Placement | JerryBlack_ZJNU | AC ✓ | 1ms | 3512kb | C++20 | 5.1kb | 2023-10-26 20:55:49 | 2023-10-26 20:55:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define fi first
#define se second
#define lowbit(x) (x&(-x))
const int mod=998244353;
const double eps=1e-12;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
#define popcnt __builtin_popcount
int dcmp(double x){if(fabs(x)<eps)return 0;return x>0?1:-1;}
// #define int ll
template<typename T>
int normalize(T value, int mod) {
if (value < -mod || value >= 2 * mod) value %= mod;
if (value < 0) value += mod;
if (value >= mod) value -= mod;
return value;
}
template<int mod>
struct static_modular_int {
using mint = static_modular_int<mod>;
int value;
static_modular_int() : value(0) {}
static_modular_int(const mint &x) : value(x.value) {}
template<typename T, typename U = std::enable_if_t<std::is_integral<T>::value>>
static_modular_int(T value) : value(normalize(value, mod)) {}
template<typename T>
mint power(T degree) const {
degree = normalize(degree, mod - 1);
mint prod = 1, a = *this;
for (; degree > 0; degree >>= 1, a *= a)
if (degree & 1)
prod *= a;
return prod;
}
mint inv() const {
return power(-1);
}
mint& operator=(const mint &x) {
value = x.value;
return *this;
}
mint& operator+=(const mint &x) {
value += x.value;
if (value >= mod) value -= mod;
return *this;
}
mint& operator-=(const mint &x) {
value -= x.value;
if (value < 0) value += mod;
return *this;
}
mint& operator*=(const mint &x) {
value = int64_t(value) * x.value % mod;
return *this;
}
mint& operator/=(const mint &x) {
return *this *= x.inv();
}
friend mint operator+(const mint &x, const mint &y) {
return mint(x) += y;
}
friend mint operator-(const mint &x, const mint &y) {
return mint(x) -= y;
}
friend mint operator*(const mint &x, const mint &y) {
return mint(x) *= y;
}
friend mint operator/(const mint &x, const mint &y) {
return mint(x) /= y;
}
mint& operator++() {
++value;
if (value == mod) value = 0;
return *this;
}
mint& operator--() {
--value;
if (value == -1) value = mod - 1;
return *this;
}
mint operator++(int) {
mint prev = *this;
value++;
if (value == mod) value = 0;
return prev;
}
mint operator--(int) {
mint prev = *this;
value--;
if (value == -1) value = mod - 1;
return prev;
}
mint operator-() const {
return mint(0) - *this;
}
bool operator==(const mint &x) const {
return value == x.value;
}
bool operator!=(const mint &x) const {
return value != x.value;
}
bool operator<(const mint &x) const {
return value < x.value;
}
template<typename T>
explicit operator T() {
return value;
}
friend std::istream& operator>>(std::istream &in, mint &x) {
std::string s;
in >> s;
x = 0;
for (const auto c : s)
x = x * 10 + (c - '0');
return in;
}
friend std::ostream& operator<<(std::ostream &out, const mint &x) {
return out << x.value;
}
static int primitive_root() {
if constexpr (mod == 1000000007) return 5;
if constexpr (mod == 998244353) return 3;
if constexpr (mod == 786433) return 10;
static int root = -1;
if (root != -1)
return root;
std::vector<int> primes;
int value = mod - 1;
for (int i = 2; i * i <= value; i++)
if (value % i == 0) {
primes.push_back(i);
while (value % i == 0)
value /= i;
}
if (value != 1) primes.push_back(value);
for (int r = 2;; r++) {
bool ok = true;
for (auto p : primes) {
if ((mint(r).power((mod - 1) / p)).value == 1) {
ok = false;
break;
}
}
if (ok) return root = r;
}
}
};
// constexpr int MOD = 1000000007;
constexpr int MOD = 998244353;
using mint = static_modular_int<MOD>;
mint binom(mint n,mint m)
{
mint res=1;
for(mint i=0;i<m;i++)
{
res=res*(n-i)/(m-i);
}
return res;
}
void solve()
{
mint n,m;
cin>>n>>m;
cout<<mint(11)*binom(n,4)*binom(m,4)+
mint(6)*binom(n,4)*binom(m,3)+
mint(6)*binom(n,3)*binom(m,4)+
binom(n,4)*binom(m,2)+
binom(n,2)*binom(m,4)<<endl;
}
/*
*/
#undef int
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);
// cout<<fixed<<setprecision(15);
// int _;cin>>_;while(_--)
{
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3476kb
input:
4 5
output:
275
result:
ok 1 number(s): "275"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
723435135 239873451
output:
832099301
result:
ok 1 number(s): "832099301"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
10348683 1000000000
output:
959472414
result:
ok 1 number(s): "959472414"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
1000000000 886687075
output:
994294391
result:
ok 1 number(s): "994294391"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3412kb
input:
238133469 977550485
output:
181382226
result:
ok 1 number(s): "181382226"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
895943525 1000000000
output:
574248092
result:
ok 1 number(s): "574248092"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3408kb
input:
1000000000 772281920
output:
2306050
result:
ok 1 number(s): "2306050"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
123728314 859786182
output:
722858859
result:
ok 1 number(s): "722858859"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
76505681 1000000000
output:
94904116
result:
ok 1 number(s): "94904116"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3408kb
input:
1000000000 952844073
output:
632222340
result:
ok 1 number(s): "632222340"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3416kb
input:
599257776 36989190
output:
592333335
result:
ok 1 number(s): "592333335"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3404kb
input:
257067834 1000000000
output:
520152555
result:
ok 1 number(s): "520152555"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3392kb
input:
1000000000 133406229
output:
769022397
result:
ok 1 number(s): "769022397"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3420kb
input:
484852621 919224885
output:
829749309
result:
ok 1 number(s): "829749309"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
437629987 1000000000
output:
388969627
result:
ok 1 number(s): "388969627"
Test #16:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
1000000000 313968382
output:
471013029
result:
ok 1 number(s): "471013029"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
665414774 326352585
output:
424688776
result:
ok 1 number(s): "424688776"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
1000000000 1000000000
output:
656213933
result:
ok 1 number(s): "656213933"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
4 4
output:
71
result:
ok 1 number(s): "71"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3396kb
input:
4 1000000000
output:
946327704
result:
ok 1 number(s): "946327704"
Test #21:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
1000000000 4
output:
946327704
result:
ok 1 number(s): "946327704"