Gym 100952H&&2015 HIAST Collegiate Programming Contest H. Special Palindrome【dp预处理+矩阵快速幂/打表解法】

H. Special Palindrome

time limit per test:1 second

memory limit per test:64 megabytes

input:standard input

output:standard output

A sequence of positive and non-zero integers called palindromic if it can be read the same forward and backward, for example:

15 2 6 4 6 2 15

20 3 1 1 3 20

We have a special kind of palindromic sequences, let's call it a special palindrome.

A palindromic sequence is a special palindrome if its values don't decrease up to the middle value, and of course they don't increase from the middle to the end.

The sequences above is NOT special, while the following sequences are:

1 2 3 3 7 8 7 3 3 2 1

2 10 2

1 4 13 13 4 1

Let's define the function F(N), which represents the number of special sequences that the sum of their values is N.

For example F(7) = 5 which are : (7), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1)

Your job is to write a program that compute the Value F(N) for given N's.

Input

The Input consists of a sequence of lines, each line contains a positive none zero integer N less than or equal to 250. The last line contains 0 which indicates the end of the input.

Output

Print one line for each given number N, which it the value F(N).

Examples

Input

1
3
7
10
0

Output

1
2
5
17

题目链接:http://codeforces.com/gym/100952/problem/H

题意:一个从开始到中间是非递减的回文被称为特殊回文,例如1123211,定义F(N)为和为N的特殊回文的个数,如F(1)=1,即和为1的回文只有一个 就是 1,F(5)=7, (7), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1),求F(N),N小于等于250!

思路:当N为偶数时,分2种情况,第一种为回文的长度为奇数,那么,最中间的数 m 一定是2 4 6 8......两边的数的和为(N-m)>>1,对(N-i)>>1进行整数划分(m划分),第二种为回文长度为偶数,则回文两边的和为N>>1,对N>>1整数划分(N>>1划分),当N为奇数的时候只有一种情况,就是回文长度为奇数,最中间的数m为1 3 5 7....划分和上面一样!

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 inline ll read()
 5 {
 6     ll x=0,f=1;
 7     char ch=getchar();
 8     while(ch<'0'||ch>'9')
 9     {
10         if(ch=='-')
11             f=-1;
12         ch=getchar();
13     }
14     while(ch>='0'&&ch<='9')
15     {
16         x=x*10+ch-'0';
17         ch=getchar();
18     }
19     return x*f;
20 }
21 inline void write(ll x)
22 {
23     if(x<0)
24     {
25         putchar('-');
26         x=-x;
27     }
28     if(x>9)
29         write(x/10);
30     putchar(x%10+'0');
31 }
32 ll dp[333][333];
33 inline void funday(ll n)
34 {
35     for(ll i=1;i<=n;i++)
36     {
37         for(ll j=1;j<=n;j++)
38         {
39             if(i==1||j==1)
40                 dp[i][j]=1;
41             else if(i>j)
42                 dp[i][j]=dp[i-j][j]+dp[i][j-1];
43             else if(i==j)
44                 dp[i][j]=dp[i][i-1]+1;
45             else dp[i][j]=dp[i][i];
46         }
47     }
48 }
49 ll n,m,ans;
50 int main()
51 {
52     funday(251);
53     while(n=read())
54     {
55         if(n==0)
56             return 0;
57         ans=0;
58         if(n&1)
59         {
60             for(ll i=1;i<=n;i+=2)
61                 ans+=dp[(n-i)/2][i];
62             ans++;
63         }
64         else
65         {
66             for(ll i=2;i<=n;i+=2)
67                 ans+=dp[(n-i)/2][i];
68             ans+=dp[n/2][n/2];
69             ans++;
70         }
71         write(ans);
72         printf("\n");
73     }
74     return 0;
75 }

打表解法:

分奇偶用 dfs 搞出非递减的左半边串, 然后求出这个的和 ans[sum + i]++;

对于偶数个的直接dfs, 对于奇数的则枚举mid, 然后依次dfs

 1 void dfseven(int k, int sum)
 2 {
 3     if(2*sum > 50) return;
 4     //cout<<"here1"<<endl;
 5     for(int i = k; i <= 50; i++){
 6         if(2*(sum + i) <= 50) {ans[2*(sum + i)]++; dfseven(i, sum + i);}
 7         else return;
 8     }
 9 
10 }
11 
12 void dfsodd(int mid, int k, int sum)
13 {
14     if(2*sum + mid > 50) return;
15     //cout<<"here2"<<endl;
16     for(int i = k; i <= 50; i++){
17         if(2*(sum + i) + mid <= 50 && i <= mid) {ans[2*(sum + i) + mid]++; dfsodd(mid, i, sum + i);}
18         else return;
19     }
20 
21 }

然后只打了前ans[50] 及以前的, 因为后面的比较大时间不够的, 所以打出前50的表然后到数列网站 OEIS 查了一下, 还真有,??

所以把那前250个ans贴到 txt里, 然后写一个中间程序 把这些数据 转换成 printf("ans[%d] = %d;", i, val);的样子打到另一个txt文件里, 然后复杂粘贴到上去, 整理下就好了

打表完整代码:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 typedef long long LL;
 6 const int maxn = 250 + 8;
 7 
 8 int ans[maxn];
 9 
10 //偶数个的
11 void dfseven(int k, int sum)
12 {
13     if(2*sum > 50) return;
14     //cout<<"here1"<<endl;
15     for(int i = k; i <= 50; i++){
16         if(2*(sum + i) <= 50) {ans[2*(sum + i)]++; dfseven(i, sum + i);}
17         else return;
18     }
19 
20 }
21 
22 void dfsodd(int mid, int k, int sum)
23 {
24     if(2*sum + mid > 50) return;
25     //cout<<"here2"<<endl;
26     for(int i = k; i <= 50; i++){
27         if(2*(sum + i) + mid <= 50 && i <= mid) {ans[2*(sum + i) + mid]++; dfsodd(mid, i, sum + i);}
28         else return;
29     }
30 
31 }
32 
33 int main()
34 {
35     #ifdef LOCAL
36     freopen("a.txt", "r", stdin);
37     freopen("b.txt", "w", stdout);
38     #endif // LOCAL
39     memset(ans, 0, sizeof ans);
40     //ans[2]++;
41     dfseven(1, 0);
42     //ans[1]++;
43     for(int i = 1; i <= 50; i++){
44         dfsodd(i, 1, 0);
45     }
46     for(int i = 1; i <= 50; i++){
47         printf("ans[%d] = %d;", i, ans[i] + 1);
48     }
49 
50 /*
51     int n;
52     while(scanf("%d", &n)){
53         printf("%d", ans[n]);
54 
55     }
56     */
57     return 0;
58 }

最终AC代码如下:

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 typedef long long LL;
  6 const int maxn = 250 + 8;
  7 
  8 LL ans[maxn];
  9 
 10 int main()
 11 {
 12     
 13 ans[1] = 1;
 14 ans[2] = 2;
 15 ans[3] = 2;
 16 ans[4] = 4;
 17 ans[5] = 3;
 18 ans[6] = 7;
 19 ans[7] = 5;
 20 ans[8] = 11;
 21 ans[9] = 8;
 22 ans[10] = 17;
 23 ans[11] = 12;
 24 ans[12] = 26;
 25 ans[13] = 18;
 26 ans[14] = 37;
 27 ans[15] = 27;
 28 ans[16] = 54;
 29 ans[17] = 38;
 30 ans[18] = 76;
 31 ans[19] = 54;
 32 ans[20] = 106;
 33 ans[21] = 76;
 34 ans[22] = 145;
 35 ans[23] = 104;
 36 ans[24] = 199;
 37 ans[25] = 142;
 38 ans[26] = 266;
 39 ans[27] = 192;
 40 ans[28] = 357;
 41 ans[29] = 256;
 42 ans[30] = 472;
 43 ans[31] = 340;
 44 ans[32] = 621;
 45 ans[33] = 448;
 46 ans[34] = 809;
 47 ans[35] = 585;
 48 ans[36] = 1053;
 49 ans[37] = 760;
 50 ans[38] = 1354;
 51 ans[39] = 982;
 52 ans[40] = 1740;
 53 ans[41] = 1260;
 54 ans[42] = 2218;
 55 ans[43] = 1610;
 56 ans[44] = 2818;
 57 ans[45] = 2048;
 58 ans[46] = 3559;
 59 ans[47] = 2590;
 60 ans[48] = 4485;
 61 ans[49] = 3264;
 62 ans[50] = 5616;
 63 ans[51] = 4097;
 64 ans[52] = 7018;
 65 ans[53] = 5120;
 66 ans[54] = 8728;
 67 ans[55] = 6378;
 68 ans[56] = 10826;
 69 ans[57] = 7917;
 70 ans[58] = 13373;
 71 ans[59] = 9792;
 72 ans[60] = 16484;
 73 ans[61] = 12076;
 74 ans[62] = 20236;
 75 ans[63] = 14848;
 76 ans[64] = 24793;
 77 ans[65] = 18200;
 78 ans[66] = 30275;
 79 ans[67] = 22250;
 80 ans[68] = 36886;
 81 ans[69] = 27130;
 82 ans[70] = 44810;
 83 ans[71] = 32992;
 84 ans[72] = 54329;
 85 ans[73] = 40026;
 86 ans[74] = 65683;
 87 ans[75] = 48446;
 88 ans[76] = 79265;
 89 ans[77] = 58499;
 90 ans[78] = 95419;
 91 ans[79] = 70488;
 92 ans[80] = 114650;
 93 ans[81] = 84756;
 94 ans[82] = 137447;
 95 ans[83] = 101698;
 96 ans[84] = 164496;
 97 ans[85] = 121792;
 98 ans[86] = 196445;
 99 ans[87] = 145578;
100 ans[88] = 234221;
101 ans[89] = 173682;
102 ans[90] = 278720;
103 ans[91] = 206848;
104 ans[92] = 331143;
105 ans[93] = 245920;
106 ans[94] = 392722;
107 ans[95] = 291874;
108 ans[96] = 465061;
109 ans[97] = 345856;
110 ans[98] = 549781;
111 ans[99] = 409174;
112 ans[100] = 649019;
113 ans[101] = 483330;
114 ans[102] = 764959;
115 ans[103] = 570078;
116 ans[104] = 900373;
117 ans[105] = 671418;
118 ans[106] = 1058191;
119 ans[107] = 789640;
120 ans[108] = 1242061;
121 ans[109] = 927406;
122 ans[110] = 1455820;
123 ans[111] = 1087744;
124 ans[112] = 1704261;
125 ans[113] = 1274118;
126 ans[114] = 1992458;
127 ans[115] = 1490528;
128 ans[116] = 2326608;
129 ans[117] = 1741521;
130 ans[118] = 2713398;
131 ans[119] = 2032290;
132 ans[120] = 3160899;
133 ans[121] = 2368800;
134 ans[122] = 3677789;
135 ans[123] = 2757826;
136 ans[124] = 4274556;
137 ans[125] = 3207086;
138 ans[126] = 4962526;
139 ans[127] = 3725410;
140 ans[128] = 5755174;
141 ans[129] = 4322816;
142 ans[130] = 6667228;
143 ans[131] = 5010688;
144 ans[132] = 7716070;
145 ans[133] = 5802008;
146 ans[134] = 8920663;
147 ans[135] = 6711480;
148 ans[136] = 10303379;
149 ans[137] = 7755776;
150 ans[138] = 11888671;
151 ans[139] = 8953856;
152 ans[140] = 13705118;
153 ans[141] = 10327156;
154 ans[142] = 15784173;
155 ans[143] = 11899934;
156 ans[144] = 18162385;
157 ans[145] = 13699699;
158 ans[146] = 20879933;
159 ans[147] = 15757502;
160 ans[148] = 23983452;
161 ans[149] = 18108418;
162 ans[150] = 27524280;
163 ans[151] = 20792120;
164 ans[152] = 31561603;
165 ans[153] = 23853318;
166 ans[154] = 36160845;
167 ans[155] = 27342421;
168 ans[156] = 41397124;
169 ans[157] = 31316314;
170 ans[158] = 47353396;
171 ans[159] = 35839008;
172 ans[160] = 54124796;
173 ans[161] = 40982540;
174 ans[162] = 61816437;
175 ans[163] = 46828032;
176 ans[164] = 70548311;
177 ans[165] = 53466624;
178 ans[166] = 80453313;
179 ans[167] = 61000704;
180 ans[168] = 91682668;
181 ans[169] = 69545358;
182 ans[170] = 104403741;
183 ans[171] = 79229676;
184 ans[172] = 118806744;
185 ans[173] = 90198446;
186 ans[174] = 135102223;
187 ans[175] = 102614114;
188 ans[176] = 153528658;
189 ans[177] = 116658616;
190 ans[178] = 174350347;
191 ans[179] = 132535702;
192 ans[180] = 197865953;
193 ans[181] = 150473568;
194 ans[182] = 224406247;
195 ans[183] = 170727424;
196 ans[184] = 254344551;
197 ans[185] = 193582642;
198 ans[186] = 288094273;
199 ans[187] = 219358315;
200 ans[188] = 326120818;
201 ans[189] = 248410816;
202 ans[190] = 368939881;
203 ans[191] = 281138048;
204 ans[192] = 417130912;
205 ans[193] = 317984256;
206 ans[194] = 471335560;
207 ans[195] = 359444904;
208 ans[196] = 532274004;
209 ans[197] = 406072422;
210 ans[198] = 600743477;
211 ans[199] = 458482688;
212 ans[200] = 677637038;
213 ans[201] = 517361670;
214 ans[202] = 763943462;
215 ans[203] = 583473184;
216 ans[204] = 860768675;
217 ans[205] = 657667584;
218 ans[206] = 969336374;
219 ans[207] = 740890786;
220 ans[208] = 1091013811;
221 ans[209] = 834194700;
222 ans[210] = 1227313238;
223 ans[211] = 938748852;
224 ans[212] = 1379921672;
225 ans[213] = 1055852590;
226 ans[214] = 1550704877;
227 ans[215] = 1186949056;
228 ans[216] = 1741741564;
229 ans[217] = 1333640710;
230 ans[218] = 1955329266;
231 ans[219] = 1497705768;
232 ans[220] = 2194025352;
233 ans[221] = 1681116852;
234 ans[222] = 2460655086;
235 ans[223] = 1886061684;
236 ans[224] = 2758359212;
237 ans[225] = 2114965120;
238 ans[226] = 3090606588;
239 ans[227] = 2370513986;
240 ans[228] = 3461249193;
241 ans[229] = 2655684608;
242 ans[230] = 3874538905;
243 ans[231] = 2973772212;
244 ans[232] = 4335193118;
245 ans[233] = 3328423936;
246 ans[234] = 4848416380;
247 ans[235] = 3723675326;
248 ans[236] = 5419976831;
249 ans[237] = 4163989458;
250 ans[238] = 6056235989;
251 ans[239] = 4654300706;
252 ans[240] = 6764237552;
253 ans[241] = 5200062976;
254 ans[242] = 7551745299;
255 ans[243] = 5807301632;
256 ans[244] = 8427348786;
257 ans[245] = 6482671322;
258 ans[246] = 9400510845;
259 ans[247] = 7233519619;
260 ans[248] = 10481691022;
261 ans[249] = 8067955712;
262 ans[250] = 11682407480;
263     int n;
264     while(scanf("%d", &n)){
265         if(n == 0) break;
266         printf("%I64d\n", ans[n]);
267     }
268 
269     return 0;
270 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏二进制文集

LeetCode 004 Median of Two Sorted Arrays 详细分析

题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/

1111
来自专栏何俊林

OpenGL ES总结(三)OpenGL通过计算纹理坐标来显示一张图片

导读:OpenGL是在图形图像中,非常优秀的渲染库,文中Demo下载地址:https://github.com/hejunlin2013/OpenGLTextu...

3179
来自专栏desperate633

LintCode 分割回文串题目分析代码

首先为了分割出回文串,我们首先要写出判断回文串的方法,这里使用动态规划来判断回文串,而且可以存储子串的回文串的情况。 isPalindrome[i][j]:表...

582
来自专栏HansBug's Lab

3377: [Usaco2004 Open]The Cow Lineup 奶牛序列

3377: [Usaco2004 Open]The Cow Lineup 奶牛序列 Time Limit: 10 Sec  Memory Limit: 128 ...

3227
来自专栏Albert陈凯

技术面试要了解的算法和数据结构知识

目录 在线练习 在线编程面试 数据结构 算法 贪心算法 位运算 复杂度分析 视频教程 面试宝典 计算机科学资讯 文件结构 在线练习 Le...

3225
来自专栏计算机视觉与深度学习基础

Leetcode 134 Gas Station

There are N gas stations along a circular route, where the amount of gas at sta...

2075
来自专栏简书专栏

基于Excel2013的文本函数

CONCATENATE函数既能引用一个区域直接合并,又不会漏掉数值、日期和公式结果,还能引用多个区域,比&符号更好用。

1104
来自专栏算法修养

CodeForces 17E Palisection(回文树)

E. Palisection time limit per test 2 seconds memory limit per test 128 meg...

3414
来自专栏偏前端工程师的驿站

基础野:细说无符号整数

Brief                                 本来只打算理解JS中0.1 + 0.2 == 0.30000000000000004...

2076
来自专栏小樱的经验随笔

2017 Multi-University Training Contest - Team 1 1006&&HDU 6038 Function【DFS+数论】

Function Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K...

2825

扫码关注云+社区

领取腾讯云代金券