題意

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

分析

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

代碼