QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#55372 | #4807. Melborp Lacissalc | GZU_addd | WA | 7ms | 20340kb | C++ | 2.2kb | 2022-10-13 14:08:52 | 2022-10-13 14:08:54 |
Judging History
answer
#include<bits/stdc++.h>
#define ls u<<1
#define rs u<<1|1
#define fi first
#define se second
#define min amin
#define max amax
#define pb push_back
#define pq priority_queue
#define vt vector
#define lb(x) (x&-x)
#define sub(i,j) ((1LL*i-1LL*j)%k+k)%k
std::mt19937 rnd(233);
using namespace std;
using ll=long long;
//using node=pair<int,int>;
//using nnode=array<int,3>;
//inline int read(){
// int x=0,f=1;
// char c=getchar();
// while(c<'0'||c>'9'){
// if(c=='-') f=-1;
// c=getchar();
// }
// while(c>='0'&&c<='9'){
// x=x*10+(c^'0');
// c=getchar();
// }
// return x*f;
//}
template<typename T=int>T read(){T x;cin>>x;return x;}
template<typename U,typename V>auto min(U x,V y){return x<y?x:y;}
template<typename U,typename V>auto max(U x,V y){return x>y?x:y;}
template<typename U,typename...V>auto min(U x,V...y){return min(x,min(y...));}
template<typename U,typename...V>auto max(U x,V...y){return max(x,max(y...));}
template<typename U,typename V>bool cmin(U &x,V y){return x>y?x=y,true:false;}
template<typename U,typename V>bool cmax(U &x,V y){return x<y?x=y,true:false;}
constexpr int mod=998244353;
ll qpow(int x,int n=mod-2){ll y=1;for(;n;n>>=1,x=1LL*x*x%mod)if(n&1)y=1LL*y*x%mod;return y;}
//inline ll qpow(ll a, ll n=mod-2) { ll ans = 1; while (n) { if (n & 1) { ans *= a; }a *= a; n >>= 1; }return ans; }
constexpr int N=65,M=N*(N+1)/2;
constexpr ll inf=1e18;
int n,m,k,fac[N],infac[N],f[N][N][M];
int C(int x,int y){if(x<y)return 0;return 1LL*fac[x]*infac[y]%mod*infac[x-y]%mod;}
void solve(){
cin>>n>>k>>m;
f[0][0][0]=fac[0]=1;
for(int i=1;i<=n;++i)fac[i]=1LL*fac[i-1]*i%mod;
infac[n]=qpow(fac[n]);
for(int i=n-1;~i;--i)infac[i]=1LL*infac[i+1]*(i+1)%mod;
for(int i=1;i<=k;++i){
for(int j=1;j<=n;++j){
for(int l=1;l<=j;++l){
int del;
if(i==1)del=C(l+1,2);
else del=C(l,2);
for(int p=del;p<=m;++p)
f[i][j][p]=(f[i][j][p]+1LL*f[i-1][j-l][p-del]*C(j,l)%mod)%mod;
}
}
for(int j=0;j<=n;++j)for(int p=0;p<=m;++p)
f[i][j][p]=(f[i][j][p]+f[i-1][j][p])%mod;
}
if(m==0)cout<<f[k][n][m]-1;
else cout<<f[k][n][m];
}
int main(){
cin.sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
// for(int T=read();T--;solve());
solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3812kb
input:
2 5 1
output:
12
result:
ok 1 number(s): "12"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3884kb
input:
7 10 15
output:
2016
result:
ok 1 number(s): "2016"
Test #3:
score: 0
Accepted
time: 7ms
memory: 14552kb
input:
46 50 171
output:
645560469
result:
ok 1 number(s): "645560469"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 20340kb
input:
64 64 0
output:
-1
result:
wrong answer 1st numbers differ - expected: '0', found: '-1'