187782025-11-04 17:53:38algoproPermutációkcpp17Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
3Time limit exceeded3.085s508 KiB
subtask212/12
4Accepted226ms500 KiB
5Accepted225ms316 KiB
6Accepted1ms316 KiB
7Accepted225ms508 KiB
subtask30/11
8Time limit exceeded3.082s316 KiB
9Time limit exceeded3.082s508 KiB
10Time limit exceeded3.084s316 KiB
11Time limit exceeded3.084s316 KiB
subtask40/23
12Time limit exceeded3.078s316 KiB
13Time limit exceeded3.076s316 KiB
14Time limit exceeded3.076s316 KiB
15Time limit exceeded3.078s508 KiB
16Time limit exceeded3.073s316 KiB
subtask50/19
17Time limit exceeded3.081s316 KiB
18Time limit exceeded3.079s500 KiB
19Time limit exceeded3.079s316 KiB
20Time limit exceeded3.081s316 KiB
21Time limit exceeded3.089s316 KiB
subtask60/35
22Time limit exceeded3.082s508 KiB
23Time limit exceeded3.082s316 KiB
24Time limit exceeded3.082s316 KiB
25Time limit exceeded3.082s316 KiB
26Time limit exceeded3.082s316 KiB
27Time limit exceeded3.084s500 KiB
28Time limit exceeded3.084s508 KiB
29Time limit exceeded3.082s568 KiB
30Wrong answer1ms316 KiB