QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557050#2573. Two Permutationsstack343AC ✓215ms58680kbC++232.8kb2024-09-11 01:24:172024-09-11 01:24:17

Judging History

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

  • [2024-09-11 01:24:17]
  • 评测
  • 测评结果:AC
  • 用时:215ms
  • 内存:58680kb
  • [2024-09-11 01:24:17]
  • 提交

answer

#pragma GCC optimize("Ofast")
 
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;   
using namespace std;
#define ll long long
#define ld long double
#define nline "\n"
#define f first
#define s second
#define sz(x) (ll)x.size()
#define vl vector<ll>
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define all(x) x.begin(),x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------     
const ll MOD=1e9+7;
const ll MAX=500500;
const ll max_k=20020;
const ll max_n=303;
ll dp[max_k][max_n],adp[max_k][max_n],a[max_k];
vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1);
ll binpow(ll a,ll b,ll MOD){
    ll ans=1;
    a%=MOD;  
    while(b){
        if(b&1)
            ans=(ans*a)%MOD;
        b/=2;
        a=(a*a)%MOD;
    }
    return ans;
}
ll inverse(ll a,ll MOD){
    return binpow(a,MOD-2,MOD);
} 
void precompute(ll MOD){
    for(ll i=2;i<MAX;i++){
        fact[i]=(fact[i-1]*i)%MOD;
    }
    inv_fact[MAX-1]=inverse(fact[MAX-1],MOD);
    for(ll i=MAX-2;i>=0;i--){
        inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD;
    }
}
ll nCr(ll a,ll b,ll MOD){
    if((a<0)||(a<b)||(b<0))
        return 0;   
    ll denom=(inv_fact[b]*inv_fact[a-b])%MOD;
    return (denom*fact[a])%MOD;  
}
void solve(){ 
  ll n,k; cin>>n>>k;
  dp[0][0]=1;
  for(ll i=1;i<=n;i++){
    ll use=n+1-i;
    for(ll sum=0;sum<=k;sum++){
      for(ll need=0;need<=n;need+=2){
        if(dp[sum][need]==0){
          continue;
        }
        ll not_need=2*i-2-need;
        if(not_need<=-1){
          continue;
        }
        not_need/=2;
        ll rem=n-need-not_need;
        if(need>=2){
          (adp[sum][need-2]+=dp[sum][need]*(need/2)*(need/2))%=MOD;
        }
        (adp[sum+use+use][need+2]+=2ll*dp[sum][need]*nCr(rem,2,MOD))%=MOD;
        (adp[sum+use][need]+=dp[sum][need]*rem*(need+1))%=MOD;
      }
    }
    for(ll l=0;l<=k;l++){
      for(ll r=0;r<=n;r++){
        dp[l][r]=adp[l][r];
        adp[l][r]=0;
      }
    }
  }
  cout<<dp[k][0]<<nline;
  return;    
}  
int main()                                                                                 
{         
  ios_base::sync_with_stdio(false);                         
  cin.tie(NULL);                              
  ll test_cases=1;                 
  //cin>>test_cases;
  precompute(MOD);
  while(test_cases--){
    solve();
  }
  cout<<fixed<<setprecision(12);  
  cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 13208kb

input:

2 4

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 9ms
memory: 13164kb

input:

3 7

output:

12

result:

ok 1 number(s): "12"

Test #3:

score: 0
Accepted
time: 9ms
memory: 13232kb

input:

4 10

output:

24

result:

ok 1 number(s): "24"

Test #4:

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

input:

4 14

output:

96

result:

ok 1 number(s): "96"

Test #5:

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

input:

5 10

output:

0

result:

ok 1 number(s): "0"

Test #6:

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

input:

5 15

output:

120

result:

ok 1 number(s): "120"

Test #7:

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

input:

5 21

output:

2400

result:

ok 1 number(s): "2400"

Test #8:

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

input:

6 21

output:

720

result:

ok 1 number(s): "720"

Test #9:

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

input:

6 30

output:

25920

result:

ok 1 number(s): "25920"

Test #10:

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

input:

6 27

output:

106560

result:

ok 1 number(s): "106560"

Test #11:

score: 0
Accepted
time: 6ms
memory: 13764kb

input:

20 300

output:

644873710

result:

ok 1 number(s): "644873710"

Test #12:

score: 0
Accepted
time: 9ms
memory: 13692kb

input:

20 139

output:

0

result:

ok 1 number(s): "0"

Test #13:

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

input:

30 470

output:

491424690

result:

ok 1 number(s): "491424690"

Test #14:

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

input:

30 500

output:

8436035

result:

ok 1 number(s): "8436035"

Test #15:

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

input:

40 1000

output:

617159088

result:

ok 1 number(s): "617159088"

Test #16:

score: 0
Accepted
time: 9ms
memory: 16184kb

input:

40 900

output:

729805907

result:

ok 1 number(s): "729805907"

Test #17:

score: 0
Accepted
time: 22ms
memory: 19928kb

input:

60 1830

output:

16340084

result:

ok 1 number(s): "16340084"

Test #18:

score: 0
Accepted
time: 18ms
memory: 22632kb

input:

60 2000

output:

832198921

result:

ok 1 number(s): "832198921"

Test #19:

score: 0
Accepted
time: 90ms
memory: 36444kb

input:

100 5050

output:

437918130

result:

ok 1 number(s): "437918130"

Test #20:

score: 0
Accepted
time: 21ms
memory: 16080kb

input:

100 700

output:

0

result:

ok 1 number(s): "0"

Test #21:

score: 0
Accepted
time: 215ms
memory: 58680kb

input:

100 10000

output:

0

result:

ok 1 number(s): "0"