[BZOJ2173]整数的lqp拆分

时间:2021-03-15 01:37:50
【题目描述】
  lqp在为出题而烦恼,他完全没有头绪,好烦啊…
  他首先想到了整数拆分。整数拆分是个很有趣的问题。给你一个正整数N,对于N的一个整数拆分就是满足任意m>0,a1 ,a2 ,a3…am>0,且a1+a2+a3+…+am=N的一个有序集合。通过长时间的研究我们发现了计算对于N的整数拆分的总数有一个很简单的递推式,但是因为这个递推式实在太简单了,如果出这样的题目,大家会对比赛毫无兴趣的。
  然后lqp又想到了斐波那契数。定义F0=0,F1=1,Fn=Fn-1+Fn-2 (n>1),Fn就是斐波那契数的第n项。但是求出第n项斐波那契数似乎也不怎么困难…
  lqp为了增加选手们比赛的欲望,于是绞尽脑汁,想出了一个有趣的整数拆分,我们暂且叫它:整数的lqp拆分。和一般的整数拆分一样,整数的lqp拆分是满足任意m>0,a1 ,a2 ,a3…am>0,且a1+a2+a3+…+am=N的一个有序集合。但是整数的lqp拆分要求的不是拆分总数,相对更加困难一些。对于每个拆分,lqp定义这个拆分的权值Fa1Fa2…Fam,他想知道对于所有的拆分,他们的权值之和是多少?简单来说,就是求

[BZOJ2173]整数的lqp拆分
  由于这个数会十分大,lqp稍稍简化了一下题目,只要输出对于N的整数lqp拆分的权值和mod 109+7输出即可。

【输入格式】
  输入的第一行包含一个整数N。
【输出格式】
  输出一个整数,为对于N的整数lqp拆分的权值和mod 109+7。
【样例输入】
3
【样例输出】
5
【样例说明】
  F0=0,F1=1,F2=1,F3=2。
  对于N=3,有这样几种lqp拆分:
  3=1+1+1, 权值是1*1*1=1。
  3=1+2,权值是1*2=2。
  3=2+1,权值是2*1=2。
  所以答案是1*1*1+1*2+2*1=5。
【数据说明】
  20%数据满足:1≤N≤25
  50%数据满足:1≤N≤1000
  100%数据满足:1≤N≤1000000
【试题来源】
  2011中国国家集训队命题答辩
 
Solution
  hta:当年LQP在集训队作业中给出了O(NlogN)的算法,需要用到生成函数并且推导较为复杂。有兴趣的同学可以参考LQP2011年的作业。
  其实打表找规律才是正解= =
  G[n]=2G[n-1]+G[n-2],G[0]=0,G[1]=1
  连矩阵快速幂都不要多良心~
  
  暴力显然有G[n]=ΣG[i]*F[n-i]+F[n],O(n^2)
  aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAA4QAAAFSCAIAAAAl1IZ3AAAgAElEQVR4nO3d25arKBCA4aylAmK//+syF9XbsT0gclTzf1czu43BArGCiB8HAAAANPJpXQAAAAB8L5JRAAAANEMyCgAAgGZIRgEAANAMySgAAACaIRkFAABAMzWS0Wm0Wqmrn9JKTdaWKA8AAABu4jwZnawdtdFKff5RwzBqI5miNePQ956Pj9qoYZjGdVr5YyettOxQK73NO6fRDn0/GnPxiPI4LR4AAADS+ZLRyVqtVNd1RutlNikjnXNuOurDfNFobbTe3XPXdXOiac3YdZ0143ZLrdTuHooKLx4AAABSHCaj1owyCPpjp90NjP4dODwaNTzKRH/stEz15q/rum53V2oYauajV4sHAACAaPvJqCSapyng5/M5ukfvuX2vle66bvvvQ98fTS3tum57o7+QiOIBAAAgzk4yOo+Jnn/4+B790X3tHzsdpbmjMUfjrDIweVqedHHFAwAAQJx1MjpZ67/5/ufDB5uNxhzljpLp7uap02j92W2Fh5miiwcAAIAI62RUnkxKnKMpzzzt/kn2v3vPXUYlj26FH909zyu6eAAAAIjwJxmdh0WPHloKISOIR8+eD33v2f/n8znKOH/vkheeORpdPAAAAET4k4yO2gTOFvWQh5+OskZJdg9Lc/zX07vknysiCnD6VwAAAFz1J7WSm9T+aZHzik5H6Z3s5PD7opNRayvcJScZBQAAqOlPaiXJVshzQvKgjwyjrp5hKjf0WCEXbF4AAACArxKZjM4bb2/H+zO2ruv82Z7n5aIVcsGU4gEAAOCqP4mXpGIhyajM4NzNzPwp4+/j6nsLQsk+PTfiKySjKcUDAADAVas5o0EvXnL/nm3fnV3qTxk9D8X/PqJ0nApXSEZTigcAAICr/uR2MhM0ZPUiNQxHSZtncNH9ew5pN4uVZ/k9q0qFjJsGOtpJSvEAAABw1f6i9/4H6mX596OUTpI2z4KgWqnd+/v+l7/LwGTiavwh4ooHAACACDsJpYx6Hq1a7/4NoGq1nxee3s6W0cfV/uXt8553kMqXll70Prp4AAAAiLA/uimTR7VS1ozLG9OTtdNoT7PVruuOUlUhud28B3mXvWeHzjmja7wOVEQUDwAAABF8sydHbbRS8oi9kFvVozH+EUp5DMj/xdNoZUqAvMj+dC5m13U1Hx66WjwAAABEKPVwet6hRBmqzLU3AAAA3ESpZHQabcb0ceh77pIDAAC8T8FlO43Wahiy7KfCQ/QAAACor+wa8kbrxOWQyEQBAABerGwy6pwbjRn6PmJJJnls37/iKQAAAB6teDLqnJusjRgf1UpVWFUUAAAADdVIRgEAAIBdJKMAAABohmQUAAAAzZCMAgAAoBmSUQAAADRDMgoAAIBmSEYBAADQDMkoAAAAmiEZBQAAQDMkowAAAGiGZBQAAADNkIwCAACgGZJRAAAANEMyCgAAgGZIRgEAANAMySgAAACaIRkFAABAMySjAAAAaIZktKDPh/ACAAD4kC0V8fmndUEAAABujWypIJJRAAAAP7Iln+XoZsRgJ8koAACAH9nSCUkolynp1c8CAADgCNmSzyoTdSSjAAAAWZEt+azuy29v2a9sP16vrAAAAA9EtuSzyiavJpckowAAAH5kSz4kowAAAEWRLR3azUSZMwoAAJAR2dKhbTJ6NRNl3XsAAAA/UiUAAAA0QzIKAACAZkhGAQAA0AzJKAAAAJohGQUAAEAzJKMAAABohmR0x9HbPqO1PiAAAICbIk/aYc1IMgoAAFABedI+o/Uym7RmvPTxydrRGJJRAAAAvxp50jRarVTcZ7VSk7V5yxMoMR91zk2jrZyMBoa6flRT2kA1DRtbLg891wAA3+w8T5qsHbXRSs1pmRqGURu5blkzDn3v+fiojRqGaYy8yE2jHfp+NCbu44mWRx2Xj0pG699m1OYTrOs6z34CQx0R1ZRmkNgGqmnV2Oo3gF1tzzUAwNfy5UmTtVqpruuM1ssrnIy+zFfHUR9evYzWRuv0UmqlsuwnghqGZR5wdehIBkdDttRKfz4fz7CW5LVHG/hDrYZBDcPmG4OimtgMcrWBElLCkl3RBnClGM3ONQDAdzrMk+QhHjUMP3ba3WC+i32Un+XNQtQwPDQfDUxGZY6pf1zqaIPTUO9mXS4gqonN4M6ZqEsISwlFG8AlDc81AMAX2s+TJMM4vSB9Pp+jm7Ont+8jdF3X5Fbvj526rlvmo0eZWQoZZfQfoFZqu0FiqD1RTWwGJdpANfUbW6sGsKvVuQYA+EI7yeg8GHb+4eObs13XRcyw9LNm9EyYK2qydpmPhgTnKtnz6TbbPDgx1EdRTW8GJdpANRGNLXAI3PPxJg1gV8NzDQDwbdYXv8la/833Px8+2Gw0ptCVrOu6Vg9YFM1HZWrpdjrgj51Ong/LEeptVNObQbk2UM3VxpaSjLZtALsanmsAgK+yvnzKvcLEGWPysMvRX6fRWjMarVdP/hqtu67zD/NopRumOKvF8DOuVSTPU2+v/daMWvnqIi7UK9uopjcDf8E8ZQtpBomiw+KXkoxWbgD3P9cAAN/jz+VzHg9LmRMpYzxHF7lptHIVXN6UXA06+havMeZ0Xl1Rq3w013Me8ozU9rjUMHjSBX+otVJD369CvWsV1fRm4C+YS24GKaLDciolGS3RAJ5+rgEAvsSfy6cMzyTegJanXvzXsOVNSbk6aqV/7CT/7rlAygZHE1U/V0Qf4PLVSlny0R877RbpNBsID7W/TldRTW8GIQVzCc0gXURYTkU3qgoNIPu5BgBALn+uf3Jz1n/5Wb2XaJvbyU783yrji3JTcjn2I//uuS8pg3bN3+WT/nKmpdVoa3jSfCHU3jpdRTW9GYQUzCU0g3QRYTkVnYzWaACPPdcAAK/350omF7+Qpxbmy6cahtXDK6dXULdYxUYrvczkJMXx53Yh+68gYz4qq50vx7d+7ORf4VxcCrV/s+Wu0ptBYB2lNINEEWE5Fd0s6zSA555rAIB3i0xG5423l/OQC9j8RauBGZnN5p+qeJ8L5HIx/JSXestRb/996Hv/0F14qE/LEJeMuoNmcOlLLzWDzxWnXx1YwnLFWB7v9t8zNoCnn2sAgBf7c6WR61NIFiLzyXYXnTm9gM2fXX3cs89L+69JIpYyhic3Q3cnL+6ucL4UGOqQO63LXaU3g5A6SmwGKeLCErJxTGHKN4B3nGsAgLdazRkNeuOOm19duDdsc3oBk+djPpvhtN/Vbc4emLjPBTJk3uEpTyRPX/V0Gorw+93LXaU3g5A6SmwGKeLCErJxRGGKNoDXnGsAgBf7c6WR7CrkKeajlWjcPEft+La1fHab6wx9f7TPPyU+HtP6XHF2iCfCR9f8Aicv+j57HOrfkIYtXD8fS3ozOC2YS24GKeLCErJxRGGKNoBy5xoAALnsL3rvHzI5WolGyKCL5zonn10N+cjNytMESFLAXKt7RpMlcrK8hCkw7dvlD3VgSN1eVBObwWkbcGnNIEVKWPziktFyDcC94lwDALzezuVTRlM8NzH9i8L8Lk94MOPw6LPzv0+j9QzGyGbNF+KWVdNTHloSiWsYBYbaH1J3ENWUZuAvmOez4WWOlhgWj4hktE4DOPr3R5xrAIDX2798yqxBrZQ143JYZbJ2Gu1pmiILa+/+6Wi63vz+Sf+FWV5j6NmggpT7qkvyghyJc/S7jjyhnqd+aqX8efNRVFOagadgLrkZpEgPy5GryWjpBvCCcw0A8A0OL5+TtaM2WqnlywOHvtdKjcb4UzF5JmP3T0fT9eTCeXpPsOu6wCWHCsmyBKYMaK3EDQR6Qi33cOV1O/6deKIa3Qw8BXPJzSBFlrDsCk9G6zSAp59rAIAvUepR2a7rsi9abs3YdqhGblzebRZdYqjLRbVEG6imeWML98pzDQDwPUolo3ILMu8+h75vmNyEvM28icRQl4tqiTZQTdvGdsn7zjUAwFcpuIig0Tpj6ma0bjgkKY/PF12JPUV0qEtHNW8bqKZtY4vwpnMNAPBtyq5oLY+JZNlP26ujGobox+dlCaTsRVqJCHWdqOZqA9U0b2xxXnOuAQC+TfEkaTRm6PvoZ8/lqe2i7+M5Jc9fRx+CNWOd0cHwUFeOamIbqOYOjS3FC841AMAXqvGuv8nGrxl5+nru0n5fnJjwWLE8e56xSB6Boa4f1ZQ2UE3zxpbu0ecaAOA78eJpn/TH5yusVQQAAPBcJKOH5K2JcXfYJ2utGWWhx8SBVQAAgBcjGT20XOY9EavkAAAA7CIZ3SfvusyFqXgAAAC7SEZ3yETPnMlo1JpQAAAAr0cyCgAAgGZIRgEAANAMySgAAACaIRkFAABAMySjAAAAaIZkFAAAAM2QjIb6fC7E6tLGAAAAX4ucKbN5bdHWBQEAAHgAcqYiSEYBAABCkDOdixjpJBkFAAAIQc4UhGQUAACgBHKmc8vM8ujt856PAAAA4Ag507mIzJJkFAAAIAQ50zmSUQAAgELImc5xmx4AAKAQcqYTklbyABMAAEAJ5Ewn4tZ1Yt17AACAECRMAAAAaIZkFAAAAM2QjAIAAKAZklEAAAA0QzIKAACAZkhGAQAA0AzJKAAAAJohGQUAAEAzJKMAAABohmQUAAAAzZCMAgAAoBmSUQAAADRDMgoAAIBmSEYBAADQDMkoAAAAmiEZBQAAQDMkowAAAGjm1sno53Pr4gEAACDRTbO9zz+tCwIAAICCbp3tkYwCAAC8W9lsbzm6GTHYSTIKAADwbsWzPUkolynp1c8CAADgrYqPjLq/OSXJKAAAAGb1btO7TVa6a/XxosUDAABAWzVGRo/+9+rHAQAA8DIkowAAAGimYLa3m4kyZxQAAACzqsno1UyUde8BAADejVQPAAAAzZCMAgAAoBmSUQAAADRDMgoAAIBmSEYBAADQDMkoAAAAmimSjB696jNaiUICAACguSJ5njUjySgAAABOlcrzjNbLbNKa8dLHJ2tHY0hGAQAA3q1gnpeYjzrnptFeSkan0Wqlrn7LpfIU3X8crdRkbetSJLlnYJf8Qa5fBfePmHt+y3xEkAWhroZQN/H0sONU2UFHrVRiPioZbciWozZqGKZxp72O2nyCdV13df+l/dhpGu2ojcRz9ddptEPfj8ZULlWWqLqmgXW/XbPuuk4KqZXeLYk/yBFVMNn/K1SoYRi1kQ7XmnHo+6PPto1YuFYt8/8CvCXI/h7ANQr1O3qAFUJdX0gn3LwzQWnF74CrYVieJFd/3Mjg6OlmRmujtX8brfTn8/H8KJTEd3cD//7VMKhhOC1kNK2UdCISxqNtTiNQQkpUXevAHk1uPiqSP8iBVTBZq5Xqus7oP32ujFjMZRj1frcb0tSbOKqsJi3zZUEO6QFco1AX7QHqI9SVXeqEW13mUEGN6ZiJ+ehpMhp4jskkVP9Pq90NTvdfOmea+ftHNQz1T9ToqLrWgf2x0+fz0UrPDXIa7dxWj0bx/UE+rQLpedUw/Nhpd4N5csvuaXLPy4nwVFbllvniIPt7ANeiEyjaAzREqCuI6ISbXOZQQY1k9MdOMgI/56NHF4kI/nttSzIi4r9DoZVabRC+/wpO+8eu6yrfgomLqrtBYI3Wu52dHJGnbP4ge/4qOdBpT3r07c0jlqJay3x3kE97AFe9E3huD+BHqCuI64TrX+ZQQaUH1Sdrl/loxuGurusCp6KGdC6fz2eVKIfvv4LTQ7Bm9EwYOtpn0SK5vai6GwRWq/18ZbInj835g3z013m47rRgn4Pbx80jlqJOy3x9kENOt8qdwHN7AD9CXUFcJxwRdtxfvVWTSuSjozGBjVLmnm4n0/zYyfcQQ/D+6wj8sX5plndK5xgXVXe/wK58vA8BuLMgb/86960hc1R2N7t5xEKUbpnfEOSQHsBV7ATe2gM4Qt2avxO+GnbcX9UlPFdTldMXmJAHFEK2lKcRt83XmvHox9np/qfRWjMaras9nxjSP8pjiZf2GV2euKi6+wV25fQ+rz/I27/KXaeUqU5xETNad11XdFwkvLJKt8zSQXZN4ywCM6RqnUChHsAR6o0Xh3qX/1y+GnbcX+315Ff5aMqVQ34pBp4nMid6e7FUw3C0B//+tVJD389jvZdKHi3ku2SSe3gOl1L4iKi6WwZ2SYrnD6A/yKu/ziN20VOl/RGbRivXjGXEVjciCnXclyqraMssHWTXNM6zwJOiWidQogdwhHrPi0O9Wyp/VK+GHff358T4XBH9lctXK30S8lF5UiGkOcoje9sy+xt0yP7lnKnzKL0L6x+lSEdr1uzuM64wcVF1twzsktH6dMzeH+TVX2VII+VYwiMmJZdriVZaFk0sfTkJrKyiLbNOkF3TOLvgDKlOJ1C0B3CEeuHdod467YSvhh331+ZNm+kvZ3L/7sqFbHm0kpm/uwnZv+y52ikRlIza/alFnn3GFSYuqu6WgZ1Jp3866dAf5NVf5Xj9x7I6I1ZhvBAxY9zfwRL5d/+NvESBlVW0ZdYJsmsaZxeeIVXpBIr2AI5QL7w71CshnfDVsOP+mr32PT0fDews3L+1gpe/Dn/s5F8fOHD/IWttZBR4yOGRcQnJaFxUA4tXObCL79WB8+L9R7H8q/x3yG7nS44ahmVffCliWv1ZLUVqpOisr/DKKtcy6wTZNY2zuxLACp1A0R7AEeqFd4d6U5igTvhS2HF/LetyuRh+xGtnw9uiTH/Z/vvQ956hlJD9h28TKP3rPJtlLImLjWrgUZxuk/dYhDVj+H1e/56Xf5X/vpTjrhK78IiNxqyGMaSajmZSZgljeJCPtkwvRp0gu6g4ZwnypUJ6tsxYmKI9gCPUm0Pe/vs7Qr0U3glf3TNurnFdSluP++EV2BZlPP/oRYWe4ZzT/R+ttVHOpZ4lfJ8RJYmOakjx6gfWOTdZe2ldaP9RLP8qjTwkT5ID3xYjMGJD368+e7TDjC5VVrmWWSHIrmmcRXgAS3cCRXsAR6gXXh/q/7/xSidMMvoyLesycV5gYFv8fYXawQLXnmdvT/df/xbGfZLR6KiGFK/JvaGh7y8Nz4cno3KL7cIbazdRPY2YPL7z2Yz2/S4HU3Lq7aXKKtcyKwTZNY2zuE+GVLQHcIR64fWhnl3qhElGX+ZPXX6uSPzi9NGv32kuZ203evbh6f6Hvg8pQEaBkb8U2LiqTJnTecPA+pdH2eUP8vKv8qMr5InUo9VbTiMmH9ymYr+RLDn19lJllWuZFYLsmsZZXMqQinYCRXsAR6gXXh/quRiXOuHE/AF30+aHhSwekbhwj/xuOz1VAi9RV/cvt04qr3kR0j9Klh++YFZcMppy7HcL7FEneLp631GQt38Nedb7aPUWF9DU5YOrMZIKkbz0FaVbZukgu3ZxXhXgdLMKnUC5HmDeP6GeP/LuULvrnfDVsOP+2iSjslB24tDX70pj3lliKStT+Pc/73kabbXfZyH9oxSs6CLMiet93Cqwu53gNFo1DJ6ezh/k3b/K8IMnwfVENTBiR/9eLpKXvqJCyywXZM9na7bYwAypdKiL9gCe/RPqqx4R6ohO+GrYcX8NktGMq/bI2rxHf5V3S8hgftx7WTz7n+eoaaXq3FCWbuU0dPIOt/DdXu0c06PqbhPY5XoOW/6lpD1BPvqrHJpWyppxGbrJWul5PYmUJ2JHszbn12OWWybwUmWVbpnLImUPsmsaZxHYA7jCoS7dAzhCvSjG60Md1wlfDTvur3YymvfZFJnZvf33uStZivh5d7R/9+/2h7ym4nK5r9seztGWXdcFLnAz7zlwy1xRdfcIrL8T9D/U6Q+y56+TtaM2Wqnl2/aGvtdKjcZ4rnyeiB3N2pRzreidrEuVVa5lrpQIsmsaZ3elB3DFQl2nB3CE+mtCHd0JXw077q9qMipD63nbd9d1RR+7Lr3/vKwZn/J78VmBXfIHuVwVPDdi7jkt89FBFoS6GkLdxFPCjkvqJaOF3jYuNzLy7rPm/vMa+v4pnc6zArvkD3K5KnhuxNxzWuajgywIdTWEuomnhB2XVEpG5fH5QsvnGq2z57g195+L0fpZTxc+JbBL/iCXroInRsw9rWU+NMiCUFdDqJt4VtgRrlIyqoYh+vF5WY3Fv408QhFVtCCl95/uoafo/QO71DYTnb/lQRFzz2yZj*NTVEOomnhh2BKqRjMrzrdGPzwe+rHY0Zuj7cms9lN5/NHlGuOZ7MvK6bWCX/EGuXAWPiJh7eMt8SpAFoa6GUDfx6LAjRPFk9PeVYgkPvsljsCFbTrbsimil9x/n9PXE93fPwC75g1y/Cu4fMff8lvmIIAtCXQ2hbuLpYcepsslo+uPzdRaYAAAAQBMFk1F5n1jcpOnJWmtGWQItcWAVAAAAt1UwGV2uOJ2IdRwAAABeqVQy6n+zwlVMFgEAAHilIsmoTPTMmYxWefk7AAAAKqv9bnoAAABgRjIKAACAZkhGAQAA0AzJKAAAAJohGQUAAEAzJKMAAABoplIy+vmEftFyRaeiRQIAAEBz90r4lgko+SgAAMDr3SvbW2WfJKMAAADvVjzbSxngJBkFAAB4txrZXlxOSSYKAADwejVGRpf/vev0gwAAAHilqslo6U8BAADgWe6YjJKJAgAAfInb3aYnEwUAAPgeZTM/ySwvrXh/+i8AAAB4jeLJ6KVsMvDZJgAAALwD2R4AAACaIRkFAABAMySjAAAAaIZkFAAAAM2QjAIAAKAZklEAAAA0QzIKAACAZkhGAQAA0AzJKAAAAJohGQUAAEAzJKMAAABohmQUAAAAzZCMAgAAoBmSUQAAADRDMgoAAIBmSEYBAADQDMkoAAAAmnlkMvpZaF0WAF+EzgcAsntef7q8BnBJAFANnQ8AlPC8znR1AeB6AKAJOh8AyKJZZ7ocV0i57cX1AMAlWTofeh4AyKVlfyq9+fKqELcHALgksfOh5wGAjFqOjLrNHKy4nQBAuMTOhweYACCvW9ymd3+HKHbt7qFSWQG8SHrns90JACBa45HRo/+9+nEACJTrIUh6IQDI4pHJKNcAANFIRgHgVtp0prsXg8CefbsZlwQAgVI6H89+AADR7pKMhvfsgTO6AGArV+dToGgA8KXoUgEAANAMySgAAACaIRkFAABAMySjAAAAaIZkFAAAAM2QjAIAAKCZZks75dXkKAA8Cz0PANxQm87UmpFLAoDK6HkA4IaadaZG62Wfbs146eOTtaMxXBIAXELPAwB3U6kznUarlVr9Y+JVQXZb85KwexS7tFKTtaXLsxReti9Rvwqye0qd+kPdtiLe0fO44MZAz3M3dESt3LlfSvegSgkMdY3OdNRGDcM07pRGK5V4VZDrymkBwu+7dV139Si2ptEOfT8aE3gUk7WjNstoqGEYtZEqtGYc+t5/gOFle4cfO03j/0HbbnC1CnLJ0tjcneo0MdStKsK9pefxH8hKRLRTOp/7tNL6ptFqpbuuk7rTSu/GgY4ouyyRb9gv/RbgLeddrmtx8WTUaG209myghmF5Slz9sSJDFCFbaqU/n4/nx4RcXXY38B+FGgY1DHvfqPzH7pybrNVKdV1n9J8zSn73zJEZ9WFFnka4laOwZKGVkhNS4uPZrElwUhqbu1mdZgl1/Yp4R8/jojqfwGgndj63aqUrRTsfdzz5+CggdES55I18k3p52XmX61pcNhkNjFriVSHwkiAzvfzp+e4GIVe1o45PDYPns3JeqWH4sdPuBvP9xKOY3K1dLpW+Hgj/CeDOqqCQ6MbmblyniaGuWRHv6HlcQudzGu3Ezue2rVQU7Xx+7PT5fLTSc2Sm0c5t6WiUnY4oXYnIV66XF593iReIgsno6c3l2Y+dZMh9vioc1VMK+c3hH9nWSq02CD+KI13X7X6ptLnThvX5fI4KkF62Fzg9AdxxFZQT19jcves0PdR1KuIdPY9LbgyeaCd2PndupRUYrXfzHqloT2ToiBIViny1enn3eZd4gSiYjHZdFz4Ta7J2eVUo8aM2JFKfz2d1Nbp0FLusGbczcuafR6cf9wzXp5ftBUKqdbcKTnebUKjIxubuXafpoa5TEe/oeVxyYziKdnrnc+dWWoFW+8nEZE8ea6MjSlQo8nXq5fXnXeIFolQyOhpztXaLXhVkgtd2ZsyPnXzThK8fxa6u65b3QeYzJ+gRs4PNcpXt6UJOALepgpDdRhcprrG529dpllCXroh39DwuU2PYRju987l5K23r430YyNERFZMY+dL18g3nXeIFolQyKpNzr35qNTc548oF8mjhNgTWjEc/ttzZUUyjtWY0Wp8+1yaP/i3+V30Cxur94spmtO66rugPrPCwZBF4AqyqIGS30UWKa2zuxnUqsoS6dEW8o+dxmTqfbbTTO587t9LKnc/WaWzpiApJjHzpeil93rkb1EviBaJIMio/yOKOfHVVyDVXV+Y4b7snNQxH5fQfhVZq6Pt5QMX/7TKLXL59/oWUMjvNX7ZptNL4lmVbDf8U+o11KSxZBH7RsgoCdxtdpIjG5m5cp7MsoS5aEe/oeVy+zmcV7fTO586ttH7nsyLB8bdtOqIS0iNftl8qfN65e9RL4gXizyc/V3i+TGbpRv8wXb7gJMtVQR7B25bZ3/5CjkKayOl9PdlMZoHIr9XEW4HhZZMxHmmUWmlZEqx0uwwMSxaBJ8CyCgJ3G1eeuMbmbl+nLlOoi1bEO3oel6/zWUU7vfO5fyut2fmsGK1Px9TpiEpIj3zReqlz3rnW9ZJ4gSjy8/Fo7dNw6a9IWfK/kProUyFHIXs+bcHyw0iaiOzW/5HV4W+LeqFsxri/P4Xl3/23aRIFhiWL0BNgUQWBu40rT1xjc7evU5cp1EUr4h09j8vX+ayind753L+V1ux8liT5O50RSEeUXZbIV+iXSp93rnW9JF4giiSjgWXyy3hVkIV/l78qfuzkX+zXhR1FyMIZq73Jf4TMlZ57EzUMqzPtUtm0+rMchhx40d/ryIAAAAy6SURBVOkj4WFJF97YLjXL6AYc19gCi9ewTgNLGLJluYp4R8/jsnY+y12ldz73b6U1O5+/36sDn4ChI8orV+RL90ulzzvXul4SLxD3TUbd3yWpU14jK9Mmtv8+9L3nx0rIUUREP7xdzhvvzK4ILttozOr3kETjaPLK54rTgz0tXuIXBX6Xf8tcJRFxjS3wQGSbJnUaWMKQLctVRHgJ/dr2PC5r57PcbG4/p59yB51PeMFu20pzfdGSNWP4TdijPect2Is7oqUskff/Nb3Yc7jCCxlx3rmoeslYKeEVt7vlrZNR9y+IKRm9jAkfva7T8wP69CiOFs7w702OKKRdyv531+AILNvQ96uPe/aZy6WwpEs8ATwbRxQmurGFFK9hnYpcoS5XEe/oeVzWzme5q/TO5+attHLn8/ul1l46LjqiXPJGvly9VDjv3A3q5c3JaJbZP7/vQztYQtbzdNvpUVwa+p73JndPQp6N8JT8tGwyY/qz+YH1u9hHyQlVle/U3CoZjW5sIcVrWKfie5LRtj2Py9r5LHeV3vncvJU2uU089P2l4XM6olzyRr5cvVQ479wN6iXxAvHZbhHI802/ExcSbm+5fL9xo6cQnR7F0Pfhhzkfi1znQp5rO1qYI6Rs8tlt6/8tc8kJVZfCku7SCVD6uYGU+Wp3rlORK9TlKuIdPY/L2vksjyW987l5K63c+bizZZJ20RFlkT3y5eqlwnnnblAviReIIiOjkomnHLysSpBleY7ARrDlPwq5DxK4Z7m8za0k5Nm6o4U5Qsrm/jWL1S/gS2WOU+ErVgJPgFUVhOw2rjDRx37bOl0V4HQzf6iLVsQ7eh6Xr/PZRjux87lzK63f+RzlQ6ereNIRJcoe+dL1Uvq8czeol8QLRJFk9HcdqSsv11qRtYvTf+CmrGjgP4p5z9NoT39OycbLliQ/Yjxnjr/kgWVLKXOcCl+xEngCbKvgdLdXS5K4fMZt63SWJdRFK+IdPY/L1/nsRjul87lzK63c+ezmQ9No1TB4cho6onQlIl+hXsqdd57PPugCUSQZdc7Jaqtxn821Nsc0/r5+QCsV9+YDz1HMs0C0UqeXLnkf1+4etFLWjMviTdbKeeVvuJ6yHU2cmt9IVm69sUthSSenaEhr2a0Cj6t9TXpjc3etU5Er1KUr4h09j8vU+RxFO6XzuW0rrdn5LNdb2PIvKU9HlKJQ5EvXiyh03rkb1Ev6BaJUMirzcCM+mGUG+hyXpYifBZ6jkGFzeb3B6X66rtv9TTNZO2qjlVq+s2voe63UaIy/Uj1lO5o4JbHN9Z7D/VJdCUuibRV7Nj6qAs/OA7fM1djcXevUZQ11uYoQ7+h5XKbOxxPt6M7ntq20Wufjz4f8jy3TEaUoF/nS/dKsxHnnWtfLti48Gx+FulQyKl95tWeX8dvSgbsk4ihWrBkLzdhIL9uXKFcF2T29Tv2hrlMR7+h5XHJjoOe5GzqiVu7QL6V7QaV4Ql0wGZX7BZe2/zR6p7DH1aPYGvq+UANKL9uXKFcF2T29Tv2hrlMR7+h5XHJjoOe5GzqiVu7QL6V7QaV4Ql0wGXXOGa0Du3h5iLXmernhwo9i97NFh1tSyvYlSldBds+tU3+oa1bEO3oel9AY6Hnuho6olfv0S+keXSn+UJdNRuXrQ6atqGGIfohVFkSI+GC4wKPYfqpCK48r25d4Vkcze2Kd3q3Hf0fP46IaAz3P3dARtXK3findQyvlNNTFe1Ln3GjM0PeembnyiFn0Q6yX3k4b7fQoluTJuGrvorhUti9RuQqye1Cd+kPdsCLe0fO4K42Bnudu6IhauW2/lO5ZlRIY6hrJqHNusodrXP2+qyptacA6PxQ8R7Fy+v7f7MLL9iXqV0F2T6lTf6jbVsQ7eh4X3Bjoee6GjqiVO/dL6R5UKYGhrpSMHkl/iLXOygUA3oSeBwDuo2UyKi+qirvPNVlrzShrayUObwD4KvQ8AHArLZPR5aKviR6xLgOAO6DnAYBbaZaM+l+lcNWjJ38AqIaeBwDupk0yKtOtcl4Syr8GHcDT0fMAwA01foAJAAAA34xkFAAAAM2QjAIAAKAZklEAAAA0QzIKAACAZkhGAQAA0MyNktHPJ7Qw4VsCgN+l/oTOBwCye1jHOi/v17ogAL4LnQ8AFPLIjpXrAYAm6HwAILtbdKxXxxu4HgBIFzHSSecDANndpWMlGQVQH8koADR3i4512b8fvQP6aHsAiHO153F0PgBQwC06VgYnANQX0ZPQ+QBAdrfoWElGAdRHMgoAd3CLjpXb9ADq4zY9ANxB+45VOnceYAJQU0TPE7E9AOBU+441Yl2niAVZAGApohuh8wGAEuhVAQAA0AzJKAAAAJohGQUAAEAzJKMAAABohmQUAAAAzZCMAgAAoBmSUQAAADRDMgoAAIBmSEYBAADQDMkoAAAAmiEZBQAAQDMkowAAAGiGZBQAAADNkIwCAACgGZJRAAAANEMyCgAAgGZIRgEAANDMO5PRabRaqdalOKeVmqxtXYp4T4nz1tMjDwDAaxRMRqfRaqW7rvt8Pl3XaaWnMfTyP1k7aqOV+vyjhmHURhIIa8ah748+O2qjhiH8u4r6sdM0/n8sq79Oox36fjSmSdnci+I8C2x1zSMPAABEqWTUmvGzx2jt/+BkrVaq6zqj/6QRMgg372fU+2mE0fr0K2rSSknSJsU+2qZ+mV8WZ3G11TWJPAAAWCqSjP7Y6fP5aKXnO6HTaOeEzJrx6IOSTKhh+LHT7gZGa9nJ7j3We2ZIwpOMOufUMNQs+SvjHNfqKkceAACsFElGjda7134Zcju68ysJ0GlmcLQH/z3l5vzJqHOu67o6t7zfGue4VucqRh4AAGwVSUa12k90JmuPcrJ5rO5050f3jruu84y5NneajFozdl13dZ9Xi/HiOEe0OhEReQAAkEvtp+nlsZLVP87pQsgDzrubjcbcPJ84TUadc13XXXqk5moy+g1x3rXb6pauRh4AAOTSIBnd3iCWG6kpU/fkQZyjv06jtWY0Wq+e/jZad11XZ6gvJBmVx8Av7fNSGUrH2d0j1FunR3018gAAIJeqyeg02s/ns5qfNw/XHT1ME7jboyxnGq2kQct0cLJ2/pfTYbMsQpLR0ZhtfPz7DC9A6Ti724R6W6rTqF6NPAAAyOVPNvO5IuLLjNbbNdJHbQJnMXp2e5pJSEYi3y7pkVZaFgG9TzIqhTlaTWl3n+EFqBNnd4NQr+y2upWrkQcAALnUGxmVlXe20xDl3rE/D5hXGtpNiHfXk1+RB3dkXqAahnl4T/796NmXjIKSUft/Ghe4z/AC1Imzu0Gol45a3crVyAMAgFzqJaNa6d1nRCTdCXl8ZF7SXA3DMr0IyfMkkZLX8yxvNEv6dZM5o+GbzRtfLUDpOLsbhPpvYfZb3Vb0eD8AAEhR6eprzXh0gzg8SZo3Xt0pDkkj5m9ZjczJdMajaZS7w4RHQgoQeIAlSlInzi4q1BnjvORpdUdlCN85AADIosbVd7LWv+R4YJIkE/u2uzpNI+YPrj57tMMSEpPRo43DC1Ahzu4eof79Rm+r2yIZBQCgiRpX36HvPZP2tAp6IZD798jzdtbjaRohz+5sh/rk3+s8ttI8Ga0QZ3ePUAt/q9siGQUAoIniT9MvH2HZJTMUQx6ylveMb5/m/p2keJx5yAe3edjQ97s7LCE8GS30AFOFOLt7hNoFtLqtS5EHAAC5lB0KOsoJVv8Y8qC3PBa9m37JqJsn0ZEPrmYrygPU1VYaCr/HHb4o/dWRvNJxdvcIdWCrW7oaeQAAkEvBZHQ3J5hGq4Zhe9WXETVPuuBZGOh3kciD2ZBHH5z/fRpthSGxkGRUilRo0XtRLs6ez9YM9aVWtyohi94DAFBfqWRUkp4ju1d9mdSolbJmXA6tTdZKMuHJomRl9d0/Ha0oNL8bs8LKl5LGnaY78s7M8N1GJKOuWJzdDUId0ermkvM6UAAAmiiSjPpzAs8zzpO1ozZaqeULJIe+10qNxniSCXnmZvdPv7MVNzMdJXOqcGd2G4GjLbuuC1x6ad5zXJFKxNm1DnV0q3PXIw8AAHJ5z+PDXddVXlA9L2vGRwzOPT3OW0+JPAAAr/SeZHQa7aNTiqHvH5HkPT3OW0+JPAAAr/SeZNQ5Z7QOf+POrRitH/Qo93PjvPWsyAMA8D6vSkadc0brx60W+cR86Ilx3npi5AEAeJm3JaPOudGYoe8fsUyPPL1e871EGT0ozluPjjwAAG/ywmTUOTfZGkuHptNKPTSZE0+J89bTIw8AwGu8MxkFAADAI5CMAgAAoBmSUQAAADRDMgoAAIBmSEYBAADQDMkoAAAAmvkP2ciWXQumx9UAAAAASUVORK5CYII=" alt="" />
  《论出题人犯逗的危害》233
 
 #include<cstdio>
int n;long long mod=1e9+,g[];
int main()
{
scanf("%d",&n);g[]=;
for(int i=;i<=n;i++)g[i]=(*g[i-]+g[i-])%mod;
printf("%lld\n",g[n]);
}

[BZOJ2173]整数的lqp拆分的更多相关文章

  1. BZOJ2173 整数的lqp拆分(生成函数)

    首先有序整数拆分有个显然的递推式是g(n)=Σg(i) (i=0~n-1),即枚举加入最后一个数之前和是多少.(虽然不用递推式也能显然地知道答案是2n-1). 类似地,lqp拆分有递推式f(n)=Σf ...

  2. 打表&bsol;数学【bzoj2173】&colon; 整数的lqp拆分

    2173: 整数的lqp拆分 Description lqp在为出题而烦恼,他完全没有头绪,好烦啊- 他首先想到了整数拆分.整数拆分是个很有趣的问题.给你一个正整数N,对于N的一个整数拆分就是满足任意 ...

  3. BZOJ 2173&colon; 整数的lqp拆分&lpar; dp &rpar;

    靠着暴力+直觉搞出递推式 f(n) = ∑F(i)f(n-i) (1≤i≤n) (直接想大概也不会很复杂吧...). f(0)=0 感受一下这个递推式...因为和斐波那契有关..我们算一下f(n)+f ...

  4. BZOJ 2173 luoguo P4451 &lbrack;国家集训队&rsqb;整数的lqp拆分

    整数的lqp拆分 [问题描述] lqp在为出题而烦恼,他完全没有头绪,好烦啊… 他首先想到了整数拆分.整数拆分是个很有趣的问题.给你一个正整数N,对于N的一个整数拆分就是满足任意m>0,a1 , ...

  5. 整数的lqp拆分

    题目大意 lqp在为出题而烦恼,他完全没有头绪,好烦啊… 他首先想到了整数拆分.整数拆分是个很有趣的问题.给你一个正整数N,对于N的一个整数拆分就是满足任意m>0,a1 ,a2 ,a3…am&g ...

  6. &lbrack;国家集训队&rsqb;整数的lqp拆分

    我们的目标是求$\sum\prod_{i=1}^m F_{a_i}$ 设$f(i) = \sum\prod_{j=1}^i F_{a_j}$那么$f(i - 1) = \sum\prod_{j=1}^ ...

  7. BZOJ 2173 整数的lqp拆分

    题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2173 题意:给出输出n.设一种拆分为n=x1+x2+x3,那么这种拆分的价值为F(x1) ...

  8. 洛谷P4451 &lbrack;国家集训队&rsqb;整数的lqp拆分 &lbrack;生成函数&rsqb;

    传送门 题意简述:语文不好不会写,自己看吧 思路如此精妙,代码如此简洁,实是锻炼思维水经验之好题 这种题当然是一眼DP啦. 设\(dp_n\)为把\(n\)拆分后的答案.为了方便我们设\(dp_0=1 ...

  9. Luogu4451 &lbrack;国家集训队&rsqb;整数的lqp拆分

    题目链接:洛谷 题目大意:求对于所有$n$的拆分$a_i$,使得$\sum_{i=1}^ma_i=n$,$\prod_{i=1}^mf_{a_i}$之和.其中$f_i$为斐波那契数列的第$i$项. 数 ...

随机推荐

  1. python &quot&semi;yield&quot&semi;&lpar;转载&rpar;

    转载地址:http://www.ibm.com/developerworks/cn/opensource/os-cn-python-yield/ 您可能听说过,带有 yield 的函数在 Python ...

  2. delphi提示&OpenCurlyDoubleQuote;Undeclared&lowbar;identifier”的缺少引用单元列表

    _Stream ADODB_TLB akTop, akLeft, akRight, akBottom Controls Application (the variable not a type) Fo ...

  3. UI2&lowbar;UITextField

    // // ViewController.h // UI2_UITextField // // Created by zhangxueming on 15/7/2. // Copyright (c) ...

  4. 基于jquery中children&lpar;&rpar;与find&lpar;&rpar;的区别介绍

    本篇文章介绍了,基于jquery中children()与find()的区别,需要的朋友参考下 .children(selector) 方法是返回匹配元素集合中每个元素的所有子元素(仅儿子辈).参数可选 ...

  5. POJ1811- Prime Test&lpar;Miller&ndash&semi;Rabin&plus;Pollard's rho&rpar;

    题目大意 给你一个非常大的整数,判断它是不是素数,如果不是则输出它的最小的因子 题解 看了一整天<初等数论及其应用>相关部分,终于把Miller–Rabin和Pollard's rho这两 ...

  6. js中的屏蔽

    js屏蔽效果 /** 屏蔽F1帮助 */  window.onhelp = function(){return false;}     /**  *屏蔽 F5.Ctrl+N.Shift+F10.Alt ...

  7. Tyvj P3276

    题目链接:http://www.tyvj.cn/p/3276 这题是一个动归题,一直没有想出动归的做法,后来求教别人之后写了一个记忆化搜索,只有出题者又给我提供了DP的解法,下面我来写写DP的写法 设 ...

  8. PyQt5实时汇率查询

    用PyQt5实现了界面,使用urllib实时抓取ip138.com网站的汇率信息. import sys import urllib import urllib.request from PyQt5. ...

  9. radiobutton独特属性

    radiobutton是通过name来分组的,也就是说,使用相同的名字的radio,它们才是单选的,如果名字不同的radio,是不具备这个效果的,这个是第一要点. 第二,针对不同的radio(name ...

  10. map基本方法

    添加功能: V put(K key, V value)  添加和修改 ,添加时返回null,修改时返回被修改的值   Map<String,String> map = new HashMa ...