2729: [HNOI2012]排队

2729: [HNOI2012]排队

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 957  Solved: 449

[Submit][Status]

Description

某中学有 n 名男同学,m 名女同学和两名老师要排队参加体检。他们排成一条直线,并且任意两名女同学不能相邻,两名老师也不能相邻,那么一共有多少种排法呢?(注意:任意两个人都是不同的)

Input

只有一行且为用空格隔开的两个非负整数 n 和 m,其含义如上所述。

对于 30%的数据 n≤100,m≤100

对于 100%的数据 n≤2000,m≤2000

Output

输出文件 output.txt 仅包含一个非负整数,表示不同的排法个数。注意答案可能很大。

Sample Input

1 1

Sample Output

12

HINT

Source

day1

题解:做完此题发现我还是摆脱不了逗比的本性——好好的高精度,结果输出时弄反了。。。呵呵呵。。。典型的对自己自信过头的后果 说思路吧:经典的插空思想,男生爱咋搞砸搞,于是N!,然后接下来轮到妹纸和Teacher,老师不在一起时,则很明显情况为m*C(n+1,1)*C(n+2,m-1)也就是m*(n+1)*C(n+2,m-1),在一起时就是C(n+3,m)*C(n+1,2),然后直接求和没了,高精度啥的是显然的。。。只求别在逗比TT

 1 /**************************************************************
 2     Problem: 2729
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:1920 ms
 7     Memory:1008 kb
 8 ****************************************************************/
 9  
10 type 
11         arr=array [0..100001] of longint;  
12 var 
13         i,j,k,l,m,n,a1,a2,a3,a4:longint;  
14         a,b:arr;    
15 procedure multy (var a:arr; b:longint);inline;  
16 var 
17         i:longint;  
18 begin 
19         for i:=1 to a[0] do a[i]:=a[i]*b;  
20         i:=1;  
21         while (i<=a[0])or(a[i]>0) do 
22                 begin 
23                         a[i+1]:=a[i+1]+a[i] div 10;  
24                         a[i]:=a[i] mod 10;  
25                         inc(i);  
26                 end;  
27         dec(i);  
28         a[0]:=i;  
29 end;  
30    
31 procedure addty (var a,b:arr);inline;  
32 var 
33         i,k:longint;  
34 begin 
35         if a[0]>b[0] then k:=a[0] else k:=b[0];  
36         for i:=1 to k do 
37                 begin 
38                         a[i]:=a[i]+b[i];  
39                         a[i+1]:=a[i+1]+a[i] div 10;  
40                         a[i]:=a[i] mod 10;  
41                 end;  
42         if a[k+1]<>0 then inc(k);  
43         a[0]:=k;  
44 end;  
45    
46 begin 
47         readln(n,m);  
48         if (n=0)and(m=0) then begin writeln(0);halt; end;  
49     fillchar(b,sizeof(b),0);
50         b[1]:=1;  b[0]:=1;  
51         multy(b,n+1);  
52         multy(b,2);  
53         multy(b,m);  
54         for i:=n+2-m+2 to n+2 do multy(b,i);  
55         a:=b;  
56         fillchar(b,sizeof(b),0);  
57         b[0]:=1;  b[1]:=1;  
58         multy(b,n+1);  
59         multy(b,n);  
60         for i:=n+4-m to n+3 do multy(b,i);  
61         addty(a,b);  
62         for i:=2 to n do multy(a,i);  
63         for i:=a[0] downto 1 do write(a[i]);  
64         writeln;  
65 end.  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

长文 | 手把手教你如何使用python进行数据分析(最好将文章代码自己码一遍)

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 原文 http://www.cnbl...

40250
来自专栏专知

【 关关的刷题日记50】 Leetcode 345. Reverse Vowels of a String

关关的刷题日记50 – Leetcode 345. Reverse Vowels of a String 题目 Write a function that ta...

27630
来自专栏算法修养

HYSBZ 2160 拉拉队排练(回文树)

2160: 拉拉队排练 Time Limit: 10 Sec  Memory Limit: 259 MB Submit: 825  Solved: 324 [...

36270
来自专栏专注研发

poj-1008-玛雅历

上周末,M.A. Ya教授对古老的玛雅有了一个重大发现。从一个古老的节绳(玛雅人用于记事的工具)中,教授发现玛雅人使用了一个一年有365天的叫做Haab的历法...

19430
来自专栏CodeSheep的技术分享

函数式编程思维在三行代码情书中的应用

25050
来自专栏tkokof 的技术,小趣及杂念

Sweet Snippet 之 Bounce Setting

  又是一篇Sweet Snippet,自己看来都觉得过小,不足以成篇,不过自觉有些趣味,也就随便记一记了,权当自娱自乐 :)

7410
来自专栏ACM算法日常

水果(STL+排序)- HDU 1263

夏天来了~~好开心啊,呵呵,好多好多水果~~ Joe经营着一个不大的水果店.他认为生存之道就是经营最受顾客欢迎的水果.现在他想要一份水果销售情况的明细表,这样J...

10710
来自专栏ACM算法日常

CodeForces 982F:The Meeting Place Cannot Be Changed(有向图)

Petr is a detective in Braginsk. Somebody stole a huge amount of money from a ba...

10610
来自专栏专知

【LeetCode 290】 关关的刷题日记28 Word Pattern

关关的刷题日记28 – Leetcode 290. Word Pattern 题目 Given a pattern and a string str, find...

35280
来自专栏开发与安全

从零开始学C++之STL(六):变动性算法源代码分析与使用示例(copy_backward、 transform、 replace_copy_if 等)

首先回顾前面的文章,我们把for_each 归类为非变动性算法,实际上它也可以算是变动性算法,取决于传入的第三个参数,即函数 指针。如果在函数内对容器元素做了修...

20800

扫码关注云+社区

领取腾讯云代金券