QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#388312 | #5097. 小 P 爱学习 | zwh2008 | 0 | 0ms | 0kb | C++14 | 1.3kb | 2024-04-13 14:41:39 | 2024-04-13 14:41:40 |
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1505,M=105,mod=1e9+7;
int n,m,a[N*M];
ll ans,f[N][N],F[N],g[N],fc[N*M],inv[N*M];
ll qp(ll a,int b){ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
void init(int n) {
fc[0]=1;for(int i=1;i<=n;i++)fc[i]=fc[i-1]*i%mod;
inv[n]=qp(fc[n],mod-2);for(int i=n-1;~i;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
int main() {
freopen("study.in","r",stdin);
freopen("study.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m,F[0]=f[0][0]=1,init(n*m);
for(int i=1;i<=n*m;i++)cin>>a[i];
const int T=8;
for(int i=1;i<=n;i++)g[i]=inv[i*m-1];
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) {
__int128 F=0;
for(int k=1;k<=j;k++)F+=f[i-1][j-k]*g[k];
f[i][j]=F%mod;
}
for(int i=1;i<=n*m;i++) {
const int v=a[i];
for(int j=n;j>=T;j-=T) {
F[j]=(F[j-1]*v+F[j])%mod;
F[j-1]=(F[j-2]*v+F[j-1])%mod;
F[j-2]=(F[j-3]*v+F[j-2])%mod;
F[j-3]=(F[j-4]*v+F[j-3])%mod;
F[j-4]=(F[j-5]*v+F[j-4])%mod;
F[j-5]=(F[j-6]*v+F[j-5])%mod;
F[j-6]=(F[j-7]*v+F[j-6])%mod;
F[j-7]=(F[j-8]*v+F[j-7])%mod;
}
for(int j=n%T;j;j--)F[j]=(F[j-1]*v+F[j])%mod;
}
for(int i=1;i<=n;i++)ans=(ans+F[i]*f[i][n]%mod*fc[n*m-i])%mod;
cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
3 4 993987920 851664708 532496582 332334976 645105194 437392477 101400616 97233810 821968468 15736516 160047245 366079295
output:
result:
Subtask #2:
score: 0
Dangerous Syscalls
Test #6:
score: 0
Dangerous Syscalls
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
Dangerous Syscalls
Test #11:
score: 0
Dangerous Syscalls
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:
result:
Subtask #4:
score: 0
Dangerous Syscalls
Test #16:
score: 0
Dangerous Syscalls
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:
result:
Subtask #5:
score: 0
Dangerous Syscalls
Test #21:
score: 0
Dangerous Syscalls
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...