史前文明

題目描述

明明和白白是好朋友，他們經(jīng)常在一起商量數(shù)學(xué)問題。

明明和白白暑假到巨石陣旅游。他們發(fā)現(xiàn)這些巨石高大聳峙，而且以一種富含魔力的方式排列著。他們面前有n塊石頭，明明給他們編號為1~n。而恰巧編號為i的石頭高度也為i。他們隨后驚奇地發(fā)現(xiàn)這些石頭可以挪動(dòng)，于是他們定義一個(gè)石頭的排列為“魔陣”，當(dāng)且僅當(dāng)這個(gè)排列中最少有n-k個(gè)石頭滿足它所處的位置等于它的高度，即ai=i；

明明明明明白白白白白浪費(fèi)了一天的時(shí)間來搬石頭，但他還是想計(jì)算一下一共有幾種“魔陣”。

輸入

有多組測試樣例。每行兩個(gè)數(shù)n和k，4<=n<=1000? ?1<=k<=4

輸出

每行一個(gè)答案，輸出魔陣的種類數(shù)量。

樣例輸入

4 1 200 3 200 4 1000 4

樣例輸出

1 2646701 584811251 373086956251

分析：

很明顯的錯(cuò)位排列題，由于k很小只有4，所以直接分類討論一下就可以了，甚至暴力都可以完成。

k=1

只有一種，1，2，3，4........n，F[1]=1;

k=2

從n個(gè)數(shù)中選擇2個(gè)，有C(n,2)種選法，選出的兩個(gè)數(shù)交換一下，所以每種選法有1種情況，F[2]=F[1]+C(n,2);

? ? ? 位置	? ? ? ? ? ? ? ? ? 1	? ? ? ? ? ? ? ? ? ? ? 2
? 情況1（合法）	? ? ? ? ? ? ? ? ? 2	? ? ? ? ? ? ? ? ? ? ? 1
情況2（重復(fù)）	? ? ? ? ? ? ? ? ? 1	? ? ? ? ? ? ? ? ? ? ? 2

k=3

從n個(gè)數(shù)中選擇3個(gè)，有C(n,3)種選法，選出的三個(gè)數(shù)有兩種交換，所以每種選法有2種情況

F[3]=F[1]+F[2]+C(n,3)*2

位置	1	2	3
重復(fù)	1	2	3
重復(fù)	1	3	2
重復(fù)	2	1?	3
合法	2	3	1
合法	3	1	2
重復(fù)	3	2	1

k=4

從n個(gè)數(shù)中選擇4個(gè)，有C(n,3)種選法，選出的三個(gè)數(shù)有兩種交換，所以每種選法有9種情況,F[4]=F[1]+F[2}+F[3]+C(n,4)*9

位置	1	2	3	4
1	2	1	4	3
2	2	3	4	1
3	2	4	1	3
4	3	2	4	1
5	3	1	2	4
6	3	1	4	2
7	4	1	2	3
8	4	3	1	2
9	4	3	2	1

#include<bits/stdc++.h> using namespace std; long long int n,k; int main() {while(~scanf("%lld %lld",&n,&k)){long long t=1;if(k==1){printf("1\n");}t+=n*(n-1)/2;if(k==2){printf("%lld\n",t);}t=t+n*(n-1)*(n-2)/3;if(k==3){printf("%lld\n",t);}t=t+n*(n-1)*(n-2)*(n-3)*3/8;if(k==4){printf("%lld\n",t);}}return 0; }

關(guān)于 long long int（64位長整型）的輸出

1<<63? 錯(cuò)誤，由于1默認(rèn)是int型，左移63位后就會(huì)溢出

1LL<<63? 正確，先把1轉(zhuǎn)換為long long 型，然后左移63位就不會(huì)溢出啦

long long t=(1LL<<63); printf("%lld\n",t); printf("%lld\n",1LL<<63);

?

總結(jié)

以上是生活随笔為你收集整理的史前文明 组合数学的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。