QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557045#2573. Two Permutationsstack343WA 9ms13388kbC++232.8kb2024-09-11 01:14:442024-09-11 01:14:45

Judging History

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

  • [2024-09-11 01:14:45]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:13388kb
  • [2024-09-11 01:14:44]
  • 提交

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;
  ll par=0,use=n;
  dp[0][0]=1;
  for(ll i=1;i<=n;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 or 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/2+1))%=MOD;
      }
    }
    for(ll l=0;l<=k;l++){
      for(ll r=0;r<=2*i;r++){
        dp[l][r]=adp[l][r];
        adp[l][r]=0;
      }
    }
    use--;
  }
  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: 9ms
memory: 13200kb

input:

2 4

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

3 7

output:

12

result:

ok 1 number(s): "12"

Test #3:

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

input:

4 10

output:

24

result:

ok 1 number(s): "24"

Test #4:

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

input:

4 14

output:

96

result:

ok 1 number(s): "96"

Test #5:

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

input:

5 10

output:

0

result:

ok 1 number(s): "0"

Test #6:

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

input:

5 15

output:

120

result:

ok 1 number(s): "120"

Test #7:

score: -100
Wrong Answer
time: 9ms
memory: 13180kb

input:

5 21

output:

1440

result:

wrong answer 1st numbers differ - expected: '2400', found: '1440'