QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#407709#7634. Cardsi_am_noobAC ✓1943ms23688kbC++143.0kb2024-05-09 09:45:142024-05-09 09:45:15

Judging History

你现在查看的是最新测评结果

  • [2024-05-09 09:45:15]
  • 评测
  • 测评结果:AC
  • 用时:1943ms
  • 内存:23688kb
  • [2024-05-09 09:45:14]
  • 提交

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