QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#593986#7634. Cardsucup-team3519#AC ✓7173ms11088kbC++206.1kb2024-09-27 17:47:562024-09-27 17:47:56

Judging History

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

  • [2024-09-27 17:47:56]
  • 评测
  • 测评结果:AC
  • 用时:7173ms
  • 内存:11088kb
  • [2024-09-27 17:47:56]
  • 提交

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