华东交通大学2016年ACM“双基”程序设计竞赛 1004

Problem Description

LB是个十分喜欢钻研的人，对什么事都要搞明白。
有一天他看到一个公式，((a-b)*c+d*e)/f=k。他想如果给定K的值，
一共有多少种不同整数的组合(a,b,c,d,e,f)使公式成立，（-50≤a,b,c,d,e,f≤50）LB算了很久都没有算出来，
所以他向你求助，由于答案很大，所以对1e9+7取模

Input

第一行只包含一个整数T（T≤100），表示测试用例的个数。
对于每个测试用例，第一行只包含一个整数K（-500≤K≤500）

Output

对于每个测试用例，输出最后对1e9+7取模的答案。

Sample Input

1
500

Sample Output

27194104

Author

zhengjinke2123

解法：暴力打表

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #define ll long long
 5 using namespace std;
 6 int l[1000005],r[1000005];
 7 struct node
 8 {
 9     ll x,ip;
10 } e[1000005];
11 bool cmp(node a,node b)
12 {
13     return a.x<b.x;
14 }
15 ll MAX(ll a,ll b)
16 {
17     return a>b?a:b;
18 }
19 int mod=(1e9+7);
20 ll x[500000];
21 ll pos[500000];
22 void cmd()
23 {
24     int num=0;
25     for(int a=-50; a<=50; a++)
26     {
27         for(int b=-50; b<=50; b++)
28         {
29             for(int c=-50; c<=50; c++)
30             {
31                 x[5000+(a-b)*c]++;
32             }
33         }
34     }
35     for(int i=-500; i<=500; i++)
36     {
37         num=0;
38         for(int d=-50; d<=50; d++)
39         {
40             for(int e=-50; e<=50; e++)
41             {
42                 for(int f=-50; f<=50; f++)
43                 {
44                     if(f==0) continue;
45                     int y=i*f-d*e;
46                     num+=x[5000+y];
47                     num%=mod;
48                 }
49             }
50         }
51         num%=mod;
52         pos[i+500]=num;
53     }
54 }
55 int o[]={27194104,
56 14106600, 23626352, 16522256, 23701192, 25481344, 21107048, 15223680, 27835344, 14416888, 28103780, 18171336, 22833664, 14576368, 26260484, 17802848, 24201384, 22785328, 19585824, 16352328, 37814288, 14904432, 19803808, 20101392, 26446808, 20298424, 25150936, 17441008, 23819728, 19071968, 25843232, 17833688, 32409856, 15411360, 20457000, 24190800, 25691792, 15576960, 32826248, 15666544, 30132376, 21965992, 20907008, 15856576, 32924936, 23478344, 21142800, 20062280, 23701688, 18488936, 37136520, 16213936, 30353816, 20399280, 21629312, 19939224, 31435328, 16505264, 24002720, 26950208, 34631752, 16692320, 27756656, 18899360, 24785136, 26243384, 26412968, 16989408, 37797664, 17092224, 28704680, 25182248, 25377536, 20132912, 28732848, 23151800, 27217712, 24669912, 23174640, 17624352, 45568272, 17738232, 27147224, 22284528, 30537816, 21792840, 33770648, 20999280, 26598784, 22699416, 30357272, 18293784, 37313728, 20902904, 28604608, 30925816, 27259072, 20308208, 30852576, 18769824, 39022192,
57 28452344, 24935568, 19002368, 41310616, 23206648, 25248960, 24012176, 35581504, 21519520, 41092680, 19506880, 28660016, 27396272, 25893384, 29623416, 41069100, 19894536, 26235776, 24964744, 37325488, 20157112, 41239336, 22010752, 32998680, 32683064, 30736320, 20566832, 38657144, 24020736, 34176160, 28963048, 35969048, 20993464, 34549920, 25618976, 37078056, 28989184, 28018416, 22478912, 54401788, 21578512, 28397488, 32333976, 31858248, 26515800, 35965744, 22043968, 39494756, 32096040, 43279980, 22345936, 41753600, 22509856, 29601920, 36067856, 36535696, 28025376, 41649792, 25768896, 42217536, 28826888, 32076216, 23342656, 54166504, 28474872, 30883672, 32587592, 34658072, 23858440, 51230176, 29543160, 38559008, 30133536, 31800120, 32839472, 48176504, 26680928, 39958040, 30814456, 48487944, 27870776, 40835712, 25166496, 36761664, 47500440, 33253696, 25558808, 52517392, 25764368, 41830072, 32270392, 47637216, 26177640, 46987608, 31908480, 44174616, 33042480, 34831472, 32679024, 61973480,
58 30600512, 35385840, 39788616, 43249216, 33214528, 53739628, 27702160, 40349688, 34698008, 45098264, 29190920, 60776824, 34456056, 42777072, 44557088, 41686840, 28882504, 48964048, 29138480, 61563864, 39897464, 38410672, 29649936, 57193576, 41050704, 39063120, 46380840, 49708456, 30430928, 64665108, 30698240, 44603296, 38481488, 48904928, 37714528, 66066656, 31542664, 41172368, 43038840, 58098208, 38625080, 54021032, 32416424, 52099368, 50337608, 42698176, 38424056, 72678872, 33351008, 56195908, 41783032, 52628560, 37629040, 56907488, 50007528, 49716784, 46446896, 49533584, 34979232, 83467608, 35327312, 54982680, 44271232, 51654944, 45796064, 65745196, 36390528, 56637296, 57091832, 61906912, 37141232, 69815040, 37527096, 48874600, 64000440, 68539356, 38307592, 63608400, 42402656, 73550816, 48508392, 50939120, 46943896, 80915388, 50421616, 52031544, 50083944, 58365152, 40857648, 91031896, 46989496, 68071808, 58222640, 54342536, 53078968, 78343912, 50517840, 55574464, 53519216, 83962708,
59 43720536, 81312820, 44230416, 75532232, 70870000, 58215304, 45288232, 90429736, 45831248, 75289984, 70995888, 69795912, 52823344, 77018568, 59225872, 77293124, 59512176, 75205888, 48739104, 111589600, 49354704, 64209184, 61789768, 86115136, 73835808, 82753960, 51310096, 76724992, 70970120, 84369288, 55758792, 113530548, 53405344, 69459808, 86493512, 80679648, 54889784, 94381036, 68267544, 105626748, 69667856, 73399488, 57261296, 107911368, 71502264, 93676832, 79620760, 93622948, 59825528, 120985800, 60723536, 89838672, 91353528, 80112640, 76748496, 129570472, 72838712, 82605336, 83541096, 126101808, 65635392, 111698808, 66707080, 104641132, 108925368, 88044248, 82815824, 134105624, 70124304, 114167504, 91636672, 112630268, 72585384, 140339740, 93599160, 108087576, 96259776, 97548736, 83239992, 171242628, 92697640, 101142720, 110916488, 115857120, 102689992, 134790616, 82571280, 144983168, 106941648, 140972480, 85887184, 162400880, 87637440, 113509264, 150767256, 140874852, 91323064, 150235992, 93267632, 168159704,
60 134645080, 146237064, 97481256, 190112136, 123835904, 134822276, 128016728, 155481984, 125891976, 210648568, 106863400, 175718620, 136802040, 147040852, 137746984, 224095800, 114856192, 153836684, 154908208, 216576496, 120707048, 202518324, 152525304, 184633216, 193354516, 169017460, 130354808, 254979228, 133824520, 233608052, 177146256, 202804104, 141185576, 242193292, 180831800, 225933996, 220511836, 196685596, 153357824, 317029656, 157746312, 207452852, 206053048, 273157924, 212493648, 281545656, 171974960, 255962736, 223173040, 285972688, 217151608, 347268336, 197564524, 258824248, 300782388, 301165260, 208765964, 358732952, 214571900, 363262652, 277098284, 286787464, 226543708, 402084816, 302842644, 301656864, 307103796, 357121208, 245579524, 441983912, 252214716, 391450988, 332137384, 342259472, 320002640, 473789384, 282949584, 372544828, 383109056, 456858172, 296707704, 469537320, 303669448, 441750248, 430990768, 433444172, 327104400, 531363336, 342985428, 476068076, 422358824, 479758456, 379753020, 522892816, 403838348, 483089496, 432361944, 451321856, 363555504, 166016493,
61 363555504, 451321856, 432361944, 483089496, 403838348, 522892816, 379753020, 479758456, 422358824, 476068076, 342985428, 531363336, 327104400, 433444172, 430990768, 441750248, 303669448, 469537320, 296707704, 456858172, 383109056, 372544828, 282949584, 473789384, 320002640, 342259472, 332137384, 391450988, 252214716, 441983912, 245579524, 357121208, 307103796, 301656864, 302842644, 402084816, 226543708, 286787464, 277098284, 363262652, 214571900, 358732952, 208765964, 301165260, 300782388, 258824248, 197564524, 347268336, 217151608, 285972688, 223173040, 255962736, 171974960, 281545656, 212493648, 273157924, 206053048, 207452852, 157746312, 317029656, 153357824, 196685596, 220511836, 225933996, 180831800, 242193292, 141185576, 202804104, 177146256, 233608052, 133824520, 254979228, 130354808, 169017460, 193354516, 184633216, 152525304, 202518324, 120707048, 216576496, 154908208, 153836684, 114856192, 224095800, 137746984, 147040852, 136802040, 175718620, 106863400, 210648568, 125891976, 155481984, 128016728, 134822276, 123835904, 190112136, 97481256, 146237064, 134645080, 168159704,
62 93267632, 150235992, 91323064, 140874852, 150767256, 113509264, 87637440, 162400880, 85887184, 140972480, 106941648, 144983168, 82571280, 134790616, 102689992, 115857120, 110916488, 101142720, 92697640, 171242628, 83239992, 97548736, 96259776, 108087576, 93599160, 140339740, 72585384, 112630268, 91636672, 114167504, 70124304, 134105624, 82815824, 88044248, 108925368, 104641132, 66707080, 111698808, 65635392, 126101808, 83541096, 82605336, 72838712, 129570472, 76748496, 80112640, 91353528, 89838672, 60723536, 120985800, 59825528, 93622948, 79620760, 93676832, 71502264, 107911368, 57261296, 73399488, 69667856, 105626748, 68267544, 94381036, 54889784, 80679648, 86493512, 69459808, 53405344, 113530548, 55758792, 84369288, 70970120, 76724992, 51310096, 82753960, 73835808, 86115136, 61789768, 64209184, 49354704, 111589600, 48739104, 75205888, 59512176, 77293124, 59225872, 77018568, 52823344, 69795912, 70995888, 75289984, 45831248, 90429736, 45288232, 58215304, 70870000, 75532232, 44230416, 81312820, 43720536, 83962708,
63 53519216, 55574464, 50517840, 78343912, 53078968, 54342536, 58222640, 68071808, 46989496, 91031896, 40857648, 58365152, 50083944, 52031544, 50421616, 80915388, 46943896, 50939120, 48508392, 73550816, 42402656, 63608400, 38307592, 68539356, 64000440, 48874600, 37527096, 69815040, 37141232, 61906912, 57091832, 56637296, 36390528, 65745196, 45796064, 51654944, 44271232, 54982680, 35327312, 83467608, 34979232, 49533584, 46446896, 49716784, 50007528, 56907488, 37629040, 52628560, 41783032, 56195908, 33351008, 72678872, 38424056, 42698176, 50337608, 52099368, 32416424, 54021032, 38625080, 58098208, 43038840, 41172368, 31542664, 66066656, 37714528, 48904928, 38481488, 44603296, 30698240, 64665108, 30430928, 49708456, 46380840, 39063120, 41050704, 57193576, 29649936, 38410672, 39897464, 61563864, 29138480, 48964048, 28882504, 41686840, 44557088, 42777072, 34456056, 60776824, 29190920, 45098264, 34698008, 40349688, 27702160, 53739628, 33214528, 43249216, 39788616, 35385840, 30600512, 61973480,
64 32679024, 34831472, 33042480, 44174616, 31908480, 46987608, 26177640, 47637216, 32270392, 41830072, 25764368, 52517392, 25558808, 33253696, 47500440, 36761664, 25166496, 40835712, 27870776, 48487944, 30814456, 39958040, 26680928, 48176504, 32839472, 31800120, 30133536, 38559008, 29543160, 51230176, 23858440, 34658072, 32587592, 30883672, 28474872, 54166504, 23342656, 32076216, 28826888, 42217536, 25768896, 41649792, 28025376, 36535696, 36067856, 29601920, 22509856, 41753600, 22345936, 43279980, 32096040, 39494756, 22043968, 35965744, 26515800, 31858248, 32333976, 28397488, 21578512, 54401788, 22478912, 28018416, 28989184, 37078056, 25618976, 34549920, 20993464, 35969048, 28963048, 34176160, 24020736, 38657144, 20566832, 30736320, 32683064, 32998680, 22010752, 41239336, 20157112, 37325488, 24964744, 26235776, 19894536, 41069100, 29623416, 25893384, 27396272, 28660016, 19506880, 41092680, 21519520, 35581504, 24012176, 25248960, 23206648, 41310616, 19002368, 24935568, 28452344, 39022192,
65 18769824, 30852576, 20308208, 27259072, 30925816, 28604608, 20902904, 37313728, 18293784, 30357272, 22699416, 26598784, 20999280, 33770648, 21792840, 30537816, 22284528, 27147224, 17738232, 45568272, 17624352, 23174640, 24669912, 27217712, 23151800, 28732848, 20132912, 25377536, 25182248, 28704680, 17092224, 37797664, 16989408, 26412968, 26243384, 24785136, 18899360, 27756656, 16692320, 34631752, 26950208, 24002720, 16505264, 31435328, 19939224, 21629312, 20399280, 30353816, 16213936, 37136520, 18488936, 23701688, 20062280, 21142800, 23478344, 32924936, 15856576, 20907008, 21965992, 30132376, 15666544, 32826248, 15576960, 25691792, 24190800, 20457000, 15411360, 32409856, 17833688, 25843232, 19071968, 23819728, 17441008, 25150936, 20298424, 26446808, 20101392, 19803808, 14904432, 37814288, 16352328, 19585824, 22785328, 24201384, 17802848, 26260484, 14576368, 22833664, 18171336, 28103780, 14416888, 27835344, 15223680, 21107048, 25481344, 23701192, 16522256, 23626352, 14106600, 27194104,
66 };
67 int main()
68 {
69   //  cmd();
70     int t,n;
71     while(cin>>t)
72     {
73         while(t--)
74         {
75         cin>>n;
76         cout<<o[n+500]%mod<<endl;
77         }
78     }
79     return 0;
80 }