题目大意：定义一个数是完美的，当且仅当这个数的每一位可以分成两个集合，使这两个集合之和相等，求[a,b]区间内有多少个数是完美的
数位DP？……不大好搞
分块打表大法好！
首先考虑验证一个数是不是完美的怎么搞
求出数字和 如果是奇数肯定不是 如果是偶数就跑一下背包
背包很慢？没关系，由于最大的和只能有9*8/2=36 所以我们直接状压 令f=1 然后对于每一位x有
f|=f<
最后返回f&(1<
但是这数据范围是10^9诶！总不能交一个这种数据范围的表吧！
没关系，我们将数字分为1000块，对于每块求一个和，这样打出大小为1000的表是可以交上去的，零碎部分大小为10^9/1000=10^6，直接暴力
真是好方法……get了
#include#include #include #include #define Block 1000000 using namespace std; const int table[]={0,376413,832547,1288828,1744956,2196800,2647716,3090920,3526440,3951372,4366880,4823015,5304766,5797144,6290672,6782004,7272530,7758910,8238396,8710536,9182258,9638539,10130918,10610575,11103529,11590745,12080513,12565094,13045216,13523103,13996047,14452175,14945703,15438658,15913605,16403907,16892727,17371943,17858307,18339125,18810719,19262563,19753895,20241111,20731414,21199399,21684697,22170473,22655525,23128982,23601310,24052226,24542752,25032520,25521340,26006639,26480512,26967738,27450344,27929454,28401296,28844500,29330880,29815461,30294677,30780453,31267680,31727883,32207445,32681531,33151141,33586661,34066147,34546269,35032633,35517685,36000291,36479854,36928875,37398605,37865237,38290169,38762309,39240196,39721014,40194471,40673581,41147667,41617398,42050819,42514127,42929635,43401357,43874301,44345895,44818223,45290065,45759675,46226307,46689616,47111407,47567542,48049293,48541671,49035199,49526531,50017057,50503437,50982923,51455063,51926786,52408537,52900916,53398017,53897101,54395976,54894264,55390376,55882154,56370124,56858336,57350715,57847816,58346901,58846682,59346650,59846494,60345546,60842736,61337762,61832643,62326171,62825256,63325037,63822618,64321881,64821477,65319367,65818159,66315614,66811192,67302524,67801399,68301368,68800631,69295186,69792675,70292149,70790949,71286703,71781713,72272239,72770527,73270371,73769968,74267457,74763402,75261351,75759527,76256605,76751555,77237935,77734047,78233099,78730989,79230464,79728413,80220834,80714563,81209373,81704149,82183635,82675413,83172603,83671395,84170195,84668372,85162101,85646750,86134011,86626601,87098741,87586711,88081737,88579192,89074946,89572024,90066835,90554096,91029271,91513942,91985664,92473876,92968757,93464335,93959345,94454295,94949071,95441662,95926333,96400455,96856736,97349115,97828772,98321726,98808942,99298710,99783291,100263413,100741300,101214244,101706623,102203724,102702809,103202590,103702558,104202402,104701454,105198644,105693670,106188552,106668209,107167293,107654509,108153408,108643571,109140447,109631936,110124934,110615086,111104170,111597125,112096906,112595804,113093027,113592810,114091415,114589181,115087418,115585176,116080738,116567954,117067923,117558086,118057868,118549357,119048442,119540443,120037757,120529913,121025141,121514909,122014753,122511630,123010235,123509319,124005151,124504320,124999107,125496723,125991518,126476099,126975151,127466640,127964407,128456408,128955576,129444361,129941988,130432181,130927549,131407671,131904861,132397859,132896096,133393411,133888198,134385824,134870790,135365761,135853348,136331235,136826261