注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 3664  

2013-03-17 18:46:42|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=3664
题意:求集合{1,2...n}的乱序排列中满足有k个ai符合ai>i条件的排列种数,结果对1,000,000,007取余
题解:
开始想了下没什么好的思路,但是有种冥冥中有种感觉这题一定是dp,于是就暴力打表了前几个,看看能不能从结果中找到些什么……

 

0

1

2

3

4

5

6

7

1

1

0

 

 

 

 

 

 

2

1

1

0

 

 

 

 

 

3

1

4

1

0

 

 

 

 

4

1

11

11

1

0

 

 

 

5

1

26

66

26

1

0

 

 

6

1

57

302

302

57

1

0

 

7

1

120

1191

2416

1191

120

1

0

行表示n,列表示k,仔细找了下,发现了其中的规律:
第1列:
4=1*2+1*2;
11=4*2+1*3;
26=11*2+1*4;
57=26*2+1*5;
120=26*2+1*6;

第2列:
11=1*3+4*2;
66=11*3+11*3;
302=66*3+26*4;
1191=302*3+57*5;

第3列:
26=1*4+11*2;
302=26*4+66*3;
2416=302*4+302*4;
……
由此得出递推公式:
f[i][j]=f[i-1][j]*(k+1)+f[i-1][j-1]*(n-k);
边界条件:
f[i][j]=0, i==j;f[i][j]=0, j=0 或者 i=j+1;

/*
* test.cpp
*
* Created on: 2013-03-17
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
#define M 1000000007ll
#define N 1010
#define int64 __int64
int64 f[N][N];

void fun()
{
int i,j;
for(i=0;i<=1000;i++)
for(j=0;j<=1000;j++)
f[i][j]=1;
for(i=3;i<=1000;i++)
for(j=1;j<=i-2;j++)
f[i][j]=(f[i-1][j]*(j+1)%M+f[i-1][j-1]*(i-j)%M)%M;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
int n,k;
fun();
while(scanf("%d%d",&n,&k)!=EOF)
{
if(n==k)
{
printf("0\n");
continue;
}
if(k >= n-k)
k=n-k-1;
printf("%I64d\n",f[n][k]);
}
return 0;
}



  评论这张
 
阅读(92)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018