QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#250267 | #5097. 小 P 爱学习 | Crysfly | 0 | 113ms | 26096kb | C++17 | 2.7kb | 2023-11-13 00:46:08 | 2023-11-13 00:46:08 |
Judging History
answer
// what is matter? never mind.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define int long long
#define ull unsigned long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define mod 998244353
struct modint{
int x;
modint(int o=0){x=o;}
modint &operator = (int o){return x=o,*this;}
modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
modint &operator ^=(int b){
modint a=*this,c=1;
for(;b;b>>=1,a*=a)if(b&1)c*=a;
return x=c.x,*this;
}
modint &operator /=(modint o){return *this *=o^=mod-2;}
friend modint operator +(modint a,modint b){return a+=b;}
friend modint operator -(modint a,modint b){return a-=b;}
friend modint operator *(modint a,modint b){return a*=b;}
friend modint operator /(modint a,modint b){return a/=b;}
friend modint operator ^(modint a,int b){return a^=b;}
friend bool operator ==(modint a,int b){return a.x==b;}
friend bool operator !=(modint a,int b){return a.x!=b;}
bool operator ! () {return !x;}
modint operator - () {return x?mod-x:0;}
bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}
vector<modint> fac,ifac,iv;
inline void initC(int n)
{
if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
int m=iv.size(); ++n;
if(m>=n)return;
iv.resize(n),fac.resize(n),ifac.resize(n);
For(i,m,n-1){
iv[i]=iv[mod%i]*(mod-mod/i);
fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
}
}
inline modint C(int n,int m){
if(m<0||n<m)return 0;
return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 200005
#define inf 0x3f3f3f3f
int n,m;
modint a[maxn];
modint dp[1505];
modint f[1505][1505];
signed main()
{
n=read(),m=read();
initC(1500*100+5);
dp[0]=1;
For(i,1,n*m){
a[i]=read();
Rep(j,min(i,n),1)dp[j]+=dp[j-1]*a[i];
}
f[0][0]=1;
For(i,1,n){
For(j,1,n){
For(k,1,j)
f[i][j]+=f[i-1][j-k]*ifac[k*m-1];
}
}
modint res=0;
For(i,1,n)res+=f[i][n]*fac[n*m-i]*dp[i];
cout<<res.x;
return 0;
}
/*
5 2
1 2 1
2 3 1
3 4 1
4 5 1
*/
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 25952kb
input:
3 4 993987920 851664708 532496582 332334976 645105194 437392477 101400616 97233810 821968468 15736516 160047245 366079295
output:
813722045
result:
wrong answer expected 856280467, found 813722045
Subtask #2:
score: 0
Time Limit Exceeded
Test #6:
score: 0
Time Limit Exceeded
input:
1500 1 613884366 318223729 617843443 151365784 314748737 778479063 762692152 762329264 560579744 428619194 148701427 891734077 339222910 692588908 180829596 615884679 688697194 981930569 856072945 973079346 407508504 185723413 482150672 944412007 548582506 572572951 297202679 276708377 552007154 951...
output:
result:
Subtask #3:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 3ms
memory: 26096kb
input:
100 42 544703372 456304555 178333752 808160596 628160657 264931494 810502429 20342061 203372934 920107110 466566652 470361058 680819469 879463750 668822108 781685938 40434324 800845096 913025163 971899062 986502509 122277391 523016525 579121406 413351231 882719635 632511496 453222515 350376424 37340...
output:
2591624
result:
wrong answer expected 294362854, found 2591624
Subtask #4:
score: 0
Wrong Answer
Test #16:
score: 0
Wrong Answer
time: 113ms
memory: 26096kb
input:
499 60 136856769 47869549 264538291 600887500 271130365 503375271 979728502 928286478 295751844 413206031 143796624 712745939 41348750 488666164 725432432 529794914 703056452 573552365 225245406 620490759 715276073 987544150 759181034 939466746 354701446 228245827 301255190 24876250 452483821 837389...
output:
783509869
result:
wrong answer expected 157452172, found 783509869
Subtask #5:
score: 0
Time Limit Exceeded
Test #21:
score: 0
Time Limit Exceeded
input:
1500 93 299567650 399978478 101776752 583392666 56762099 127237968 595272440 581887945 332400603 269986805 17840600 323055242 263161884 607605816 966029729 591250421 964262680 642691696 658567473 339363823 715151825 270553684 202478735 193930303 14517687 248178770 917823665 315265457 473654173 33965...