QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#313732 | #8171. Cola | ucup-team266# | WA | 166ms | 316432kb | C++23 | 1.6kb | 2024-01-24 22:40:54 | 2024-01-24 22:40:54 |
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;
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;
if(n==2&&m==2) die("1");
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: 145ms
memory: 316028kb
input:
2 1
output:
499122177
result:
ok "499122177"
Test #2:
score: 0
Accepted
time: 154ms
memory: 316300kb
input:
1 1
output:
1
result:
ok "1"
Test #3:
score: 0
Accepted
time: 157ms
memory: 316104kb
input:
167 91
output:
469117530
result:
ok "469117530"
Test #4:
score: 0
Accepted
time: 157ms
memory: 316152kb
input:
9806463 8975779
output:
125384417
result:
ok "125384417"
Test #5:
score: 0
Accepted
time: 156ms
memory: 316432kb
input:
9138576 8731432
output:
306972756
result:
ok "306972756"
Test #6:
score: -100
Wrong Answer
time: 166ms
memory: 316240kb
input:
9978791 9033584
output:
102461481
result:
wrong answer 1st words differ - expected: '932159263', found: '102461481'