QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#767480 | #9254. Random Variables | AllenJYL | TL | 584ms | 34616kb | C++14 | 2.7kb | 2024-11-20 21:04:26 | 2024-11-20 21:04:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define all(_array) (_array).begin(),(_array).end()
#define msp(_array) memset(_array,0x3f,sizeof _array)
#define ms0(_array) memset(_array,0,sizeof _array)
#define msn(_array) memset(_array,-1,sizeof _array)
#define mc(_tar,_array) memcpy(_tar,_array,sizeof _tar)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define TAK cout<<"TAK"<<endl
#define NIE cout<<"NIE"<<endl
#define OK cerr<<"OK"<<endl
#define pii pair<int,int>
#define endl '\n'
bool bg_memory;
mt19937 rnd(time(0));
int Case=1;
int mod=1e9+7;
const int inf=2147483647;
const int bs=233;
const double eps=1e-6;
const int N=1e3+7,M=1e5+7;
template<class _t1,class _t2>inline void cmax(_t1 &a,_t2 b){a=a<b?b:a;}
template<class _t1,class _t2>inline void cmin(_t1 &a,_t2 b){a=a>b?b:a;}
inline int qp(int a,int b,int p=mod){int res=1;while(b){if(b&1)res=1ll*res*a%p;a=1ll*a*a%p;b>>=1;}return res;}
inline int sqrt(int x,int r){int l=0,ans=0;while(l<=r){if(1ll*mid*mid<=x) ans=mid,l=mid+1;else r=mid-1;}return ans;}
int n,bm;
int ans;
int tmp;
int dp[N][N],vis[N][N],c[N][N];
vector<pii> ap;
inline int getdp(int n,int m,int k){
if(vis[n][bm-m]) return dp[n][bm-m];
vis[n][bm-m]=1;
ap.push_back({n,bm-m});
if(n==0) return dp[n][bm-m]=1;
dp[n][bm-m]=m*getdp(n-1,m,k)%mod;
if(n-k>0) (dp[n][bm-m]+=mod-m*c[n-1][k]%mod*getdp(n-k-1,m-1,k)%mod)%=mod;
return dp[n][bm-m];
}
void Main(){
cin>>n>>bm;
tmp=qp(bm,n);
ans=0;
for(int k=0;k<n;k++){
(ans+=tmp-getdp(n,bm,k)+mod)%=mod;
for(pii j:ap) vis[j.first][j.second]=0;
ap.clear();
// cout<<ans<<endl;
}
cout<<ans<<endl;
return;
}
string RdFile="";
bool en_memory;
signed main(){
auto bg_clock=chrono::high_resolution_clock::now();
#ifdef ONLINE_JUDGE
// freopen((RdFile+".in").c_str(),"r",stdin);
// freopen((RdFile+".out").c_str(),"w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>Case>>mod;
c[0][0]=1;
for(int i=1;i<=1000;i++){
c[i][0]=1;
for(int j=1;j<=i;j++){
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
}
while(Case--) Main();
auto en_clock=chrono::high_resolution_clock::now();
auto duration_clock=chrono::duration_cast<chrono::microseconds>(en_clock-bg_clock);
double duration_count=duration_clock.count()*0.001;
double memory_used=(&en_memory-&bg_memory)/1024.0/1024;
// cerr<<"Time:"<<duration_count<<"ms"<<endl;
// cerr<<"Memory: "<<memory_used<<"MB"<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 14608kb
input:
3 123456789 3 2 5 5 7 7
output:
18 7145 2066323
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 13316kb
input:
100 2 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
result:
ok 100 lines
Test #3:
score: 0
Accepted
time: 4ms
memory: 14508kb
input:
100 3 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 0 1 2 0 1 2 0 1 2 0 0 2 0 0 2 0 0 2 0 0 0 0 0 0 0 0 0 0 1 2 0 1 2 0 1 2 0 1 2 2 0 2 2 0 2 2 0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 2 2 0 2 2 0 2 2 0 2 0 0 0 0 0 0 0 0 0 0 1 2 0 1 2 0 1 2 0 1
result:
ok 100 lines
Test #4:
score: 0
Accepted
time: 3ms
memory: 14708kb
input:
100 4 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 3 0 1 2 3 0 1 2 2 2 0 0 2 2 0 0 2 2 3 2 3 0 3 2 3 0 3 2 0 0 0 0 0 0 0 0 0 0 1 2 3 0 1 2 3 0 1 2 2 0 2 0 2 0 2 0 2 0 3 0 3 0 3 0 3 0 3 0 0 0 0 0 0 0 0 0 0 0 1 2 3 0 1 2 3 0 1 2 2 0 2 0 2 0 2 0 2 0
result:
ok 100 lines
Test #5:
score: 0
Accepted
time: 3ms
memory: 14340kb
input:
100 5 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 3 4 0 1 2 3 4 0 2 1 2 0 0 2 1 2 0 0 3 3 1 3 0 3 3 1 3 0 4 4 2 4 0 4 4 2 4 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 0 1 2 3 4 0 2 3 3 2 0 2 3 3 2 0 3 4 1 2 0 3 4 1 2 0 4 4 4 4 0 4 4 4 4 0 0 0 0 0 0 0 0 0 0 0
result:
ok 100 lines
Test #6:
score: 0
Accepted
time: 3ms
memory: 13160kb
input:
100 6 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 3 4 5 0 1 2 3 4 2 0 0 2 0 0 2 0 0 2 3 0 3 0 3 0 3 0 3 0 4 2 0 4 2 0 4 2 0 4 5 2 3 2 5 0 5 2 3 2 0 0 0 0 0 0 0 0 0 0 1 0 3 4 3 0 1 0 3 4 2 2 0 2 2 0 2 2 0 2 3 0 3 0 3 0 3 0 3 0 4 2 0 4 2 0 4 2 0 4
result:
ok 100 lines
Test #7:
score: 0
Accepted
time: 0ms
memory: 14684kb
input:
100 7 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 3 4 5 6 0 1 2 3 2 6 5 6 2 0 0 2 6 5 3 4 2 3 6 3 0 3 4 2 4 2 3 5 2 5 0 4 2 3 5 5 3 6 5 4 0 5 5 3 6 0 6 1 1 6 0 6 0 6 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 0 1 2 3 2 1 4 4 1 2 0 2 1 4 3 3 4 3 4 4 0 3 3 4
result:
ok 100 lines
Test #8:
score: 0
Accepted
time: 3ms
memory: 14012kb
input:
100 8 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 3 4 5 6 7 0 1 2 2 6 4 4 6 2 0 0 2 6 3 2 3 4 3 6 3 0 3 2 4 4 0 0 4 4 0 0 4 4 5 6 3 4 1 2 7 0 5 6 6 4 6 0 6 4 6 0 6 4 7 4 3 0 7 4 3 0 7 4 0 0 0 0 0 0 0 0 0 0 1 6 3 4 5 2 7 0 1 6 2 4 6 0 2 4 6 0 2 4
result:
ok 100 lines
Test #9:
score: 0
Accepted
time: 4ms
memory: 14880kb
input:
100 9 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 2...
output:
1 2 3 4 5 6 7 8 0 1 2 6 3 2 3 6 2 0 0 2 3 0 6 0 6 3 6 3 0 3 4 8 3 4 5 6 4 2 0 4 5 2 0 2 8 0 8 5 0 5 6 0 0 6 0 0 6 0 0 6 7 3 6 1 3 3 4 3 0 7 8 8 6 5 8 3 2 8 0 8 0 0 0 0 0 0 0 0 0 0 1 8 3 4 2 6 7 5 0 1
result:
ok 100 lines
Test #10:
score: 0
Accepted
time: 3ms
memory: 14024kb
input:
100 10 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 ...
output:
1 2 3 4 5 6 7 8 9 0 2 6 2 0 0 2 6 2 0 0 3 8 1 8 5 8 3 6 3 0 4 4 2 4 0 4 4 2 4 0 5 0 5 0 5 0 5 0 5 0 6 2 8 4 0 6 2 8 4 0 7 8 3 2 5 2 3 8 7 0 8 4 6 2 0 8 4 6 2 0 9 4 9 4 5 4 9 4 9 0 0 0 0 0 0 0 0 0 0 0
result:
ok 100 lines
Test #11:
score: 0
Accepted
time: 0ms
memory: 14280kb
input:
100 11 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 8 1 8 ...
output:
1 2 3 4 5 6 7 8 9 10 2 6 1 9 8 9 1 6 2 0 3 7 7 9 8 10 10 3 6 3 4 0 5 5 10 10 8 9 9 6 5 0 4 10 6 7 10 4 2 7 6 10 4 5 3 2 0 7 2 5 7 5 2 8 6 1 6 0 3 6 8 6 6 3 2 4 8 3 6 9 9 8 10 2 8 6 10 9 3 1 10 0 4 3 0 6 0 7 4 9
result:
ok 100 lines
Test #12:
score: 0
Accepted
time: 368ms
memory: 33884kb
input:
10 972033073 576 523187654 758 588616188 30 532959085 476 481773028 573 76725430 520 142462406 865 820120297 687 526533288 913 38106557 67 924529654
output:
259748390 909910217 708973357 300073565 463921261 889897372 587262932 255642402 868975954 14589849
result:
ok 10 lines
Test #13:
score: 0
Accepted
time: 483ms
memory: 33832kb
input:
10 922366485 846 278501607 683 609355362 44 978777279 545 730718412 926 323835432 883 761846029 623 408215612 989 588832935 449 743830620 259 183431187
output:
461786112 672633342 164805246 547995105 9661617 154501063 370848893 402005970 886523490 435107511
result:
ok 10 lines
Test #14:
score: 0
Accepted
time: 468ms
memory: 33540kb
input:
10 13890975 949 837425969 667 981449995 991 564074312 501 604745038 593 640307170 128 408163542 80 976891742 930 710947599 852 333118419 250 333252788
output:
3898759 9290500 7087084 4913904 196250 1746549 9627740 8673120 10274253 10549775
result:
ok 10 lines
Test #15:
score: 0
Accepted
time: 235ms
memory: 33892kb
input:
10 105576445 649 937885257 141 713063090 253 716966251 845 330657011 347 664392407 810 50478969 389 530582574 228 199722046 85 256258366 605 3721959
output:
22721419 27962190 85541228 53950260 35288938 100176945 86409840 102331663 55591445 14790745
result:
ok 10 lines
Test #16:
score: 0
Accepted
time: 310ms
memory: 33816kb
input:
10 445185474 268 687201814 929 296077349 690 202741564 372 661889855 442 989604795 367 456833096 702 862601129 795 37538865 556 131444040 108 645857776
output:
39577672 390323147 423333756 49417686 12978114 278291170 60346062 410583855 68429394 296833176
result:
ok 10 lines
Test #17:
score: 0
Accepted
time: 449ms
memory: 32796kb
input:
10 265384486 870 503808438 959 733458117 126 226376632 979 205878607 747 270352323 339 384431347 373 659485098 597 832514575 832 906898547 12 869891031
output:
54820154 83262107 48675762 32938269 169458409 153632065 105152812 48645927 29870948 83831862
result:
ok 10 lines
Test #18:
score: 0
Accepted
time: 314ms
memory: 34616kb
input:
10 869896294 256 326197921 496 115501273 861 238744067 581 600444623 619 536213251 89 898877607 136 353575223 860 349472278 491 770026371 668 622723560
output:
678111040 344947200 90686837 157367547 295943299 25262829 81930384 532341712 23048077 475131428
result:
ok 10 lines
Test #19:
score: 0
Accepted
time: 584ms
memory: 34552kb
input:
10 692092859 831 647975618 792 737778459 392 768554014 854 612888229 31 148093584 793 559010229 970 237393805 339 914914862 831 979073722 988 738224088
output:
324659472 16793498 421391172 416475848 59704753 347151224 415078841 680610884 397373492 296521551
result:
ok 10 lines
Test #20:
score: 0
Accepted
time: 255ms
memory: 33372kb
input:
10 827165684 577 720722656 383 778750361 951 59165685 502 993162103 589 166261195 500 816688874 40 625075150 331 160531509 394 578798823 181 710984062
output:
736529364 199088527 528654835 586634074 442300715 383600380 707706396 763397655 534310310 338272096
result:
ok 10 lines
Test #21:
score: 0
Accepted
time: 261ms
memory: 33884kb
input:
10 691312083 185 445519030 93 44970277 951 662144708 252 766000017 83 911805458 424 816227326 770 136026896 354 763387805 247 458147285 747 14566368
output:
411209183 132362175 110569626 664410537 241484162 480388660 264805387 294178848 147876955 371900799
result:
ok 10 lines
Test #22:
score: -100
Time Limit Exceeded
input:
10 691312083 1000 445519030 1000 44970277 1000 662144708 1000 766000017 1000 911805458 1000 816227326 1000 136026896 1000 763387805 1000 458147285 747 14566368
output:
365043118 14826361 571573673 63977538 484010015 499398766 433242788 43269113 412491407 371900799