QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#419408 | #8702. 狼人杀 | BreakPlus | 100 ✓ | 89ms | 23472kb | C++14 | 3.4kb | 2024-05-23 21:40:00 | 2024-05-23 21:40:01 |
Judging History
answer
/*-----------------------------------------------*/
/* Everything that kills me makes me feel alive. */
/* Email: [email protected] */
/* Author: wzj_zhzx_oicon / BreakPlus */
/*-----------------------------------------------*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<pair<ll,ll>,ll> P3;
typedef pair<pair<ll,ll>,pair<ll,ll> >P4;
#define mkp make_pair
#define fi first
#define se second
#define popcnt __builtin_popcountll
#define pb emplace_back
//#define FastIO
//#define OIcontest
const ll mod=1e9+7;
const ll maxn=500005;
inline ll read(){
ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f;
}
inline ll lowbit(ll x){ return x&-x; }
struct Bit{
ll c[maxn], _x[maxn], _w[maxn], tp=0;
void update(ll x,ll w){ _x[++tp]=x, _w[tp]=w; while(x<maxn) c[x]+=w, x+=lowbit(x);}
void update2(ll x,ll w){ while(x<maxn) c[x]+=w, x+=lowbit(x);}
ll query(ll x){ ll res=0; while(x) res+=c[x], x-=lowbit(x); return res; }
void clear(){ for(ll i=1;i<=tp;i++) update2(_x[i], -_w[i]); tp=0;}
void fclear(){ tp=0; memset(c, 0, sizeof(c)); }
}bit;
inline ll maxx(ll a,ll b){ return a>b?a:b; }
inline ll minn(ll a,ll b){ return a<b?a:b; }
inline void chkmax(ll &a,ll b){ a = maxx(a, b); }
inline void chkmin(ll &a,ll b){ a = minn(a, b); }
inline void _Add(ll &a,ll b){ a+=b; if(a>=mod) a-=mod; }
inline void _Minus(ll &a,ll b){ a-=b; if(a<0) a+=mod; }
inline ll Add(ll a,ll b){ a+=b; if(a>=mod) a-=mod; return a; }
inline ll Minus(ll a,ll b){ a-=b; if(a<0) a+=mod; return a; }
inline ll qpow(ll a,ll b){
ll ans=1, base=a;
while(b){ if(b&1) ans=1ll*ans*base%mod; base=1ll*base*base%mod; b>>=1; }
return ans;
}
struct Comb{
ll fac[maxn], inv[maxn];
Comb(){
fac[0]=1; for(ll i=1;i<=maxn-5;i++) fac[i]=1ll*fac[i-1]*i%mod;
inv[maxn-5]=qpow(fac[maxn-5],mod-2); for(ll i=maxn-6;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
ll C(ll a,ll b){ if(a<0 || b<0 || a<b) return 0; return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod; }
}comb;
ll Fac(ll x){return comb.fac[x];}ll iFac(ll x){return comb.inv[x];}ll Inv(ll x){return qpow(x, mod-2);}
/*--------------head------------------*/
void init(){
}
void clear(){ }
ll n,m,dp[155][13005][2], w1[160], w2[160], t;
void solve(){
n=read(), m=read();
dp[0][0][0] = 1;
for(ll i=0;i<n;i++)
for(ll j=0;j<n*(n+1)/2;j++)
for(ll k=0;k<=1;k++){
if(!dp[i][j][k]) continue;
for(ll l=i+1;l<=n;l++){
ll mor = (i<m && l>=m) ? ((l-i) * (l-i+1)/2) : ((l-i) * (l-i-1) / 2);
if(!k) _Add(dp[l][j+mor][1], mod-dp[i][j][k]);
_Add(dp[l][j+mor][k], mod-dp[i][j][k]);
}
}
ll ans=0, is = qpow(n-1, mod-2);
for(ll j=0;j<n*(n+1)/2;j++){
ll tmp = n*(n+1)/2*Inv(n*(n+1)/2-j)%mod;
_Add(ans, tmp * dp[n][j][0] % mod * n % mod * is % mod);
_Add(ans, mod - tmp * dp[n][j][1] % mod * is % mod);
}
printf("%lld\n", ans);
}
int main(){
#ifdef OIcontest
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
#ifdef FastIO
ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#endif
init();
ll T=1;
while(T--) clear(), solve();
return 0;
}
/*
Input1 Text Copied:
Answer1 Text Copied:
Input2 Text Copied:
Answer2 Text Copied:
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 23
Accepted
Test #1:
score: 23
Accepted
time: 3ms
memory: 14172kb
input:
12 2
output:
183756997
result:
ok single line: '183756997'
Test #2:
score: 0
Accepted
time: 6ms
memory: 14144kb
input:
17 6
output:
97571903
result:
ok single line: '97571903'
Test #3:
score: 0
Accepted
time: 6ms
memory: 12004kb
input:
13 3
output:
209826617
result:
ok single line: '209826617'
Test #4:
score: 0
Accepted
time: 6ms
memory: 14088kb
input:
13 8
output:
176038768
result:
ok single line: '176038768'
Test #5:
score: 0
Accepted
time: 3ms
memory: 14112kb
input:
18 4
output:
288404061
result:
ok single line: '288404061'
Test #6:
score: 0
Accepted
time: 6ms
memory: 14164kb
input:
10 10
output:
219657163
result:
ok single line: '219657163'
Test #7:
score: 0
Accepted
time: 6ms
memory: 14128kb
input:
19 15
output:
590577825
result:
ok single line: '590577825'
Test #8:
score: 0
Accepted
time: 0ms
memory: 12048kb
input:
11 6
output:
488143489
result:
ok single line: '488143489'
Test #9:
score: 0
Accepted
time: 6ms
memory: 14008kb
input:
10 5
output:
470594541
result:
ok single line: '470594541'
Test #10:
score: 0
Accepted
time: 0ms
memory: 14100kb
input:
20 5
output:
582458555
result:
ok single line: '582458555'
Test #11:
score: 0
Accepted
time: 6ms
memory: 14160kb
input:
20 12
output:
648081410
result:
ok single line: '648081410'
Test #12:
score: 0
Accepted
time: 6ms
memory: 14100kb
input:
20 4
output:
335777285
result:
ok single line: '335777285'
Test #13:
score: 0
Accepted
time: 6ms
memory: 12088kb
input:
20 15
output:
389216500
result:
ok single line: '389216500'
Test #14:
score: 0
Accepted
time: 6ms
memory: 12236kb
input:
20 16
output:
582458555
result:
ok single line: '582458555'
Test #15:
score: 0
Accepted
time: 3ms
memory: 14088kb
input:
20 19
output:
589126150
result:
ok single line: '589126150'
Test #16:
score: 0
Accepted
time: 7ms
memory: 14288kb
input:
20 6
output:
389216500
result:
ok single line: '389216500'
Subtask #2:
score: 34
Accepted
Dependency #1:
100%
Accepted
Test #17:
score: 34
Accepted
time: 3ms
memory: 12516kb
input:
49 14
output:
486918542
result:
ok single line: '486918542'
Test #18:
score: 0
Accepted
time: 3ms
memory: 14204kb
input:
28 13
output:
642223597
result:
ok single line: '642223597'
Test #19:
score: 0
Accepted
time: 3ms
memory: 16336kb
input:
35 23
output:
842346505
result:
ok single line: '842346505'
Test #20:
score: 0
Accepted
time: 0ms
memory: 14580kb
input:
47 11
output:
583647040
result:
ok single line: '583647040'
Test #21:
score: 0
Accepted
time: 6ms
memory: 12108kb
input:
34 30
output:
990970048
result:
ok single line: '990970048'
Test #22:
score: 0
Accepted
time: 6ms
memory: 12176kb
input:
30 7
output:
393675971
result:
ok single line: '393675971'
Test #23:
score: 0
Accepted
time: 3ms
memory: 14436kb
input:
43 5
output:
737421246
result:
ok single line: '737421246'
Test #24:
score: 0
Accepted
time: 7ms
memory: 14312kb
input:
30 21
output:
254760745
result:
ok single line: '254760745'
Test #25:
score: 0
Accepted
time: 6ms
memory: 14200kb
input:
27 22
output:
266692865
result:
ok single line: '266692865'
Test #26:
score: 0
Accepted
time: 7ms
memory: 14388kb
input:
40 12
output:
133652311
result:
ok single line: '133652311'
Test #27:
score: 0
Accepted
time: 3ms
memory: 14216kb
input:
29 4
output:
873892090
result:
ok single line: '873892090'
Test #28:
score: 0
Accepted
time: 7ms
memory: 12464kb
input:
50 46
output:
267950067
result:
ok single line: '267950067'
Test #29:
score: 0
Accepted
time: 4ms
memory: 14500kb
input:
50 11
output:
423642322
result:
ok single line: '423642322'
Test #30:
score: 0
Accepted
time: 7ms
memory: 14644kb
input:
50 43
output:
625476642
result:
ok single line: '625476642'
Test #31:
score: 0
Accepted
time: 7ms
memory: 14648kb
input:
50 36
output:
767166129
result:
ok single line: '767166129'
Test #32:
score: 0
Accepted
time: 2ms
memory: 14592kb
input:
50 14
output:
357467965
result:
ok single line: '357467965'
Test #33:
score: 0
Accepted
time: 0ms
memory: 14652kb
input:
50 30
output:
219673347
result:
ok single line: '219673347'
Test #34:
score: 0
Accepted
time: 8ms
memory: 14512kb
input:
50 44
output:
392786132
result:
ok single line: '392786132'
Test #35:
score: 0
Accepted
time: 7ms
memory: 14580kb
input:
50 10
output:
848251616
result:
ok single line: '848251616'
Subtask #3:
score: 43
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #36:
score: 43
Accepted
time: 7ms
memory: 15376kb
input:
75 47
output:
668751416
result:
ok single line: '668751416'
Test #37:
score: 0
Accepted
time: 12ms
memory: 15460kb
input:
75 41
output:
310834114
result:
ok single line: '310834114'
Test #38:
score: 0
Accepted
time: 54ms
memory: 20728kb
input:
133 124
output:
57167600
result:
ok single line: '57167600'
Test #39:
score: 0
Accepted
time: 44ms
memory: 20248kb
input:
129 74
output:
751074385
result:
ok single line: '751074385'
Test #40:
score: 0
Accepted
time: 57ms
memory: 20992kb
input:
135 133
output:
759430862
result:
ok single line: '759430862'
Test #41:
score: 0
Accepted
time: 12ms
memory: 15456kb
input:
75 19
output:
967921272
result:
ok single line: '967921272'
Test #42:
score: 0
Accepted
time: 47ms
memory: 19544kb
input:
124 9
output:
641081661
result:
ok single line: '641081661'
Test #43:
score: 0
Accepted
time: 8ms
memory: 15508kb
input:
76 66
output:
465902083
result:
ok single line: '465902083'
Test #44:
score: 0
Accepted
time: 67ms
memory: 22156kb
input:
142 13
output:
12401929
result:
ok single line: '12401929'
Test #45:
score: 0
Accepted
time: 89ms
memory: 22816kb
input:
150 5
output:
388058135
result:
ok single line: '388058135'
Test #46:
score: 0
Accepted
time: 24ms
memory: 15768kb
input:
109 97
output:
381109644
result:
ok single line: '381109644'
Test #47:
score: 0
Accepted
time: 80ms
memory: 23208kb
input:
150 133
output:
174431234
result:
ok single line: '174431234'
Test #48:
score: 0
Accepted
time: 86ms
memory: 23364kb
input:
150 147
output:
198921722
result:
ok single line: '198921722'
Test #49:
score: 0
Accepted
time: 84ms
memory: 22892kb
input:
150 142
output:
631473185
result:
ok single line: '631473185'
Test #50:
score: 0
Accepted
time: 85ms
memory: 23472kb
input:
150 136
output:
743180069
result:
ok single line: '743180069'
Test #51:
score: 0
Accepted
time: 85ms
memory: 23472kb
input:
150 138
output:
621574340
result:
ok single line: '621574340'
Test #52:
score: 0
Accepted
time: 85ms
memory: 21532kb
input:
150 119
output:
872660153
result:
ok single line: '872660153'
Test #53:
score: 0
Accepted
time: 89ms
memory: 22716kb
input:
150 144
output:
939939060
result:
ok single line: '939939060'
Test #54:
score: 0
Accepted
time: 87ms
memory: 23412kb
input:
150 1
output:
166208360
result:
ok single line: '166208360'
Test #55:
score: 0
Accepted
time: 88ms
memory: 23204kb
input:
150 75
output:
353929212
result:
ok single line: '353929212'