QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#818090#5097. 小 P 爱学习nullptr_qwq0 59ms7332kbC++142.6kb2024-12-17 16:20:222024-12-17 16:20:29

Judging History

This is the latest submission verdict.

  • [2024-12-17 16:20:29]
  • Judged
  • Verdict: 0
  • Time: 59ms
  • Memory: 7332kb
  • [2024-12-17 16:20:22]
  • Submitted

answer

// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=150005;
inline int qpow(int x,ll y){ int res=1; for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)res=1ll*res*x%mod; return res; }
inline void inc(int &x,const int y){ x=(x+y>=mod)?(x+y-mod):(x+y); }
inline void dec(int &x,const int y){ x=(x>=y)?(x-y):(x+mod-y); }
inline void mul(int &x,const int y){ x=1ll*x*y%mod; }
inline int add(const int x,const int y){ return (x+y>=mod)?(x+y-mod):(x+y); }
inline int sub(const int x,const int y){ return (x>=y)?(x-y):(x+mod-y); }
inline int prod(const int x,const int y){ return 1ll*x*y%mod; }
mt19937 eng(std::chrono::steady_clock::now().time_since_epoch().count());
inline int rd(const int l,const int r) { return std::uniform_int_distribution<int>(l,r)(eng); }
namespace combi{
	int fac[maxn],ifac[maxn],inv[maxn];
	void init(const int N){
		fac[0]=ifac[0]=inv[0]=1;
		F(i,1,N)fac[i]=1ll*fac[i-1]*i%mod;
		ifac[N]=qpow(fac[N],mod-2);
		dF(i,N-1,1)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
		F(i,1,N)inv[i]=1ll*ifac[i]*fac[i-1]%mod;
	}
	inline int C(const int n,const int m){
		if(m>n||n<0||m<0) return 0;
		return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
	}
}
using namespace combi;
const int NR=505;
int n,m,coef[NR],f[NR][NR],g[NR][NR],dp[NR];
void solve(){
	cin>>n>>m,f[0][0]=g[0][0]=coef[0]=1,init(maxn-3);
	F(_,1,n*m){
		int x; cin>>x;
		dF(i,n-1,0)inc(coef[i+1],1ll*coef[i]*x%mod);
	} const int B=sqrt(n);
	F(i,1,n)F(j,i,n)F(k,1,min(j,B))inc(f[i][j],1ll*f[i-1][j-k]*ifac[k*m-1]%mod);
	F(i,1,n/B)F(j,i,n)F(k,B+1,j)inc(g[i][j],1ll*g[i-1][j-k]*ifac[k*m-1]%mod);
	int ans=0;
	F(k,1,n){
		int res=0;
		F(i,0,min(k,B))F(j,0,n)inc(res,1ll*f[k-i][n-j]*g[i][j]%mod*C(k,i)%mod);
		inc(ans,1ll*res*fac[n*m-k]%mod*coef[k]%mod);
	} cout<<ans;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int zsy=1;
	F(____,1,zsy)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 7272kb

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
Runtime Error

Test #6:

score: 0
Runtime Error

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: 2ms
memory: 6404kb

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: 59ms
memory: 7332kb

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
Runtime Error

Test #21:

score: 0
Runtime Error

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...

output:


result: