題意

我們稱一個長度為2n的數列是有趣的，當且僅當該數列滿足以下三個條件：$我們稱一個長度為2n的數列是有趣的，當且僅當該數列滿足以下三個條件：$ (1)它是從1到2n共2n個整數的一個排列ai；$(1)它是從1到2n共2n個整數的一個排列{ai}；$ (2)所有的奇數項滿足a1<a3<…<a2n?1，所有的偶數項滿足a2<a4<…<a2n；$(2)所有的奇數項滿足a1 <nobr>(3)任意相鄰的兩項a2i?1與a2i(1≤i≤n)滿足奇數項小于偶數項，即：a2i?1&lt;a2i。</nobr><script type="math/tex" id="MathJax-Element-71"> (3)任意相鄰的兩項a2i-1與a2i(1≤i≤n)滿足奇數項小于偶數項，即：a2i-1 <nobr>現在的任務是：對于給定的n，請求出有多少個不同的長度為2n的有趣的數列。因為最后的答案可能很大，所以只要求輸出答案modP的值。</nobr><script type="math/tex" id="MathJax-Element-72"> 現在的任務是：對于給定的n，請求出有多少個不同的長度為2n的有趣的數列。因為最后的答案可能很大，所以只要求輸出答案 mod P的值。$ n≤1000000，P≤1000000000。$n≤1000000，P≤1000000000。$

分析

這么菜的題我都沒有想到。。。一頭撞死算了。 考慮每次都找最前的奇數位或最前的偶數位來放數字，但有第三個限制所以任意時刻偶數位不能多于奇數位，于是問題就變成了卡特蘭數。 直接線性篩分解質因數即可。

代碼