187842025-11-04 18:01:54horkaPermutációkcpp17Futási hiba 54/1003.089s4668 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7,c=305;
int dp[2][c][c];
int nov[2][c][c],nov2[2][c][c]; //curr, pos 
int brute(int n, int k)
{
	k=n-k;
	int ans=0;
	vector<int> v(n);
	iota(v.begin(),v.end(),1);
	do
	{
		vector<int> pos(n+1);
		for(int i=0; i<n; i++)
			pos[v[i]]=i;
		int curr=1;
		bool ok=0;
		for(int i=2; i<=n; i++)
		{
			if(pos[i]>pos[i-1]) curr++;
			else curr=1;
			if(curr>=k) ok=1;
		}
		if(ok) ans++;
	}
	while(next_permutation(v.begin(),v.end()));
	return ans;

}
signed main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,k; cin>>n>>k;
	//cout<<brute(3,1)<<" "<<brute(7,4)<<" "<<brute(n,k)<<endl;
	k=n-k;
	int ans=1;
	for(int i=2; i<=n; i++)
		ans=ans*i%MOD;
	if(k<=1)
	{
		cout<<ans<<"\n";
		return 0;
	}
	dp[1][1][1]=1;
	for(int i=1; i<=n; i++)
	{
		int p=i%2,q=1-p;
		for(int a=0; a<k; a++)
			for(int b=0; b<=n; b++)
				nov[q][a][b]=0,nov2[q][a][b]=0,dp[q][a][b]=0;
		for(int curr=1; curr<k; curr++)
		{
			for(int pos=1; pos<=i; pos++)
			{
				nov[p][curr][pos]=(nov[p][curr][pos]+nov[p][curr][pos-1])%MOD;
				dp[p][curr][pos]=(dp[p][curr][pos]+nov[p][curr][pos])%MOD;
			}
			for(int pos=i; pos>0; pos--)
			{
				nov2[p][curr][pos]=(nov2[p][curr][pos]+nov2[p][curr][pos+1])%MOD;
				dp[p][curr][pos]=(dp[p][curr][pos]+nov2[p][curr][pos])%MOD;
			}
			if(i<n){
			for(int pos=1; pos<=i; pos++)
			{
				int e=dp[p][curr][pos];
				if(curr+1<k)
				{
					nov[q][curr+1][pos+1]=(nov[q][curr+1][pos+1]+e)%MOD;
				}
				//if(i==2 && pos==1) cout<<"itt: "<<e<<endl;
				nov2[q][1][pos]=(nov2[q][1][pos]+e)%MOD;
			}
			}
		}
		/*cout<<i<<": ";
		for(int pos=1; pos<=i; pos++)
			cout<<dp[p][1][pos]<<" ";
		cout<<endl;*/
	}
	int s=0;
	for(int i=1; i<k; i++)
	{
		int tmp=0;
		for(int pos=1; pos<=n; pos++)
		{
			tmp=(tmp+dp[n%2][i][pos])%MOD;
		}
		s=(s+tmp)%MOD;
	}
	ans=(ans-s+MOD)%MOD;
	cout<<ans;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
3Futási hiba6ms4660 KiB
subtask212/12
4Elfogadva1ms316 KiB
5Elfogadva1ms564 KiB
6Elfogadva1ms508 KiB
7Elfogadva1ms316 KiB
subtask30/11
8Futási hiba7ms4660 KiB
9Futási hiba7ms4660 KiB
10Futási hiba6ms4660 KiB
11Futási hiba6ms4660 KiB
subtask423/23
12Elfogadva2ms316 KiB
13Elfogadva6ms1076 KiB
14Elfogadva7ms1260 KiB
15Elfogadva10ms1588 KiB
16Elfogadva1ms500 KiB
subtask519/19
17Elfogadva46ms1200 KiB
18Elfogadva151ms2908 KiB
19Elfogadva263ms4648 KiB
20Elfogadva1ms416 KiB
21Elfogadva1ms316 KiB
subtask60/35
22Futási hiba7ms4660 KiB
23Futási hiba8ms4660 KiB
24Futási hiba7ms4660 KiB
25Futási hiba6ms4660 KiB
26Időlimit túllépés3.089s4148 KiB
27Elfogadva1ms316 KiB
28Futási hiba6ms4668 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB