QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19583#2115. Od deski do deski [A]CharlieVinnie10 ✓108ms144544kbC++141003b2022-02-06 10:29:452022-05-06 06:11:10

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 06:11:10]
  • 评测
  • 测评结果：10
  • 用时：108ms
  • 内存：144544kb
查看
  • [2022-02-06 10:29:45]
  • 提交

answer

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,v) memset(a,v,sizeof(a))
#define Fin(file) freopen(file".in","r",stdin)
#define Fout(file) freopen(file".out","w",stdout)
#define Fgen(file) freopen(file".in","w",stdout)
#define Fans(file) freopen(file".ans","w",stdout)
#define int long long
using namespace std;

const int N=3e3+5,mod=1e9+7;

int n,m,f[N][N][2];

void ckadd(int& x,int y)
{
    x+=y;
    if(x>=mod) x-=mod;
}

signed main()
{
    cin>>n>>m;
    
    f[0][0][1]=1;
    
    For(i,0,n-1){
        For(j,0,n){
            ckadd(f[i+1][j][0],f[i][j][0]*(m-j)%mod);
            ckadd(f[i+1][j][1],f[i][j][0]*j%mod);
            ckadd(f[i+1][j+1][0],f[i][j][1]*(m-j)%mod);
            ckadd(f[i+1][j][1],f[i][j][1]*j%mod);
        }
    }
    
    int ans=0;
    For(j,0,n) ckadd(ans,f[n][j][1]);
    cout<<ans<<endl;

    cerr<<"Time = "<<clock()<<" ms"<<endl;
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 3ms
memory: 3560kb

input:

4 2

output:

10

result:

ok single line: '10'

Test #2:

score: 0
Accepted
time: 0ms
memory: 5644kb

input:

1 1

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 3ms
memory: 3568kb

input:

1 3

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

1 5

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

2 2

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 3ms
memory: 3692kb

input:

2 4

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 3ms
memory: 3596kb

input:

3 1

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 0ms
memory: 5508kb

input:

3 3

output:

9

result:

ok single line: '9'

Test #9:

score: 0
Accepted
time: 3ms
memory: 3612kb

input:

3 5

output:

25

result:

ok single line: '25'

Test #10:

score: 0
Accepted
time: 4ms
memory: 5512kb

input:

4 2

output:

10

result:

ok single line: '10'

Test #11:

score: 0
Accepted
time: 3ms
memory: 3540kb

input:

4 4

output:

76

result:

ok single line: '76'

Test #12:

score: 0
Accepted
time: 3ms
memory: 3588kb

input:

5 1

output:

1

result:

ok single line: '1'

Test #13:

score: 0
Accepted
time: 3ms
memory: 3592kb

input:

5 3

output:

117

result:

ok single line: '117'

Test #14:

score: 0
Accepted
time: 3ms
memory: 3612kb

input:

5 5

output:

825

result:

ok single line: '825'

Test #15:

score: 0
Accepted
time: 3ms
memory: 3676kb

input:

7 2

output:

116

result:

ok single line: '116'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

9 2

output:

496

result:

ok single line: '496'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

11 2

output:

2028

result:

ok single line: '2028'

Test #18:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

13 2

output:

8168

result:

ok single line: '8168'

Test #19:

score: 0
Accepted
time: 3ms
memory: 3640kb

input:

10 3

output:

48237

result:

ok single line: '48237'

Subtask #2:

score: 1
Accepted

Test #20:

score: 1
Accepted
time: 3ms
memory: 3652kb

input:

1 2

output:

0

result:

ok single line: '0'

Test #21:

score: 0
Accepted
time: 3ms
memory: 3576kb

input:

1 4

output:

0

result:

ok single line: '0'

Test #22:

score: 0
Accepted
time: 3ms
memory: 5616kb

input:

2 1

output:

1

result:

ok single line: '1'

Test #23:

score: 0
Accepted
time: 3ms
memory: 3460kb

input:

2 3

output:

3

result:

ok single line: '3'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

2 5

output:

5

result:

ok single line: '5'

Test #25:

score: 0
Accepted
time: 2ms
memory: 3552kb

input:

3 2

output:

4

result:

ok single line: '4'

Test #26:

score: 0
Accepted
time: 2ms
memory: 3556kb

input:

3 4

output:

16

result:

ok single line: '16'

Test #27:

score: 0
Accepted
time: 3ms
memory: 3608kb

input:

4 1

output:

1

result:

ok single line: '1'

Test #28:

score: 0
Accepted
time: 3ms
memory: 3584kb

input:

4 3

output:

33

result:

ok single line: '33'

Test #29:

score: 0
Accepted
time: 1ms
memory: 5724kb

input:

4 5

output:

145

result:

ok single line: '145'

Test #30:

score: 0
Accepted
time: 3ms
memory: 3660kb

input:

5 2

output:

24

result:

ok single line: '24'

Test #31:

score: 0
Accepted
time: 3ms
memory: 3560kb

input:

5 4

output:

352

result:

ok single line: '352'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

6 2

output:

54

result:

ok single line: '54'

Test #33:

score: 0
Accepted
time: 4ms
memory: 5644kb

input:

8 2

output:

242

result:

ok single line: '242'

Test #34:

score: 0
Accepted
time: 1ms
memory: 5724kb

input:

10 2

output:

1006

result:

ok single line: '1006'

Test #35:

score: 0
Accepted
time: 4ms
memory: 3736kb

input:

12 2

output:

4074

result:

ok single line: '4074'

Test #36:

score: 0
Accepted
time: 4ms
memory: 5824kb

input:

14 2

output:

16358

result:

ok single line: '16358'

Subtask #3:

score: 1
Accepted

Test #37:

score: 1
Accepted
time: 30ms
memory: 57096kb

input:

1689 2

output:

998472085

result:

ok single line: '998472085'

Test #38:

score: 0
Accepted
time: 64ms
memory: 132708kb

input:

2748 2

output:

451726470

result:

ok single line: '451726470'

Test #39:

score: 0
Accepted
time: 8ms
memory: 34208kb

input:

1204 2

output:

449822862

result:

ok single line: '449822862'

Test #40:

score: 0
Accepted
time: 65ms
memory: 130788kb

input:

2727 2

output:

203224669

result:

ok single line: '203224669'

Test #41:

score: 0
Accepted
time: 11ms
memory: 26340kb

input:

984 2

output:

175698237

result:

ok single line: '175698237'

Test #42:

score: 0
Accepted
time: 93ms
memory: 144316kb

input:

3000 2

output:

165694478

result:

ok single line: '165694478'

Subtask #4:

score: 1
Accepted

Test #43:

score: 1
Accepted
time: 2ms
memory: 9700kb

input:

97 83

output:

613159502

result:

ok single line: '613159502'

Test #44:

score: 0
Accepted
time: 5ms
memory: 9860kb

input:

109 112

output:

749531455

result:

ok single line: '749531455'

Test #45:

score: 0
Accepted
time: 5ms
memory: 7872kb

input:

92 84

output:

754509307

result:

ok single line: '754509307'

Test #46:

score: 0
Accepted
time: 5ms
memory: 9928kb

input:

111 116

output:

434377961

result:

ok single line: '434377961'

Test #47:

score: 0
Accepted
time: 4ms
memory: 7860kb

input:

95 82

output:

345936119

result:

ok single line: '345936119'

Test #48:

score: 0
Accepted
time: 0ms
memory: 9872kb

input:

106 94

output:

551192069

result:

ok single line: '551192069'

Test #49:

score: 0
Accepted
time: 3ms
memory: 9920kb

input:

110 94

output:

41938476

result:

ok single line: '41938476'

Subtask #5:

score: 1
Accepted

Test #50:

score: 1
Accepted
time: 25ms
memory: 32828kb

input:

1168 346407973

output:

112579949

result:

ok single line: '112579949'

Test #51:

score: 0
Accepted
time: 2ms
memory: 11332kb

input:

313 68910142

output:

83916341

result:

ok single line: '83916341'

Test #52:

score: 0
Accepted
time: 5ms
memory: 9884kb

input:

161 64396010

output:

499230829

result:

ok single line: '499230829'

Test #53:

score: 0
Accepted
time: 32ms
memory: 65572kb

input:

1836 434479347

output:

873178296

result:

ok single line: '873178296'

Test #54:

score: 0
Accepted
time: 24ms
memory: 51612kb

input:

1588 392

output:

611721416

result:

ok single line: '611721416'

Subtask #6:

score: 1
Accepted

Test #55:

score: 1
Accepted
time: 3ms
memory: 9900kb

input:

123 468402382

output:

827499041

result:

ok single line: '827499041'

Test #56:

score: 0
Accepted
time: 12ms
memory: 27416kb

input:

1016 982915840

output:

813922878

result:

ok single line: '813922878'

Test #57:

score: 0
Accepted
time: 3ms
memory: 18556kb

input:

709 58889328

output:

215179237

result:

ok single line: '215179237'

Test #58:

score: 0
Accepted
time: 12ms
memory: 23256kb

input:

884 504516691

output:

199072709

result:

ok single line: '199072709'

Test #59:

score: 0
Accepted
time: 11ms
memory: 43212kb

input:

1414 131

output:

292793609

result:

ok single line: '292793609'

Subtask #7:

score: 1
Accepted

Test #60:

score: 1
Accepted
time: 13ms
memory: 20300kb

input:

779 140176290

output:

438118426

result:

ok single line: '438118426'

Test #61:

score: 0
Accepted
time: 3ms
memory: 13884kb

input:

488 292223807

output:

720591335

result:

ok single line: '720591335'

Test #62:

score: 0
Accepted
time: 10ms
memory: 22016kb

input:

849 198249514

output:

936832149

result:

ok single line: '936832149'

Test #63:

score: 0
Accepted
time: 14ms
memory: 24456kb

input:

929 316667619

output:

684900471

result:

ok single line: '684900471'

Test #64:

score: 0
Accepted
time: 17ms
memory: 37388kb

input:

1282 216

output:

39918106

result:

ok single line: '39918106'

Subtask #8:

score: 1
Accepted

Test #65:

score: 1
Accepted
time: 40ms
memory: 97468kb

input:

2315 21373850

output:

692830582

result:

ok single line: '692830582'

Test #66:

score: 0
Accepted
time: 70ms
memory: 135820kb

input:

2819 54930015

output:

704850526

result:

ok single line: '704850526'

Test #67:

score: 0
Accepted
time: 56ms
memory: 138628kb

input:

2876 518453378

output:

160061956

result:

ok single line: '160061956'

Test #68:

score: 0
Accepted
time: 73ms
memory: 130476kb

input:

2722 126086649

output:

930849830

result:

ok single line: '930849830'

Test #69:

score: 0
Accepted
time: 51ms
memory: 112436kb

input:

2508 121810583

output:

5167845

result:

ok single line: '5167845'

Test #70:

score: 0
Accepted
time: 44ms
memory: 111800kb

input:

2500 4000

output:

805467400

result:

ok single line: '805467400'

Subtask #9:

score: 1
Accepted

Test #71:

score: 1
Accepted
time: 68ms
memory: 122640kb

input:

2631 684393357

output:

936211679

result:

ok single line: '936211679'

Test #72:

score: 0
Accepted
time: 81ms
memory: 140376kb

input:

2913 516585428

output:

664802101

result:

ok single line: '664802101'

Test #73:

score: 0
Accepted
time: 98ms
memory: 142904kb

input:

2966 566883908

output:

74800796

result:

ok single line: '74800796'

Test #74:

score: 0
Accepted
time: 63ms
memory: 112360kb

input:

2508 135568838

output:

345174594

result:

ok single line: '345174594'

Test #75:

score: 0
Accepted
time: 108ms
memory: 142108kb

input:

2948 557406795

output:

163500664

result:

ok single line: '163500664'

Test #76:

score: 0
Accepted
time: 45ms
memory: 111928kb

input:

2500 1000

output:

996821828

result:

ok single line: '996821828'

Subtask #10:

score: 1
Accepted

Test #77:

score: 1
Accepted
time: 94ms
memory: 144520kb

input:

3000 1000000000

output:

543073891

result:

ok single line: '543073891'

Test #78:

score: 0
Accepted
time: 93ms
memory: 144448kb

input:

3000 999999999

output:

453659722

result:

ok single line: '453659722'

Test #79:

score: 0
Accepted
time: 95ms
memory: 144384kb

input:

3000 999999998

output:

98366752

result:

ok single line: '98366752'

Test #80:

score: 0
Accepted
time: 89ms
memory: 144408kb

input:

2999 1000000000

output:

282559837

result:

ok single line: '282559837'

Test #81:

score: 0
Accepted
time: 76ms
memory: 144340kb

input:

2999 999999999

output:

720365773

result:

ok single line: '720365773'

Test #82:

score: 0
Accepted
time: 76ms
memory: 144408kb

input:

2999 999999998

output:

461705162

result:

ok single line: '461705162'

Test #83:

score: 0
Accepted
time: 100ms
memory: 144420kb

input:

2998 1000000000

output:

842668451

result:

ok single line: '842668451'

Test #84:

score: 0
Accepted
time: 98ms
memory: 144296kb

input:

2998 999999999

output:

304660083

result:

ok single line: '304660083'

Test #85:

score: 0
Accepted
time: 77ms
memory: 144316kb

input:

2998 999999998

output:

92840037

result:

ok single line: '92840037'

Test #86:

score: 0
Accepted
time: 67ms
memory: 144532kb

input:

3000 1

output:

1

result:

ok single line: '1'

Test #87:

score: 0
Accepted
time: 96ms
memory: 144544kb

input:

3000 100

output:

513574771

result:

ok single line: '513574771'
English 繁體中文 简体中文

Server Time: 2024-11-29 18:23:49 | OpenSource Project