QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#313726 | #8171. Cola | ucup-team266# | WA | 167ms | 316444kb | C++23 | 2.2kb | 2024-01-24 22:36:08 | 2024-01-24 22:36:09 |
Judging History
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'