首页 > 代码库 > Permutations 好题

Permutations 好题

2024-07-14 00:58:22   226人阅读

 Permutations

Time Limit: 20000/10000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
SubmitStatus

Problem Description

给出两个正整数N、K，问存在多少个长度为N的排列，满足其峰顶数目为K。所谓排列就是有一个序列a[1] ...a[N]，每个数均不相同，且都是1 

<= a[i] <= N，a[i]是峰顶的意思是 a[i] > a[i - 1] && a[i] > a[i + 1]，对于边界，我们假设a[0] = -1000000000 和 a[N + 

1] = -1000000000

Input

多组数据，每组数据一行，N,K(1 <= N <= 10^18, 1 <= K <= 30)

Output

每组数据一行，你的答案 % 239

Sample Input

5 15 23 110 3

Sample Output

16884131

Hint

比如对于排列1 3 2 4 5，a[2] = 3和a[5] = 5都是峰顶，因此这个排列峰顶数目为2
 
 
  1 #include <iostream>  2 #include <string.h>  3 #include <algorithm>  4 #include <math.h>  5 #include <stdio.h>  6 using namespace std;  7 #define ll long long  8 #define MAX 32  9 #define mod 239 10 struct matrix 11 { 12     int a[MAX][MAX]; 13 } origin,res,anss,ansa; 14 matrix multiply(matrix x,matrix y) 15 { 16     matrix temp; 17     memset(temp.a,0,sizeof(temp.a)); 18     int i,j,k; 19     for(k=0; k<MAX; k++) 20         for(i=0; i<MAX; i++) 21             if(x.a[i][k]) 22                 for(j=0; j<MAX; j++) 23                     temp.a[i][j]+=x.a[i][k]*y.a[k][j]%mod,temp.a[i][j]%mod; 24     return temp; 25 } 26 void calc(ll x) 27 { 28     memset(res.a,0,sizeof(res.a)); 29     int i; 30     for(i=0; i<MAX; i++) 31         res.a[i][i]=1; 32     while(x) 33     { 34         if(x&1) 35             res=multiply(res,origin); 36         origin=multiply(origin,origin); 37         x>>=1; 38     } 39 } 40 void init(int x) 41 { 42     memset(origin.a,0,sizeof(origin.a)); 43     int i,j; 44     for(i=1; i<MAX; i++) 45     { 46         j=i-1; 47         origin.a[i][i]=2*i; 48         origin.a[i][j]=(x-2*j)%mod; 49     } 50 } 51 int dp[241][241]= {0},ans; 52 void init1() 53 { 54     int i,j; 55     dp[1][1]=1; 56     for(i=2; i<241; i++) 57         for(j=1; j<i; j++) 58             dp[i][j]=((dp[i-1][j]*2*j)%mod+(dp[i-1][j-1]*max(0,i-2*j+2))%mod)%mod; 59 } 60 int main() 61 { 62     init1(); 63     ll n,k,i,m,j,kk; 64     while(~scanf("%lld%lld",&n,&k)) 65     { 66         if(n<241) 67         { 68             printf("%d\n",dp[n][k]); 69             continue; 70         } 71         n-=239; 72         ans=0; 73         memset(anss.a,0,sizeof(anss.a)); 74         for(i=0; i<MAX; i++)anss.a[i][i]=1; 75         for(kk=239; kk<478; kk++) 76         { 77             init(kk); 78             anss=multiply(origin,anss); 79             if((n%239)==(kk%239)) 80             { 81                 for(i=0; i<MAX; i++) 82                     for(j=0; j<MAX; j++) 83                         ansa.a[i][j]=anss.a[i][j]; 84             } 85         } 86         n/=239; 87         if(n) 88         { 89             for(i=0; i<MAX; i++) 90                 for(j=0; j<MAX; j++) 91                     origin.a[i][j]=anss.a[i][j]; 92             calc(n); 93             ansa=multiply(ansa,res); 94         } 95         for(j=0; j<MAX; j++) 96         { 97             ans+=(dp[238][j]*ansa.a[k][j])%mod; 98             ans%=mod; 99         }100         printf("%d\n",ans);101     }102 }
View Code

 


联系
我们