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 1
5 2
3 1
10 3
Sample Output
16
88
4
131
Hint
比如对于排列1 3 2 4 5，a[2] = 3和a[5] = 5都是峰顶，因此这个排列峰顶数目为2
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
using namespace std;
#define ll long long
#define MAX 32
#define mod 239
struct matrix
{
int a[MAX][MAX];
} origin,res,anss,ansa;
matrix multiply(matrix x,matrix y)
{
matrix temp;
memset(temp.a,,sizeof(temp.a));
int i,j,k;
for(k=; k<MAX; k++)
for(i=; i<MAX; i++)
if(x.a[i][k])
for(j=; j<MAX; j++)
temp.a[i][j]+=x.a[i][k]*y.a[k][j]%mod,temp.a[i][j]%mod;
return temp;
}
void calc(ll x)
{
memset(res.a,,sizeof(res.a));
int i;
for(i=; i<MAX; i++)
res.a[i][i]=;
while(x)
{
if(x&)
res=multiply(res,origin);
origin=multiply(origin,origin);
x>>=;
}
}
void init(int x)
{
memset(origin.a,,sizeof(origin.a));
int i,j;
for(i=; i<MAX; i++)
{
j=i-;
origin.a[i][i]=*i;
origin.a[i][j]=(x-*j)%mod;
}
}
int dp[][]= {},ans;
void init1()
{
int i,j;
dp[][]=;
for(i=; i<; i++)
for(j=; j<i; j++)
dp[i][j]=((dp[i-][j]**j)%mod+(dp[i-][j-]*max(,i-*j+))%mod)%mod;
}
int main()
{
init1();
ll n,k,i,m,j,kk;
while(~scanf("%lld%lld",&n,&k))
{
if(n<)
{
printf("%d\n",dp[n][k]);
continue;
}
n-=;
ans=;
memset(anss.a,,sizeof(anss.a));
for(i=; i<MAX; i++)anss.a[i][i]=;
for(kk=; kk<; kk++)
{
init(kk);
anss=multiply(origin,anss);
if((n%)==(kk%))
{
for(i=; i<MAX; i++)
for(j=; j<MAX; j++)
ansa.a[i][j]=anss.a[i][j];
}
}
n/=;
if(n)
{
for(i=; i<MAX; i++)
for(j=; j<MAX; j++)
origin.a[i][j]=anss.a[i][j];
calc(n);
ansa=multiply(ansa,res);
}
for(j=; j<MAX; j++)
{
ans+=(dp[][j]*ansa.a[k][j])%mod;
ans%=mod;
}
printf("%d\n",ans);
}
}