QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#593986 | #7634. Cards | ucup-team3519# | AC ✓ | 7173ms | 11088kb | C++20 | 6.1kb | 2024-09-27 17:47:56 | 2024-09-27 17:47:56 |
Judging History
answer
#include <bits/stdc++.h>
template <int m>
struct ModInt {
private:
int raw_;
using mint = ModInt;
using i64 = int64_t;
public:
ModInt() {
raw_ = 0;
}
template <typename T>
ModInt(const T &v) {
raw_ = v % m;
}
int value() const {
return (raw_ + m) % m;
}
mint &operator+=(const mint &rhs) {
raw_ = (raw_ + rhs.raw_) % m;
return *this;
}
mint &operator-=(const mint &rhs) {
raw_ = (raw_ - rhs.raw_) % m;
return *this;
}
mint &operator*=(const mint &rhs) {
raw_ = (i64)raw_ * rhs.raw_ % m;
return *this;
}
mint &operator/=(const mint &rhs) {
raw_ = (i64)raw_ * qpow(rhs.raw_, m - 2) % m;
return *this;
}
friend mint operator+(const mint &lhs, const mint &rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint &lhs, const mint &rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint &lhs, const mint &rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint &lhs, const mint &rhs) {
return mint(lhs) /= rhs;
}
static constexpr int mod() {
return m;
}
static constexpr int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) {
res = (i64)res * a % m;
}
a = (i64)a * a % m, b >>= 1;
}
return res;
}
};
template <class Z>
class Poly : public std::vector<Z> {
static std::vector<int> rev;
static std::vector<Z> w;
static void dft(auto f, int n) {
if (rev.size() != n) {
rev.resize(n);
for (int i = 0; i < n; i++) {
rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? n >> 1 : 0);
}
}
if (w.size() < n) {
int k = __builtin_ctz(w.size());
w.resize(n);
while ((1 << k) < n) {
auto e =
Z::qpow(31, 1 << (__builtin_ctz(Z::mod() - 1) - k - 1));
for (int i = 1 << (k - 1); i < (1 << k); ++i) {
w[i * 2] = w[i];
w[i * 2 + 1] = w[i] * e;
}
++k;
}
}
for (int i = 0; i < n; ++i) {
if (i < rev[i]) {
std::swap(f[i], f[rev[i]]);
}
}
for (int i = 1; i < n; i *= 2) {
for (int j = 0; j < n; j += i * 2) {
auto g = f + j, h = f + j + i;
for (int k = 0; k < i; ++k) {
const Z p = g[k], q = h[k] * w[i + k];
g[k] = p + q, h[k] = p - q;
}
}
}
}
static void idft(auto f, int n) {
std::reverse(f + 1, f + n);
dft(f, n);
const Z inv = (1 - Z::mod()) / n;
for (int i = 0; i < n; ++i) {
f[i] *= inv;
}
}
public:
using std::vector<Z>::vector;
using std::vector<Z>::size;
using std::vector<Z>::resize;
using std::vector<Z>::empty;
Poly &operator+=(const Poly &rhs) {
if (rhs.size() > size()) {
resize(rhs.size());
}
for (int i = 0; i < rhs.size(); ++i) {
this->operator[](i) += rhs[i];
}
return *this;
}
Poly &operator+=(const Z &rhs) {
if (size() == 0) {
resize(1);
}
this->operator[](0) += rhs;
return *this;
}
Poly &operator-=(const Poly &rhs) {
if (rhs.size() > size()) {
resize(rhs.size());
}
for (int i = 0; i < rhs.size(); ++i) {
this->operator[](i) -= rhs[i];
}
return *this;
}
Poly &operator*=(const Z &rhs) {
for (Z &i : *this) {
i *= rhs;
}
return *this;
}
Poly &operator*=(const Poly &rhs) {
int N = 1, n = size() + rhs.size() - 1;
while (N < n) {
N *= 2;
}
Poly &f(*this), g(N);
f.resize(N);
std::copy(rhs.begin(), rhs.end(), g.begin());
dft(f.begin(), N);
dft(g.begin(), N);
for (int i = 0; i < N; ++i) {
f[i] *= g[i];
}
idft(f.begin(), N);
f.resize(n);
return f;
}
};
template <class Z>
std::vector<int> Poly<Z>::rev;
template <class Z>
std::vector<Z> Poly<Z>::w{0, 1};
using mint = ModInt<998244353>;
using poly = Poly<mint>;
using namespace std;
using ll=long long;
const int D=500;
poly bfcalc(poly ndp,vector<mint>p,int t,int mxsz){
poly dp;
while(t--){
dp.clear();
dp.resize(ndp.size()+2);
for(int i=0;i<ndp.size();i++){
if(i==0){
dp[0]+=ndp[0];
continue;
}
for(int j=0;j<=4;j++){
int d=i+j-2;
if(d<0)d=0;
dp[d]+=ndp[i]*p[j];
}
}
swap(dp,ndp);
//if(ndp.size()>mxsz)ndp.resize(mxsz);
}
return ndp;
}
void solve(){
int n,m;
cin>>n>>m;
n++;
vector<mint>p(5);
mint sum=0;
int mxsz=2*m+1;
for(int i=0;i<=4;i++){
ll x;
cin>>x;
p[i]=x;
sum+=x;
}
for(int i=0;i<=4;i++){
p[i]/=sum;
}
poly tms,cur;
cur.resize(100000+10);
cur[n]=1;
poly cur2=cur;
tms.resize(2*D+1);
tms[2*D]=1;
tms=bfcalc(tms,p,D,mxsz);
// cur2=bfcalc(cur2,p,m,mxsz);
int lft=m;
while(lft>0){
if(lft<=D){
cur=bfcalc(cur,p,lft,mxsz);
lft=0;
}
else{
poly h;
h.resize(2*D+1);
for(int i=0;i<2*D;i++){
h[i]=cur[i];
}
h=bfcalc(h,p,D,mxsz);
if(cur.size()<=2*D){
cur=h;
lft-=D;
continue;
}
poly g;
g.resize(cur.size()-2*D);
for(int i=2*D;i<cur.size();i++){
g[i-2*D]=cur[i];
}
g*=tms;
cur=h;
cur+=g;
if(cur.size()>mxsz)
cur.resize(mxsz);
lft-=D;
}
}
// if(cur[0].value()!=cur2[0].value()){
// cout<<"???"<<'\n';
// cout<<cur[0].value()<<' '<<cur2[0].value();
// cout<<'\n';
// return;
// }
cur[0]=1-cur[0];
cout<<cur[0].value();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
solve();
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 10ms
memory: 4804kb
input:
1 1 1 1 1 1 1
output:
399297742
result:
ok 1 number(s): "399297742"
Test #2:
score: 0
Accepted
time: 7169ms
memory: 10960kb
input:
100000 100000 1234 4567 7890 4321 54321
output:
348074135
result:
ok 1 number(s): "348074135"
Test #3:
score: 0
Accepted
time: 7171ms
memory: 10912kb
input:
100000 100000 1 2 3 4 5
output:
639188342
result:
ok 1 number(s): "639188342"
Test #4:
score: 0
Accepted
time: 7150ms
memory: 10876kb
input:
100000 100000 5 4 3 2 1
output:
211669278
result:
ok 1 number(s): "211669278"
Test #5:
score: 0
Accepted
time: 6ms
memory: 3888kb
input:
0 0 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 2464ms
memory: 6532kb
input:
1 50000 1 1 1 1 1
output:
548880636
result:
ok 1 number(s): "548880636"
Test #7:
score: 0
Accepted
time: 10ms
memory: 4804kb
input:
50000 1 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 7161ms
memory: 11088kb
input:
100000 100000 234 666 7655 12234 0
output:
45268602
result:
ok 1 number(s): "45268602"
Test #9:
score: 0
Accepted
time: 7154ms
memory: 10912kb
input:
99999 99999 12345 54332 12345 65432 34444
output:
360543661
result:
ok 1 number(s): "360543661"
Test #10:
score: 0
Accepted
time: 7136ms
memory: 10888kb
input:
99998 99998 1 1 1 1 1
output:
602326230
result:
ok 1 number(s): "602326230"
Test #11:
score: 0
Accepted
time: 7173ms
memory: 10900kb
input:
99998 99997 1 1 1 1 1
output:
159752985
result:
ok 1 number(s): "159752985"
Test #12:
score: 0
Accepted
time: 7141ms
memory: 10908kb
input:
99997 100000 1 2 3 4 5
output:
139603712
result:
ok 1 number(s): "139603712"
Test #13:
score: 0
Accepted
time: 7168ms
memory: 10940kb
input:
100000 99997 1 2 2 1 3232323
output:
363030953
result:
ok 1 number(s): "363030953"
Test #14:
score: 0
Accepted
time: 9ms
memory: 3924kb
input:
0 0 0 0 1 0 0
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 332ms
memory: 5892kb
input:
10000 10000 91095828 93770094 5303328 491263 50290308
output:
135900098
result:
ok 1 number(s): "135900098"
Test #16:
score: 0
Accepted
time: 330ms
memory: 5884kb
input:
9226 9995 62366139 253808 1929312 491263 4375669
output:
812662634
result:
ok 1 number(s): "812662634"
Test #17:
score: 0
Accepted
time: 332ms
memory: 5976kb
input:
18641 10000 1061 4359 1330 13764 16043
output:
112339046
result:
ok 1 number(s): "112339046"
Extra Test:
score: 0
Extra Test Passed