QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#246244#2830. Data Structurenameless_story#Compile Error//C891.9kb2023-11-10 17:46:022023-11-10 17:46:02

Judging History

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

  • [2023-11-10 17:46:02]
  • 评测
  • [2023-11-10 17:46:02]
  • 提交

answer

#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
template<class T1,class T2> bool cmin(T1 &x,const T2 &y) { if (y<x) { x=y; return 1; }return 0; }
template<class T1,class T2> bool cmax(T1 &x,const T2 &y) { if (x<y) { x=y; return 1; }return 0; }
#define all(x) (x).begin(),(x).end()
const int mod=998244353;
ll power(ll a,ll p)
{
	ll ret=1;
	while (p)
	{
		if (p&1)
			ret=ret*a%mod;
		a=a*a%mod;
		p>>=1;
	}
	return ret;
}
ll inv(ll n)
{
	return power(n,mod-2);
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n,x,y,q;
	while (cin>>n>>x>>y>>q)
	{
		vector<pair<int,int>> qs(q);
		int A=1,B=1;
		for (auto &[a,b]:qs)
		{
			cin>>a>>b;
			cmax(A,a);
			cmax(B,b);
		}
		map<ll,vector<vector<ll>>> F;
		function<void(ll)> solve=[&](ll len)
			{
				if (F.find(len)!=F.end())
					return;
				vector<vector<ll>> f(A+1,vector<ll>(B+1,0ll));
				if (len==1)
				{
					f[1][0]=x;
					f[0][1]=y;
					f[0][0]=(x+y)%mod;
					F[len]=f;
					return;
				}
				solve(len>>1);
				solve(len+1>>1);
				auto &fl=F[len>>1],&fr=F[len+1>>1];
				vector<ll> C1(max(A,B)+1,0);
				C1[0]=1;
				for (int i=1; i<=max(A,B); i++)
				{
					C1[i]=C1[i-1]*((len>>1)-i+1)%mod*inv(i)%mod;
				}
				vector<ll> C2=C1;
				for (int i=1; i<=max(A,B); i++)
				{
					C2[i]=C2[i-1]*((len+1>>1)-i+1)%mod*inv(i)%mod;
				}
				for (int i=0; i<=A; i++)
				{
					for (int j=0; j<=B; j++)
					{
						for (int k=0; k<=j; k++)
						{
							(f[i][j]+=C2[j-k]*fl[i][k]%mod*power(y,len+1>>1)%mod)%=mod;
						}
					}
				}
				for (int i=0; i<=B; i++)
				{
					for (int j=0; j<=A; j++)
					{
						for (int k=0; k<=j; k++)
						{
							(f[j][i]+=C1[j-k]*fr[k][i]%mod*power(x,len>>1)%mod)%=mod;
						}
					}
				}
				F[len]=f;
				return;
			};
		solve(n);
		auto &out=F[n];
		for (auto [a,b]:qs)
		{
			cout<<out[a][b]*inv(power(x,a))%mod*inv(power(y,b))%mod*inv(2)%mod<<'\n';
		}
	}
}

Details

answer.code:1:9: fatal error: bits/stdc++.h: No such file or directory
    1 | #include"bits/stdc++.h"
      |         ^~~~~~~~~~~~~~~
compilation terminated.