Submission #45833162

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 5010
//#define M
#define mo 998244353
int pw(int a, int b) {
	int ans=1; 
	while(b) {
		if(b&1) ans*=a; 
		a*=a; b>>=1; 
		ans%=mo; a%=mo; 
	}
	return ans; 
}
int fac[N], inv[N], ifac[N]; 
void init(int n) {
	int i; 
	for(i=fac[0]=1; i<=n; ++i) fac[i]=fac[i-1]*i%mo; 
	ifac[n]=pw(fac[n], mo-2); 
	for(i=n-1; i>=0; --i) ifac[i]=ifac[i+1]*(i+1)%mo; 
}
int C(int n, int m) {
	if(m>n) return 0;
	return fac[n]*ifac[m]%mo*ifac[n-m]%mo; 
}
const int iv2=pw(2, mo-2); 
int n, m, i, j, k, T, rt;
char s[5]; 

struct Segment_tree {
	int tot, ls[N<<2], rs[N<<2]; 
	int dp[N<<2][N], c[N<<2]; 
	void build(int &k, int l, int r) {
		if(!k) k=++tot; 
		if(l==r) return ; 
		int mid=(l+r)>>1; 
		build(ls[k], l, mid); 
		build(rs[k], mid+1, r); 
	}
	void Add(int &a, int b) {
		a+=b; if(a>=mo || a<=-mo) a%=mo; 
	}
	void push_up(int k) {
		int i, j; 
		for(i=1; i<=m; ++i) dp[k][i]=(dp[ls[k]][i]+dp[rs[k]][i])%mo; 
		for(i=1; i<=m; ++i) 
			for(j=1; i+j<=m; ++j)
				Add(dp[k][i+j], dp[ls[k]][i]*dp[rs[k]][j]); 
	}
	void add(int k, int l, int r, int x, int y) {
		if(l==r) {
			c[k]+=y; 
			for(int i=0; i<=m; ++i) dp[k][i]=0; 
			for(int i=1; i<=c[k] && i*x<=m; ++i) {
				dp[k][i*x]=C(c[k], i); 
//				printf("dp[%lld][%lld]=%lld\n", k, i*x, dp[k][i*x], C(c[k], i)); 
			}
			return ; 
		}
		int mid=(l+r)>>1; 
		if(x<=mid) add(ls[k], l, mid, x, y); 
		else add(rs[k], mid+1, r, x, y); 
		push_up(k); 
	}
}Seg;

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); m=read(); 
	init(5000); 
	Seg.build(rt, 1, m); 
	for(i=1; i<=n; ++i) {
		scanf("%s%lld", s+1, &k); 
		if(s[1]=='+') j=1; else j=-1; 
		Seg.add(1, 1, m, k, j); 
		printf("%lld\n", Seg.dp[1][m]); 
	}
	return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:88:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   88 |                 scanf("%s%lld", s+1, &k);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~

Judge Result