[TIOJ 1193] Puyo疊疊樂

作法：

原題就是要問 1~n 形成的 heap 有幾種。可以知道 1 必須當根，而左子樹就會是在剩下 n-1 個裡選 k 個出來，右子樹則是被選剩下的，再乘上子樹形成 heap 的方法數，可以得到遞回式 f(n) = sum( i = 0 ~ n-1 ) C(n-1,i) * f( i ) * f( n-1-i ) ，然後列個前幾項就會發現答案其實就是 n! XD

不過仔細想想 Treap 的性質，也就是給定 key 值和 pri 值就唯一決定了一個Treap，就可以發現一個 Heap 和 一個 1~n 的排列是一一對應的。如果給定一個 1~n 的排列，那我們考慮將他依序插入一個BST中，並且將第 i 個被插入的節點標上 i ，那麼看這顆樹加上標上的值就會發現他是一個 Heap ，而且 1~n 的一個排列只會對應到一個 Heap 。而如果給定一個 Heap ，我們可以在他的每個節點標上 1~n 的任意一個數，使得如果看這個樹加上標上的值會形成一個BST ( 不難知道這有唯一的標法 )，再來只要按照 節點的 Heap 值由小到大的順序將標上的值寫下來，就可以得到一個 1~n 的排列。所以可知 Heap 的種數和 1~n 的排列總個數一樣。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000000+10 ;
 
bool vis[maxn] ;
int p[80000],pcnt=0 ;
 
void prime()
{
    for(int i=2;i*i<maxn;i++) if(!vis[i])
        for(int j=i*i;j<maxn;j+=i) vis[j]=1 ;
    for(int i=2;i<maxn;i++) if(!vis[i])
        p[++pcnt]=i ;
}
 
int m ;
LL power(LL a,int x)
{
    if(!x) return 1LL ;
    if(x==1) return a ;
    LL tmp=power(a,x/2) ;
    if(x%2) return (tmp*tmp%m)*a%m ;
    else return (tmp*tmp)%m ;
}
 
main()
{
    prime() ;
    int n ;
    while(scanf("%d%d",&n,&m)==2 && m+n)
    {
        LL ans=1LL ;
        for(int i=1;p[i]<=n;i++)
        {
            int x=0,tmp=n ;
            while(tmp) x+=tmp/p[i] , tmp/=p[i] ;
            ans=ans*power(p[i],x)%m ;
        }
        printf("%lld\n",ans) ;
    }
}