QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#555216 | #9254. Random Variables | Hanghang | TL | 153ms | 19236kb | C++20 | 710b | 2024-09-09 20:46:17 | 2024-09-09 20:46:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1003;
ll H,n,m,f[N][N],C[N][N];
void Solve()
{
cin>>n>>m;ll res=1,ans=0;
for(int i=1;i<=n;i++)res=res*m%H,ans=res;
for(int k=1;k<=n;k++)
{
ll lim=n/k;memset(f,0,sizeof(f));
for(int i=0;i<=lim;i++)f[0][i]=1;
for(int i=0;i<=n;i++)f[i][lim+1]=0;
for(int i=1;i<=n;i++)for(int j=0;j<=min(lim,m);j++)
{
f[i][j]=f[i-1][j]*(m-j)%H;
if(i>k)f[i][j]=(f[i][j]-f[i-k-1][j+1]*C[i-1][k]%H*(m-j)%H+H)%H;
}
ans=(ans+res-f[n][0]+H)%H;
}
cout<<ans<<endl;
}
int main()
{
int T;cin>>T>>H;
for(int i=0;i<N;i++)for(int j=C[i][0]=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%H;
while(T--)Solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 18640kb
input:
3 123456789 3 2 5 5 7 7
output:
18 7145 2066323
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 150ms
memory: 18764kb
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: 153ms
memory: 19000kb
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: 144ms
memory: 18860kb
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: 150ms
memory: 18768kb
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: 149ms
memory: 18644kb
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: 145ms
memory: 18700kb
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: 152ms
memory: 19236kb
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: 149ms
memory: 18656kb
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: 145ms
memory: 18772kb
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: 144ms
memory: 19072kb
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: -100
Time Limit Exceeded
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