QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#313726#8171. Colaucup-team266#WA 167ms316444kbC++232.2kb2024-01-24 22:36:082024-01-24 22:36:09

Judging History

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

  • [2024-01-24 22:36:09]
  • 评测
  • 测评结果:WA
  • 用时:167ms
  • 内存:316444kb
  • [2024-01-24 22:36:08]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const ll mod=998244353;
ll fact[20001000],rfact[20001000];
ll ksm(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
ll C(int n,int k)
{
	if(k<0||n<k) return 0;
	return fact[n]*rfact[k]%mod*rfact[n-k]%mod;
}
int n,m;
vector<pair<int,ll>> calc(int l,int r)
{
	if(l>r)
	{
		vector<pair<int,ll>> ret;
		ret.pb(0,1);
		return ret;
	}
	if(l==r)
	{
		vector<pair<int,ll>> ret;
		ret.pb(0,1);
		ret.pb(l,mod-1);
		return ret;
	}
	int mid=(l+r)/2;
	vector<pair<int,ll>> v1=calc(l,mid),v2=calc(mid+1,r);
	vector<pair<int,ll>> ans;
	for(int i=0;i<sz(v1);i++)
		for(int j=0;j<sz(v2);j++)
			if(v1[i].first+v2[j].first<=m)
				ans.pb(v1[i].first+v2[j].first,v1[i].second*v2[j].second%mod);
	srt(ans);
	vector<pair<int,ll>> ret;
	for(auto pr:ans)
		if(!sz(ret)||ret.back().first!=pr.first)
			ret.pb(pr);
		else
			ret[sz(ret)-1].second=(ret[sz(ret)-1].second+pr.second)%mod;
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	fact[0]=1;
	for(int i=1;i<20001000;i++)
		fact[i]=fact[i-1]*i%mod;
	rfact[20000999]=ksm(fact[20000999],mod-2);
	for(int i=20000999;i;i--)
		rfact[i-1]=rfact[i]*i%mod;
	cin>>n>>m;
	m--;
	vector<pair<int,ll>> vec;
	for(int i=0;(3*i*i+i)/2<=m;i++)
		if(i%2)
		{
			vec.pb((3*i*i-i)/2,mod-1);
			vec.pb((3*i*i+i)/2,mod-1);
		}
		else
		{
			if(i)
				vec.pb((3*i*i-i)/2,1);
			vec.pb((3*i*i+i)/2,1);
		}
	ll ans=0;
	for(auto pr:vec)
		ans=(ans+pr.second*C(n+m-pr.first,n))%mod;
	cout<<ans*rfact[n]%mod<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 140ms
memory: 316308kb

input:

2 1

output:

499122177

result:

ok "499122177"

Test #2:

score: 0
Accepted
time: 146ms
memory: 316056kb

input:

1 1

output:

1

result:

ok "1"

Test #3:

score: 0
Accepted
time: 145ms
memory: 315984kb

input:

167 91

output:

469117530

result:

ok "469117530"

Test #4:

score: 0
Accepted
time: 141ms
memory: 316436kb

input:

9806463 8975779

output:

125384417

result:

ok "125384417"

Test #5:

score: 0
Accepted
time: 167ms
memory: 316444kb

input:

9138576 8731432

output:

306972756

result:

ok "306972756"

Test #6:

score: -100
Wrong Answer
time: 151ms
memory: 316176kb

input:

9978791 9033584

output:

102461481

result:

wrong answer 1st words differ - expected: '932159263', found: '102461481'