题解

题目分析

这是一道算法题目，需要根据具体题目要求进行求解。

解题思路

1. 问题分析

• 仔细阅读题目描述，理解题目要求
• 分析输入输出格式和约束条件
• 确定需要使用的算法和数据结构

2. 算法选择

• 根据题目特点选择合适的算法
• 考虑时间复杂度和空间复杂度
• 确保算法能正确处理所有测试用例

3. 实现要点

• 注意边界条件的处理
• 优化输入输出以提高效率
• 确保代码的正确性和鲁棒性

4. 调试和优化

• 使用测试用例验证算法正确性
• 分析性能瓶颈并进行优化
• 确保代码能通过所有测试点

注意事项

• 仔细处理数据类型和精度问题
• 注意数组越界和空指针问题
• 确保算法的时间复杂度符合要求

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<bitset>
#include<queue>
#include<ctime>
#include<cmath>
#include<set>
#include<map>
#define infile(filename) freopen(filename".in","r",stdin)
#define outfile(filename) freopen(filename".out","w",stdout)
#define usefile(filename) infile(filename),outfile(filename)
using namespace std; typedef long long ll; typedef unsigned long long ull; typedef __int128 I;
namespace IO {
	const int BUF=1<<20; static char ch[BUF]={},out[BUF]={},*l=ch,*r=ch,*o=out;
#define FASTIO
#ifdef FASTIO
	inline char gc() { return (l==r&&(r=(l=ch)+fread(ch,1,BUF,stdin),l==r))?EOF:*l++; }
#else
	inline char gc() { return getchar(); }
#endif
	inline void flush() { fwrite(out,1,o-out,stdout),o=out; }
	inline void putc(char ch) { if(o==out+BUF) flush(); *o++=ch; }
	struct flusher{~flusher(){flush();}}_;
}; using IO::gc; using IO::putc;
template <typename T> void read(T &a) { static char fushu,ch; a=fushu=0; do ch=gc(); while(ch!='-'&&(ch<48||ch>57)); if(ch=='-') ch=gc(),fushu=1; do a=(a<<1)+(a<<3)+(ch^48),ch=gc(); while(ch>47&&ch<58); if(fushu) a=-a; }
template <typename T,typename ...Args> void read(T &a,Args &...args) { read(a),read(args...); }
template <typename T> void write(T a) { static char que[114]={},*p=que; if(!a) putc(48); if(a<0) putc('-'),a=-a; while(a) *p++=(a%10)^48,a/=10; while(p!=que) putc(*--p); putc(32); }
template <typename T,typename ...Args> void write(T a,Args ...args) { write(a),write(args...); }
template <typename T> void ckmax(T &a,T b) { if(a<b) a=b; }
template <typename T> void ckmin(T &a,T b) { if(b<a) a=b; }
const int N=1000099,moder=998244353;
int add(int x,int y) { return x+y>=moder?x+y-moder:x+y; } int Add(int &x,int y) { return x=x+y>=moder?x+y-moder:x+y; }
int sub(int x,int y) { return x<y?x-y+moder:x-y; } int Sub(int &x,int y) { return x=x<y?x-y+moder:x-y; }
int kuai(int a,int b) { ull rey=1,temp=a; for(;b;b>>=1) { if(b&1) rey=rey*temp%moder; temp=temp*temp%moder; } return rey; }
struct note { int a,b,c; note(int _a=0,int _b=0,int _c=0){a=_a,b=_b,c=_c;} };
int TID,T,n; map<string,note> id; int a[23]={},fact[N]={},finv[N]={},pow2[N]={},pre[N]={}; string s[23];
int Choose(int n,int m) { return n<m||n<0||m<0?0:(ull)fact[n]*finv[m]%moder*finv[n-m]%moder; }
void init() {
	id["LL_RR"]=id["LRL_R"]=id["L_RLR"]=note(0,1,0);
	id["L_LRR"]=note(0,0,1),id["LLR_R"]=note(0,0,-1);
	id["_LLRR"]=id["LLRR_"]=id["LRLR_"]=id["LR_LR"]=id["_LRLR"]=id["R_LLR"]=id["LRR_L"]=id["R_LRL"]=id["RLR_L"]=id["RR_LL"]=0;
	id["RL_LR"]=1,id["LR_RL"]=-1;
	id["RRL_L"]=id["LRRL_"]=id["RLRL_"]=2,id["R_RLL"]=id["_RLRL"]=id["_RLLR"]=-2;
}
int main()
{
	// usefile("frogs");
	int i,c_,c__,c$,c$$,c0,cup,cdn,cex;
	int _,A,B,C,D,big,les,equ;
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	init();
	fact[0]=finv[0]=pow2[0]=1;
	for(i=1;i<N;++i) fact[i]=(ull)fact[i-1]*i%moder;
	finv[N-1]=kuai(fact[N-1],moder-2);
	for(i=N-2;i;--i) finv[i]=(ull)finv[i+1]*(i+1)%moder;
	for(i=1;i<N;++i) pow2[i]=add(pow2[i-1],pow2[i-1]);
	auto PRE=[&](int x)->int{return x<-c_?0:x>c$?pre[c_+c$]:pre[x+c_];};
	cin>>TID>>T;
	loop : --T;
	cin>>n;
	c_=c__=c$=c$$=c0=cup=cdn=cex=A=B=C=D=0;
	for(i=0;i<n;++i) {
		cin>>s[i]>>a[i];
		if(id[s[i]].c==1) cup+=a[i];
		else if(id[s[i]].c==-1) cdn+=a[i];
		else if(id[s[i]].b==1) cex+=a[i];
		else if(id[s[i]].a==-1) c_+=a[i];
		else if(id[s[i]].a==-2) c__+=a[i];
		else if(id[s[i]].a==1) c$+=a[i];
		else if(id[s[i]].a==2) c$$+=a[i];
		else if(id[s[i]].a==0) c0+=a[i];
	}
	// printf("a: %d %d %d %d %d\n",c__,c_,c0,c$,c$$);
	// printf("b: %d\n",cex);
	// printf("c: %d %d\n",cdn,cup);
	for(i=-c_;i<=c$;++i) pre[i+c_]=Choose(c_+c$,c_+i);
	for(i=1;i<=c_+c$;++i) Add(pre[i],pre[i-1]);
	big=les=equ=0;
	for(i=-c__;i<=c$$;++i) {
		_=Choose(c__+c$$,c__+i);
		Add(les,(ull)PRE(-2*i-1)*_%moder);
		Add(equ,(ull)sub(PRE(-2*i),PRE(-2*i-1))*_%moder);
	}
	big=sub(pow2[c_+c__+c$+c$$],add(les,equ));
	Add(A,(ull)pow2[cup+cdn+cex]*big%moder);
	Add(B,(ull)pow2[cup+cdn+cex]*les%moder);
	// printf("les=%d equ=%d big=%d\n",les,equ,big);
	_=pow2[max(0,cex-1)];
	for(i=-cdn;i<=cup;++i)
		if(i>0) Add(A,(ull)_*equ%moder*Choose(cdn+cup,cdn+i)%moder);
		else if(i<0) Add(B,(ull)_*equ%moder*Choose(cdn+cup,cdn+i)%moder);
		else Add(D,(ull)_*equ%moder*Choose(cdn+cup,cdn+i)%moder);
	if(cex) {
		_=pow2[cex-1];
		for(i=-cdn;i<=cup;++i)
			if(i>1) Add(A,(ull)_*equ%moder*Choose(cdn+cup,cdn+i)%moder);
			else if(i<-1) Add(B,(ull)_*equ%moder*Choose(cdn+cup,cdn+i)%moder);
			else Add(C,(ull)_*equ%moder*Choose(cdn+cup,cdn+i)%moder);
	}
	A=(ull)A*pow2[c0]%moder,B=(ull)B*pow2[c0]%moder;
	C=(ull)C*pow2[c0]%moder,D=(ull)D*pow2[c0]%moder;
	printf("%d %d %d %d\n",A,B,C,D);
	if(T) goto loop;
	return 0;
}