187782025-11-04 17:53:38algoproPermutációkcpp17Időlimit túllépés 12/1003.089s568 KiB
// UUID: f4e7b4de-48b6-4965-8671-8dbe84a93267
#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(n,k);
	return 0;
	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;
		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;
			}
			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;
				}
				nov2[q][1][pos]=(nov2[q][1][pos]+e)%MOD;
			}
		}
	}
	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;
		}
		cout<<tmp<<" ";
		s=(s+tmp)%MOD;
	}
	ans=(ans-s+MOD)%MOD;
	cout<<endl<<ans;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
3Időlimit túllépés3.085s508 KiB
subtask212/12
4Elfogadva226ms500 KiB
5Elfogadva225ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva225ms508 KiB
subtask30/11
8Időlimit túllépés3.082s316 KiB
9Időlimit túllépés3.082s508 KiB
10Időlimit túllépés3.084s316 KiB
11Időlimit túllépés3.084s316 KiB
subtask40/23
12Időlimit túllépés3.078s316 KiB
13Időlimit túllépés3.076s316 KiB
14Időlimit túllépés3.076s316 KiB
15Időlimit túllépés3.078s508 KiB
16Időlimit túllépés3.073s316 KiB
subtask50/19
17Időlimit túllépés3.081s316 KiB
18Időlimit túllépés3.079s500 KiB
19Időlimit túllépés3.079s316 KiB
20Időlimit túllépés3.081s316 KiB
21Időlimit túllépés3.089s316 KiB
subtask60/35
22Időlimit túllépés3.082s508 KiB
23Időlimit túllépés3.082s316 KiB
24Időlimit túllépés3.082s316 KiB
25Időlimit túllépés3.082s316 KiB
26Időlimit túllépés3.082s316 KiB
27Időlimit túllépés3.084s500 KiB
28Időlimit túllépés3.084s508 KiB
29Időlimit túllépés3.082s568 KiB
30Hibás válasz1ms316 KiB