Permutations 好题

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

Sample Output

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
",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
",ans);
101     }
102 }

View Code