首页 > 代码库 > [luoguP2401] 不等数列

[luoguP2401] 不等数列

传送门

 

f[i][j]表示前i个数有j个<的方案数

 

#include <cstdio>#define N 1001#define p 2015int n, k;int f[N][N];int main(){	int i, j;	scanf("%d %d", &n, &k);	f[2][0] = 1;	f[2][1] = 1;	for(i = 3; i <= n; i++)		for(j = 0; j < i; j++)		{			//插头 			f[i][j] = (f[i][j] + f[i - 1][j]) % p;			//插尾			if(j) f[i][j] = (f[i][j] + f[i - 1][j - 1]) % p;			//插中间 			//替换 <			f[i][j] = (f[i][j] + f[i - 1][j] * j % p) % p;			//替换 >			if(j) f[i][j] = (f[i][j] + f[i - 1][j - 1] * (i - j - 1) % p) % p; 		}	printf("%d\n", f[n][k]);	return 0;}	 

 

[luoguP2401] 不等数列