C++14(g++5.4) 解法, 执行用时: 205ms, 内存消耗: 612K, 提交时间: 2019-07-30 19:43:41

#include <bits/stdc++.h>
using namespace std;
const int N=10005;
const int MD=998244353;
int f[2][N];
void add(int &x,int y)
{
	x+=y;
	if(x>MD) x-=MD;
}
int main()
{
	int m,q,x,s=1,cnt=0;
	scanf("%d",&m);
	f[0][0]=1;
	for(int i=0,a,b;i<m;i++)
	{
		scanf("%d%d",&a,&b);
		for(int j=0;j<s+2;j++) f[cnt^1][j]=0;
		for(int j=0;j<s;j++)
		{
			add(f[cnt^1][j+2],(1LL*f[cnt][j]*(a-b+1)%MD+MD)%MD);
			add(f[cnt^1][j+1],(1LL*f[cnt][j]*(a+b-2)%MD+MD)%MD);
			add(f[cnt^1][j],f[cnt][j]);
		}
		s+=2;
		cnt^=1;
	}
	int t=3*m;
	while(t--)
	{
		for(int j=1;j<=10000;j++)
			add(f[cnt][j],f[cnt][j-1]);
	}
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d",&x);
		printf("%d\n",f[cnt][x]);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 175ms, 内存消耗: 612K, 提交时间: 2019-10-08 10:51:39

#include<cstdio>
using namespace std;
const long long mod=998244353;
int m,a,b,q,x;
long long f[10005];
int main()
{
	scanf("%d",&m);
	f[0]=1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		long long A=(0LL+a-b+1+mod)%mod,B=(0LL+a+b-2+mod)%mod;
		for(int i=10000;i>=2;i--)
			f[i]=(f[i]+f[i-1]*B+f[i-2]*A)%mod;
		f[1]=(f[1]+f[0]*B)%mod;
		for(int k=1;k<=3;k++)
		for(int i=1;i<=10000;i++)
			f[i]=(f[i]+f[i-1])%mod; 
	}
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d",&x);
		printf("%lld\n",f[x]);
	}
}