1Description http://uoj.ac/problem/300 2Solution 2.1 根据Lucas定理，(nm)mod2=1(nm)mod2=1的充要条件是n and m=mn and m=m。发现很好DP，设fifi表示以ii结尾的序列方案数，每次加入、转移即可。 2.2 考虑优化。用fi,jfi,j表示所有结尾的数的前99位以ii为子集、后99位为jj的方案数。每次加入一个数xx时，答案加上Δ=Δ=所有的fx的前9位,jfx的前9位,j（满足xx的后99位为jj的子集）然后将所有的fi,x的后9位fi,x的后9位加上ΔΔ即可...