QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#407709 | #7634. Cards | i_am_noob | AC ✓ | 1943ms | 23688kb | C++14 | 3.0kb | 2024-05-09 09:45:14 | 2024-05-09 09:45:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
const int N=1<<19,mod=998244353,G=3;
int add(int x, int y){x+=y; if(x>=mod) x-=mod; return x;}
int sub(int x, int y){x-=y; if(x<0) x+=mod; return x;}
int mul(int x, int y){return ((ll)x)*y%mod;}
int Pow(int x, ll y=mod-2){int res=1; for(; y; y>>=1,x=mul(x,x)) if(y&1) res=mul(res,x); return res;}
struct NTT {
ll w[N];
NTT() {
ll dw = Pow(G, (mod - 1) / N);
w[0] = 1;
for (int i = 1; i < N; ++i)
w[i] = mul(w[i - 1], dw);
}
void operator()(vector<int>& a, bool inv = false) { //0 <= a[i] < P
int x = 0, n = a.size();
for (int j = 1; j < n - 1; ++j) {
for (int k = n >> 1; (x ^= k) < k; k >>= 1);
if (j < x) swap(a[x], a[j]);
}
for (int L = 2; L <= n; L <<= 1) {
int dx = N / L, dl = L >> 1;
for (int i = 0; i < n; i += L) {
for (int j = i, x = 0; j < i + dl; ++j, x += dx) {
ll tmp = mul(a[j + dl], w[x]);
a[j + dl] = sub(a[j], tmp);
a[j] = add(a[j], tmp);
}
}
}
if (inv) {
reverse(a.begin() + 1, a.end());
ll invn = Pow(n, mod - 2);
for (int i = 0; i < n; ++i)
a[i] = mul(a[i], invn);
}
}
} ntt;
vector <int> Mul(vector <int> a, vector <int> b, int bound = N) {
int m = a.size() + b.size() - 1, n = 1;
while (n < m) n <<= 1;
a.resize(n), b.resize(n);
ntt(a), ntt(b);
vector <int> out(n);
for (int i = 0; i < n; ++i) out[i] = mul(a[i], b[i]);
ntt(out, true), out.resize(min(m, bound));
return out;
}
int n,m;
vector<int> P(5),pow_P[17];
vector<int> get_pow(int k){
vector<int> res={1};
for(int i=0; i<17; ++i) if(k>>i&1) res=Mul(res,pow_P[i]);
return res;
}
vector<int> solve(int l, int r, vector<int> vec){
if(l==r) return vec;
vector<int> res(sz(vec)+2*(r-l));
if(l+1==r){
for(int i=0; i<sz(vec); ++i) for(int j=0; j<5; ++j) if(i+j-2>=0) res[i+j-2]=add(res[i+j-2],mul(vec[i],P[j]));
return res;
}
if(sz(vec)>2*(r-l)){
vector<int> vec1(vec.begin()+2*(r-l),vec.end());
vec1=Mul(vec1,get_pow(r-l));
for(int i=0; i<sz(vec1); ++i) res[i]=add(res[i],vec1[i]);
}
vector<int> vec1(vec.begin(),vec.begin()+min(2*(r-l),sz(vec)));
int mid=l+r>>1;
vec1=solve(l,mid,vec1);
vec1=solve(mid,r,vec1);
for(int i=0; i<sz(vec1); ++i) res[i]=add(res[i],vec1[i]);
return res;
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> n >> m;
{
int tot=0;
for(int i=0; i<5; ++i) cin >> P[i],tot+=P[i];
for(int i=0; i<5; ++i) P[i]=mul(P[i],Pow(tot));
}
pow_P[0]=P;
for(int i=1; i<17; ++i) pow_P[i]=Mul(pow_P[i-1],pow_P[i-1]);
vector<int> vec(n+1);
vec[n]=1;
vec=solve(0,m,vec);
int res=0;
for(int i=0; i<sz(vec); ++i) res=add(res,vec[i]);
cout << res << "\n";
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 114ms
memory: 16644kb
input:
1 1 1 1 1 1 1
output:
399297742
result:
ok 1 number(s): "399297742"
Test #2:
score: 0
Accepted
time: 1931ms
memory: 23628kb
input:
100000 100000 1234 4567 7890 4321 54321
output:
348074135
result:
ok 1 number(s): "348074135"
Test #3:
score: 0
Accepted
time: 1914ms
memory: 23604kb
input:
100000 100000 1 2 3 4 5
output:
639188342
result:
ok 1 number(s): "639188342"
Test #4:
score: 0
Accepted
time: 1936ms
memory: 23640kb
input:
100000 100000 5 4 3 2 1
output:
211669278
result:
ok 1 number(s): "211669278"
Test #5:
score: 0
Accepted
time: 112ms
memory: 16768kb
input:
0 0 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 817ms
memory: 16692kb
input:
1 50000 1 1 1 1 1
output:
548880636
result:
ok 1 number(s): "548880636"
Test #7:
score: 0
Accepted
time: 107ms
memory: 16692kb
input:
50000 1 1 1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 1933ms
memory: 23688kb
input:
100000 100000 234 666 7655 12234 0
output:
45268602
result:
ok 1 number(s): "45268602"
Test #9:
score: 0
Accepted
time: 1900ms
memory: 23572kb
input:
99999 99999 12345 54332 12345 65432 34444
output:
360543661
result:
ok 1 number(s): "360543661"
Test #10:
score: 0
Accepted
time: 1886ms
memory: 23576kb
input:
99998 99998 1 1 1 1 1
output:
602326230
result:
ok 1 number(s): "602326230"
Test #11:
score: 0
Accepted
time: 1932ms
memory: 23664kb
input:
99998 99997 1 1 1 1 1
output:
159752985
result:
ok 1 number(s): "159752985"
Test #12:
score: 0
Accepted
time: 1844ms
memory: 23660kb
input:
99997 100000 1 2 3 4 5
output:
139603712
result:
ok 1 number(s): "139603712"
Test #13:
score: 0
Accepted
time: 1943ms
memory: 23620kb
input:
100000 99997 1 2 2 1 3232323
output:
363030953
result:
ok 1 number(s): "363030953"
Test #14:
score: 0
Accepted
time: 107ms
memory: 16604kb
input:
0 0 0 0 1 0 0
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 233ms
memory: 16708kb
input:
10000 10000 91095828 93770094 5303328 491263 50290308
output:
135900098
result:
ok 1 number(s): "135900098"
Test #16:
score: 0
Accepted
time: 216ms
memory: 16604kb
input:
9226 9995 62366139 253808 1929312 491263 4375669
output:
812662634
result:
ok 1 number(s): "812662634"
Test #17:
score: 0
Accepted
time: 235ms
memory: 16608kb
input:
18641 10000 1061 4359 1330 13764 16043
output:
112339046
result:
ok 1 number(s): "112339046"
Extra Test:
score: 0
Extra Test Passed