需要统计长度为 n、取值在 [0,m] 内的非递减序列个数,使得全部元素的按位异或恰好为 m,答案对 109+7 取模。
定义 dp[i][j][k] 表示:已经确定前 i 个位置,最后一个数恰好为 j,且前 i 个数的异或和为 k 的方案数。其中 k 只需考虑到 2m 即可。
朴素转移为
dp[i][j][k]=p=0∑jdp[i−1][p][k⊕j]实验室要为一条产线指定长度为 n 的能级序列 h1,h2,…,hn。可用的能级共有 m+1 种,编号为 0 到 m 的整数。
为了让功率只升不降,序列必须非递减,即 h1≤h2≤⋯≤hn,并且每个能级都满足 0≤hi≤m。与此同时,全部能级的按位异或必须恰好等于 m,作为出厂校验值:
h1⊕h2⊕⋯⊕hn=m其中 ⊕ 表示按位异或。请计算有多少个不同的序列满足上述全部条件。由于答案可能很大,将结果对 109+7 取模后输出。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.