題目描述

對(duì)于一個(gè)數(shù)列{ai}，如果有i<j且ai>aj，那么我們稱ai與aj為一對(duì)逆序?qū)?shù)。若對(duì)于任意一個(gè)由1~n自然數(shù)組成的數(shù)列，可以很容易求出有多少個(gè)逆序?qū)?shù)。那么逆序?qū)?shù)為k的這樣自然數(shù)數(shù)列到底有多少個(gè)？

輸入輸出格式

輸入格式：

?

第一行為兩個(gè)整數(shù)n，k。

?

輸出格式：

?

寫入一個(gè)整數(shù)，表示符合條件的數(shù)列個(gè)數(shù)，由于這個(gè)數(shù)可能很大，你只需輸出該數(shù)對(duì)10000求余數(shù)后的結(jié)果。

?

輸入輸出樣例

輸入樣例#1：
4 1 輸出樣例#1：
3

說明

樣例說明：

下列3個(gè)數(shù)列逆序?qū)?shù)都為1；分別是1 2 4 3 ；1 3 2 4 ；2 1 3 4；

測(cè)試數(shù)據(jù)范圍

30%的數(shù)據(jù) n<=12

100%的數(shù)據(jù) n<=1000，k<=1000

?

一道簡(jiǎn)單題，但我覺得可以做到更大的數(shù)據(jù)，比方說加兩個(gè)0

從小到大考慮每一位，先考慮1，如果1位于i這個(gè)位置，那1與1~i-1這些位置的每一個(gè)數(shù)都會(huì)產(chǎn)生一個(gè)逆序?qū)?#xff0c;與i+1~n這些位置的數(shù)都不會(huì)產(chǎn)生逆序?qū)?#xff0c;至于具體每個(gè)數(shù)字是什么對(duì)于1的貢獻(xiàn)沒有影響

然后從排列里把1去掉，變成一個(gè)2~n的排列，這個(gè)排列與1~n-1的排列是等價(jià)的，于是問題轉(zhuǎn)化成了一個(gè)較小的問題

然后可以dp

dp[i][j]表示1~i的排列，要有j個(gè)逆序?qū)Φ姆椒〝?shù)，枚舉當(dāng)前位置產(chǎn)生的逆序?qū)磙D(zhuǎn)移，這個(gè)東西本來是nk^2的，但是發(fā)現(xiàn)一個(gè)位置轉(zhuǎn)移的時(shí)候是連續(xù)的一段，用前綴和優(yōu)化去掉一個(gè)k即可

其實(shí)這個(gè)問題等價(jià)于有n個(gè)帶編號(hào)的盒子排成一列，一共放k個(gè)球，標(biāo)號(hào)為i的盒子里不能放超過i-1個(gè)球，求方法總數(shù)，這應(yīng)該是有更好的做法的

UPD1：這個(gè)東西的生成函數(shù)是 $ (1)(1+x)(1+x+x^2)(1+x+x^2+x^3)...(1+x+x^2+...+x^{n-1}) $ 即 $ \prod_{p=1}^{n}\sum_{q=0}^{p-1}x^q?$ ，這個(gè)形式過于美妙讓人很難不認(rèn)為它有一個(gè)優(yōu)美的通解

1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 #include <algorithm> 5 #include <string> 6 #include <cstring> 7 #include <cmath> 8 #include <map> 9 #include <stack> 10 #include <set> 11 #include <vector> 12 #include <queue> 13 #include <time.h> 14 #define eps 1e-7 15 #define INF 0x3f3f3f3f 16 #define MOD 10000 17 #define rep0(j,n) for(int j=0;j<n;++j) 18 #define rep1(j,n) for(int j=1;j<=n;++j) 19 #define pb push_back 20 #define mp make_pair 21 #define set0(n) memset(n,0,sizeof(n)) 22 #define ll long long 23 #define ull unsigned long long 24 #define iter(i,v) for(edge *i=head[v];i;i=i->nxt) 25 #define max(a,b) (a>b?a:b) 26 #define min(a,b) (a<b?a:b) 27 #define print_runtime printf("Running time:%.3lfs\n",double(clock())/1000.0) 28 #define TO(j) printf(#j": %d\n",j); 29 //#define OJ 30 using namespace std; 31 const int MAXINT = 100010; 32 const int MAXNODE = 100010; 33 const int MAXEDGE = 2*MAXNODE; 34 char BUF,*buf; 35 int read(){ 36 char c=getchar();int f=1,x=0; 37 while(!isdigit(c)){if(c=='-') f=-1;c=getchar();} 38 while(isdigit(c)){x=x*10+c-'0';c=getchar();} 39 return f*x; 40 } 41 char get_ch(){ 42 char c=getchar(); 43 while(!isalpha(c)) c=getchar(); 44 return c; 45 } 46 //------------------- Head Files ----------------------// 47 48 int n,k; 49 int dp[10010],sum[10010]; 50 void get_input(); 51 void work(); 52 int main() { 53 get_input(); 54 work(); 55 return 0; 56 } 57 void work(){ 58 fill(sum,sum+k+1,1); 59 for(int i=2;i<=n;i++){ //box no i,can take 0~i-1 60 rep0(j,k+1){ 61 dp[j] = (j-i+1>0?sum[j]-sum[j-i]:sum[j]); 62 } 63 sum[0]=dp[0]; 64 rep1(j,k){ 65 sum[j]=(sum[j-1]+dp[j])%MOD; 66 } 67 } 68 printf("%d\n",(dp[k]+MOD)%MOD); 69 } 70 void get_input(){ 71 n=read();k=read(); 72 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/LoveYayoi/p/6921138.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P2513 [HAOI2009]逆序对数列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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