蒟蒻求助卡常,悬赏一关注
查看原帖
蒟蒻求助卡常,悬赏一关注
569516
C6H6楼主2023/7/9 21:23

也有可能是哪里写挂了,球球大佬卡常

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define int unsigned
const int mod = 998244353;
long long a[200010];
bool flg[200010];
long long inv[110];
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? EOF : *p1++)
const int MAXSIZE = 1 << 22;
char buf[MAXSIZE], *p1, *p2; 
void read(){}
template <class T1, class ...T2>
void read(T1& ret, T2&... rest){
    ret = 0; char c; bool f = false;
    while (!isdigit(c = gc() ) ) f = c == '-';
    while(isdigit(c) ){
    	ret = (ret << 3) + (ret << 1) + (c ^ '0');
    	c = gc();
	}
    if(f) ret = -ret;
    read(rest...);
}
char pbuf[MAXSIZE],*pp=pbuf;
inline void pc(const char &c){
	*pp++=c;
}
inline void print(const long long ret){
	static int sta[35];
	long long x = ret, top = 0;
	bool f = (ret < 0);
	if(ret < 0) x = -x;
	do{sta[top++] = x % 10, x /= 10; }while(x);
	if(f) pc('-');
	while(top) pc(sta[--top] + 48);
}
struct matrix{
    long long a[4][4];
    matrix(){
        memset(a, 0, sizeof(a));
        for(int i = 1; i <= 3; i++) a[i][i] = 1;
    }
}c;
inline long long qmi(long long a, long long b){
	long long ret = 1;
	while(b){
		if(b & 1) ret = ret * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return ret;
}
inline matrix matrix_mul(matrix a, matrix b){
    if(a.a[3][3] != 1 && a.a[1][3] != 1) a = matrix();
    if(b.a[3][3] != 1 && b.a[1][3] != 1) b = matrix();
    memset(c.a, 0, sizeof(c.a));
	for(int i = 1; i < 4; i++)
		for(int k = 1; k < 4; k++)
			for(int j = 1; j < 4; j++)
				c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j] % mod) % mod;
    return c;
}
matrix t[800010];
int siz = 1;
inline void build(int n){
    for(; siz <= n + 1; siz <<= 1);
    for(int i = siz + 1; i <= siz + n; i++){
        long long pi1 = (100 - a[i - siz]) * inv[100] % mod;
        long long pi =  a[i - siz] * inv[100] % mod;
        long long npi = qmi(pi, mod - 2);
        long long ATP[4][4] = {
            {0, 0, 0, 0},
            {0, 1, 0, 0},
            {0, pi1 * (flg[i - siz] == 0) * npi % mod, (flg[i - siz] == 0) * npi, 0},
            {0, (pi1 * npi + 1) % mod, npi, 1}
        };
        for(int j = 1; j <= 3; j++)
            for(int k = 1; k <= 3; k++)
                t[i].a[j][k] = ATP[j][k];
    }
    for(int i = siz - 1; i >= 1; i--) t[i] = matrix_mul(t[i << 1], t[i << 1 | 1]);
}
inline void add(int x){
    long long pi1 = (100 - a[x]) * inv[100] % mod;
    long long pi =  a[x] * inv[100] % mod;
    long long npi = qmi(pi, mod - 2);
    long long ATP[4][4] = {
        {0, 0, 0, 0},
        {0, 1, 0, 0},
        {0, pi1 * (flg[x] == 0) * npi % mod, (flg[x] == 0) * npi, 0},
        {0, (pi1 * npi + 1) % mod, npi, 1}
    };
    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++)
            t[x + siz].a[i][j] = ATP[i][j];
    x += siz;
    x >>= 1;
    for(; x; x >>= 1) t[x] = matrix_mul(t[x << 1], t[x << 1 | 1]);
}
inline matrix query(int l, int r){
    matrix ret = matrix();
    for(l = l + siz - 1, r = r + siz + 1; r ^ l ^ 1; l >>= 1, r >>= 1){
        if(~l & 1) ret = matrix_mul(ret, t[l ^ 1]);
        if(r & 1) ret = matrix_mul(ret, t[r ^ 1]);
    }
    return ret;
}
signed main(){
    int n, q;
    read(n, q);
    for(int i = 1; i <= n; i++) read(a[i]);
    for(int i = 1; i <= 100; i++) inv[i] = qmi(i, mod - 2);
    build(n);
    while(q--){
        int x;
        read(x);
        flg[x] ^= 1;
        add(x);
        matrix tmp;
        memset(tmp.a, 0, sizeof(tmp.a));
        int ATP[4][4] = {
            {0, 0, 0, 0},
            {0, 0, 0, 1},
            {0, 0, 0, 0},
            {0, 0, 0, 0}
        };
        for(int i = 1; i <= 3; i++)
            for(int j = 1; j <= 3; j++)
                tmp.a[i][j] = ATP[i][j];
        tmp = matrix_mul(tmp, query(1, n));
        print(tmp.a[1][1]);
        pc('\n');
    }
    fwrite(pbuf,1,pp-pbuf,stdout);
    return 0;
}
2023/7/9 21:23
加载中...