QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#229949 | #7634. Cards | ucup-team052# | AC ✓ | 3449ms | 17044kb | C++14 | 5.2kb | 2023-10-28 17:17:59 | 2023-10-28 19:29:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int md = 998244353;
inline int add(int x, int y) {
if (x + y >= md) return x + y - md;
return x + y;
}
inline int sub(int x, int y) {
if (x < y) return x - y + md;
return x - y;
}
inline int mul(int x, int y) {
return 1ull * x * y % md;
}
inline int fpow(int x, int y) {
int ans = 1;
while (y) {
if (y & 1) ans = mul(ans, x);
y >>= 1; x = mul(x, x);
}
return ans;
}
namespace Module{ // by txc
#define ll long long
#define ull unsigned ll
const int N = 1<<20, P = 998244353; // !!
int Pow(ll x, int y=P-2){
int ans=1;
for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
return ans;
}
int w[N];
ull F[N];
struct init{
init(){
for(int i=1; i<N; i<<=1){
w[i]=1;
int t=Pow(3, (P-1)/i/2);
for(int j=1; j<i; ++j) w[i+j]=(ll)w[i+j-1]*t%P;
}
}
} foo;
int Get(int x){ int n=1; while(n<=x) n<<=1; return n;}
void DFT(vector<int> &f, int n){
if((int)f.size()!=n) f.resize(n);
for(int i=0, j=0; i<n; ++i){
F[i]=f[j];
for(int k=n>>1; (j^=k)<k; k>>=1);
}
for(int i=1; i<n; i<<=1) for(int j=0; j<n; j+=i<<1){
int *W=w+i;
ull *F0=F+j, *F1=F+j+i;
for(int k=j; k<j+i; ++k, ++W, ++F0, ++F1){
ull t=(*F1)**W%P;
(*F1)=*F0+P-t, (*F0)+=t;
}
}
for(int i=0; i<n; ++i) f[i]=F[i]%P;
}
void IDFT(vector<int> &f, int n){
f.resize(n), reverse(f.begin()+1, f.end()), DFT(f, n);
int I=1;
for(int i=1; i<n; i<<=1) I=(ll)I*(P+1)/2%P;
for(int i=0; i<n; ++i) f[i]=(ll)f[i]*I%P;
}
vector<int> operator +(const vector<int> &f, const vector<int> &g){
vector<int> ans=f;
ans.resize(max(f.size(), g.size()));
for(int i=0; i<(int)g.size(); ++i) (ans[i]+=g[i])%=P;
return ans;
}
vector<int> operator *(const vector<int> &f, const vector<int> &g){
vector<int> F, G;
F=f, G=g;
int p=Get(f.size()+g.size()-2);
DFT(F, p), DFT(G, p);
for(int i=0; i<p; ++i) F[i]=(ll)F[i]*G[i]%P;
IDFT(F, p);
return F.resize(f.size()+g.size()-1), F;
}
vector<int> Inv(const vector<int> &f, int n=-1){
if(n==-1) n=f.size();
if(n==1) return {Pow(f[0])};
vector<int> ans=Inv(f, (n+1)/2), tmp(f.begin(), f.begin()+n);
int p=Get(n*2-2);
DFT(tmp, p), DFT(ans, p);
for(int i=0; i<p; ++i) ans[i]=(2-(ll)ans[i]*tmp[i]%P+P)*ans[i]%P;
IDFT(ans, p);
return ans.resize(n), ans;
}
vector<int> Mod(const vector<int> &a, const vector<int> &b){
if(b.size()>a.size()) return a;
vector<int> A=a, B=b, iB;
int n=a.size(), m=b.size();
reverse(A.begin(), A.end()), reverse(B.begin(), B.end());
B.resize(n-m+1), iB=Inv(B, n-m+1);
vector<int> d=A*iB;
d.resize(n-m+1), reverse(d.begin(), d.end());
vector<int> r=b*d;
r.resize(m-1);
for(int i=0; i<m-1; ++i) r[i]=(a[i]-r[i]+P)%P;
return r;
}
vector<int> Prod(const vector<int> &a, const vector<int> &b){
return a*b;
}
#undef ll
#undef ull
}
using Module::operator *;
const int N = 1e5 + 5, B = 500;
vector <int> f, g, F, nf;
int a[5], dp[4 * B + 1], ndp[4 * B + 1];
int n, m, ans;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
int sum = 0;
for (int i = 0; i <= 4; i++) sum = add(sum, a[i]);
for (int i = 0; i <= 4; i++) a[i] = mul(a[i], fpow(sum, md - 2));
dp[0] = 1;
for (int i = 1; i <= B; i++) {
memset(ndp, 0, sizeof(ndp));
for (int j = 0; j <= 4 * i; j++) {
for (int k = 0; k <= 4; k++) {
ndp[j + k] = add(ndp[j + k], mul(dp[j], a[k]));
}
}
memcpy(dp, ndp, sizeof(dp));
}
g.resize(4 * B + 1);
for (int i = 0; i <= 4 * B; i++) g[i] = dp[i];
if (n >= m * 2) {
cout << 1 << endl;
return 0;
}
f.resize(m * 2); f[n] = 1;
for (int __ = 1; __ <= m / B; __++) {
nf.clear(); nf.resize(m * 2);
memset(dp, 0, sizeof(dp));
for (int j = 0; j < 2 * B; j++) {
if (j < (int)f.size()) dp[j] = f[j];
}
for (int _ = 0; _ < B; _++) {
memset(ndp, 0, sizeof(ndp));
for (int j = 0; j < 2 * B + 2 * _; j++) {
for (int k = -2; k <= 2; k++) {
if (j + k >= 0) {
ndp[j + k] = add(ndp[j + k], mul(dp[j], a[k + 2]));
}
}
}
memcpy(dp, ndp, sizeof(dp));
}
for (int i = 0; i < 4 * B; i++) {
if (i < m * 2) nf[i] = add(nf[i], dp[i]);
else ans = add(ans, dp[i]);
}
if ((int)f.size() >= 2 * B) {
F.resize((int)f.size() - 2 * B);
for (int j = 0; j < (int)F.size(); j++) F[j] = f[j + 2 * B];
F = F * g;
if ((int)F.size() > m * 2) {
for (int i = m * 2; i < (int)F.size(); i++) ans = add(ans, F[i]);
F.resize(m * 2);
}
for (int i = 0; i < (int)F.size(); i++) nf[i] = add(nf[i], F[i]);
}
f = nf;
}
for (int i = 2 * B; i < (int)f.size(); i++) ans = add(ans, f[i]);
memset(dp, 0, sizeof(dp));
for (int j = 0; j < 2 * B; j++) {
if (j < (int)f.size()) dp[j] = f[j];
}
for (int _ = 0; _ < m % B; _++) {
memset(ndp, 0, sizeof(ndp));
for (int j = 0; j < 2 * B + 2 * _; j++) {
for (int k = -2; k <= 2; k++) {
if (j + k >= 0) {
ndp[j + k] = add(ndp[j + k], mul(dp[j], a[k + 2]));
}
}
}
memcpy(dp, ndp, sizeof(dp));
}
for (int i = 0; i < 4 * B; i++) ans = add(ans, dp[i]);
cout << ans << endl;
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 8136kb
input:
1 1 1 1 1 1 1
output:
399297742
result:
ok 1 number(s): "399297742"
Test #2:
score: 0
Accepted
time: 3316ms
memory: 16916kb
input:
100000 100000 1234 4567 7890 4321 54321
output:
348074135
result:
ok 1 number(s): "348074135"
Test #3:
score: 0
Accepted
time: 3086ms
memory: 16888kb
input:
100000 100000 1 2 3 4 5
output:
639188342
result:
ok 1 number(s): "639188342"
Test #4:
score: 0
Accepted
time: 3162ms
memory: 16972kb
input:
100000 100000 5 4 3 2 1
output:
211669278
result:
ok 1 number(s): "211669278"
Test #5:
score: 0
Accepted
time: 9ms
memory: 8912kb
input:
0 0 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 955ms
memory: 14256kb
input:
1 50000 1 1 1 1 1
output:
548880636
result:
ok 1 number(s): "548880636"
Test #7:
score: 0
Accepted
time: 8ms
memory: 8648kb
input:
50000 1 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 3108ms
memory: 16900kb
input:
100000 100000 234 666 7655 12234 0
output:
45268602
result:
ok 1 number(s): "45268602"
Test #9:
score: 0
Accepted
time: 3072ms
memory: 17024kb
input:
99999 99999 12345 54332 12345 65432 34444
output:
360543661
result:
ok 1 number(s): "360543661"
Test #10:
score: 0
Accepted
time: 3320ms
memory: 16912kb
input:
99998 99998 1 1 1 1 1
output:
602326230
result:
ok 1 number(s): "602326230"
Test #11:
score: 0
Accepted
time: 3449ms
memory: 17024kb
input:
99998 99997 1 1 1 1 1
output:
159752985
result:
ok 1 number(s): "159752985"
Test #12:
score: 0
Accepted
time: 3411ms
memory: 16980kb
input:
99997 100000 1 2 3 4 5
output:
139603712
result:
ok 1 number(s): "139603712"
Test #13:
score: 0
Accepted
time: 3100ms
memory: 17044kb
input:
100000 99997 1 2 2 1 3232323
output:
363030953
result:
ok 1 number(s): "363030953"
Test #14:
score: 0
Accepted
time: 8ms
memory: 8168kb
input:
0 0 0 0 1 0 0
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 119ms
memory: 12024kb
input:
10000 10000 91095828 93770094 5303328 491263 50290308
output:
135900098
result:
ok 1 number(s): "135900098"
Test #16:
score: 0
Accepted
time: 118ms
memory: 8908kb
input:
9226 9995 62366139 253808 1929312 491263 4375669
output:
812662634
result:
ok 1 number(s): "812662634"
Test #17:
score: 0
Accepted
time: 120ms
memory: 12032kb
input:
18641 10000 1061 4359 1330 13764 16043
output:
112339046
result:
ok 1 number(s): "112339046"
Extra Test:
score: 0
Extra Test Passed