QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397309#2573. Two PermutationsNaganohara_YoimiyaAC ✓70ms12896kbC++141.6kb2024-04-23 21:55:032024-04-23 21:55:03

Judging History

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

  • [2024-04-23 21:55:03]
  • 评测
  • 测评结果:AC
  • 用时:70ms
  • 内存:12896kb
  • [2024-04-23 21:55:03]
  • 提交

answer

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=1e9+7;
int ksm(int x,ll y,int p=mod){
	int ans=1;y%=(p-1);
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=105;
int f[2][N][N*N],n,K;

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	n=read(),K=read();
	
	int cur=0;f[cur][0][0]=1;
	for(int i=n;i>=1;i--){
		memset(f[cur^1],0,sizeof(f[cur^1]));
		for(int j=0;j<=n-i;j++)for(int s=0;s<=n*n;s++)if(f[cur][j][s]){
			int k=n-i-j;
			add(f[cur^1][j+2][s],1ll*f[cur][j][s]*k%mod*k%mod);
			add(f[cur^1][j+1][s+i],2ll*f[cur][j][s]*k%mod*(n-j-k-k)%mod);
			add(f[cur^1][j+1][s+i],1ll*f[cur][j][s]*(n-j-k-k)%mod);
			add(f[cur^1][j][s+i+i],1ll*f[cur][j][s]*(n-j-k-k)%mod*(n-j-k-k-1)%mod);
		}
		cur^=1;
//		cout<<"f "<<i<<" = ";for(int j=0;j<=n;j++)for(int s=0;s<=n*n;s++)if(f[cur][j][s])cout<<"("<<j<<","<<s<<" | "<<f[cur][j][s]<<") ";puts("");
	}
	cout<<f[cur][n][K]<<endl;

	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 12832kb

input:

2 4

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

3 7

output:

12

result:

ok 1 number(s): "12"

Test #3:

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

input:

4 10

output:

24

result:

ok 1 number(s): "24"

Test #4:

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

input:

4 14

output:

96

result:

ok 1 number(s): "96"

Test #5:

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

input:

5 10

output:

0

result:

ok 1 number(s): "0"

Test #6:

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

input:

5 15

output:

120

result:

ok 1 number(s): "120"

Test #7:

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

input:

5 21

output:

2400

result:

ok 1 number(s): "2400"

Test #8:

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

input:

6 21

output:

720

result:

ok 1 number(s): "720"

Test #9:

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

input:

6 30

output:

25920

result:

ok 1 number(s): "25920"

Test #10:

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

input:

6 27

output:

106560

result:

ok 1 number(s): "106560"

Test #11:

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

input:

20 300

output:

644873710

result:

ok 1 number(s): "644873710"

Test #12:

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

input:

20 139

output:

0

result:

ok 1 number(s): "0"

Test #13:

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

input:

30 470

output:

491424690

result:

ok 1 number(s): "491424690"

Test #14:

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

input:

30 500

output:

8436035

result:

ok 1 number(s): "8436035"

Test #15:

score: 0
Accepted
time: 7ms
memory: 12752kb

input:

40 1000

output:

617159088

result:

ok 1 number(s): "617159088"

Test #16:

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

input:

40 900

output:

729805907

result:

ok 1 number(s): "729805907"

Test #17:

score: 0
Accepted
time: 13ms
memory: 12812kb

input:

60 1830

output:

16340084

result:

ok 1 number(s): "16340084"

Test #18:

score: 0
Accepted
time: 19ms
memory: 12752kb

input:

60 2000

output:

832198921

result:

ok 1 number(s): "832198921"

Test #19:

score: 0
Accepted
time: 69ms
memory: 12740kb

input:

100 5050

output:

437918130

result:

ok 1 number(s): "437918130"

Test #20:

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

input:

100 700

output:

0

result:

ok 1 number(s): "0"

Test #21:

score: 0
Accepted
time: 66ms
memory: 12816kb

input:

100 10000

output:

0

result:

ok 1 number(s): "0"