UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#164600#2908. countBlahDuckling74710042ms2812kbC++111.1kb2022-11-05 09:59:362022-11-05 13:01:35

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod=1e9+7;
const int precLen=200000;

ll qpow(ll a,ll n){
    ll res=1;
    while(n){
        if(n&1)res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}

int fact[precLen+5],finv[precLen+5];

ll binom(int n,int r){
    return (ll)fact[n]*finv[n-r]%mod*finv[r]%mod;
}

void initialization(){
    fact[0]=1;
    for(int i=1;i<=precLen;i++){
        fact[i]=(ll)fact[i-1]*i%mod;
    }
    finv[precLen]=qpow(fact[precLen],mod-2);
    for(int i=precLen-1;i>=0;i--){
        finv[i]=(ll)finv[i+1]*(i+1)%mod;
    }
}

void mian(){
    int n,m,ans=0,row=0,col=0;
    cin>>n>>m;
    n--;m--;
    for(int i=0;i<n;i++)col=(col+binom(m+i,i))%mod;
    for(int j=0;j<m;j++)row=(row+binom(n+j,j))%mod;
    for(int i=0;i<=n;i++)ans=(ans+(i+1ll)*row)%mod;
    for(int j=0;j<=m;j++)ans=(ans+(j+1ll)*col)%mod;
    cout<<ans<<'\n';
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    initialization();
    int T;
    cin>>T;
    while(T--)mian();

    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 20
Accepted
time: 4ms
memory: 2808kb

input:

10
1 1
2000 1997
117 1647
392 452
959 1883
1046 1627
1398 1124
1372 306
1799 1007
111 1765

output:

0
57631948
737963048
807538931
137760374
398194748
77480423
174938019
583393917
445670336

result:

ok 10 lines

Test #2:

score: 20
Accepted
time: 4ms
memory: 2812kb

input:

10
1 1
2000 1997
1218 1479
350 1244
784 1715
999 92
396 1393
1726 1511
624 756
900 317

output:

0
57631948
610566455
356523655
593949258
665757514
349394180
73375269
50652564
663822508

result:

ok 10 lines

Test #3:

score: 20
Accepted
time: 12ms
memory: 2808kb

input:

10
1 1
100000 99997
36934 50467
5497 37576
83775 15544
23817 68917
33052 49207
59924 39340
2708 2614...

output:

0
73866797
788834869
539491921
582239610
497376436
343937059
324406513
13225836
35059446

result:

ok 10 lines

Test #4:

score: 20
Accepted
time: 8ms
memory: 2812kb

input:

10
1 1
100000 99997
6792 14252
90281 65716
46434 67120
18977 30384
16191 33996
3425 10433
31783 4263...

output:

0
73866797
609230597
213203975
638117274
527713366
525065128
867713025
174019248
375031322

result:

ok 10 lines

Test #5:

score: 20
Accepted
time: 14ms
memory: 2812kb

input:

10
1 1
100000 99994
47270 99792
93093 92620
88764 20724
48143 99711
33293 89038
2816 16811
97638 670...

output:

0
796648553
5720713
279796657
802039459
22848874
23038351
610731858
629891152
812026839

result:

ok 10 lines