NOIP2005 循环 解题报告

刚看到题目，我不知所措，真不知道怎么做（NOIP我真的是太菜了。）。
到网上找到了一个高手的结题报告（几个题目我都是搜到的他的。），原来可以用DP来解大致的思路是这样子的：
比如这里有一个循环（只是假设，可能没有这个数）：123 245 344 123，这就是一个循环数，没错吧？，好，再仔细观察一下，第一项和最后一项的后二位数也是相同的，也就是说后k个数循环的长度是后k-1个数循环长度的倍数。
恩，至于代码的话，等下再发上来

(2010年8月4日18:26:10)，这一题希望能成为我的OI转折题，没什么别的，这题我吃了不少亏，总结了几条教训，如下：
1、拿到题目先仔细分析，是否拥有子问题。
上面这一点不只是DP，各种算法都是大事化小，小事化了，不说用什么出众的数学，但是分析题目的时候，没有别的，要理性，争取能够找到更小的问题，然后逐一攻破。
2、不要为了一些微不足道剪纸而丧失了程序的正确性。
总是认为程序的效率很重要，要多用什么位运算，一些小型剪枝。以后的话尽量不要用这些运算，因为Noip只是要确保在规定时间内完成程序，所以100ms和10ms对于成绩来说都是一样的。
3、暂时就说这么多吧。
当然，程序AC之后还是可以适当的优化一下，体验速度给我带来的快乐！
题目的代码如下，可读性自我感觉4颗星！

#include <stdio.h>
#include <string.h>
#define max(a, b) ((a)>(b)?(a):(b))
#define read(a) read_(&a)
#define output(a) output_(&a)
#define mul(a, b) mul_(&a, &b)
#define mulnum(a, b) mulnum_(&a, b)
#define copy(a, b) memcpy((a), (b), sizeof(numtype) * ((b)->len) + sizeof(int))
#define give(a, b) give_(&a, b)
#define getnum(a, i) (a.num[i])
#define MAX 201
const int used = 10;
typedef char numtype;
typedef struct bignum{
 int len;
 numtype num[MAX];
}bignum;
bignum std, x, num, num1, ans;
int k;

void read_(bignum *a)
{
 char tmp[101];
 int i;
 scanf(%s, tmp);
 a->len = strlen(tmp);
 i = a->len - 1;
 while(i >= 0){
 a->num[i] = tmp[a->len - 1 - i] - \'0\';
 i--;
 }
}

void output_(bignum *a)
{
 int i;
 numtype *num = a->num;
 for(i = a->len - 1; i >= 0; i--){
 printf(%d, num[i]);
 }
 printf(\\n);
}

void give_(bignum *a, int n)
{
 int i;
 for(i = 0; n != 0; i++){
 a->num[i] = n % used;
 n /= used;
 }
 a->len = i;
}

void mul_(bignum *a, bignum *b)
{
 static bignum tmp;
 int len = a->len + b->len - 1;
 int i, j;
 numtype re;
 memset(&tmp, 0, sizeof(bignum));
 /* 上面这段代码我错了一次二次三次.. 我最后才知道所有的问题都是它... */
 for(i = 0; i < a->len; i++){
 re = 0;
 for(j = 0; j < b->len; j++){
 tmp.num[i + j] += a->num[i] * b->num[j] + re;
 //是+=
 re = tmp.num[i + j] / used;
 if(re > 0){
 tmp.num[i + j] %= used;
 }
 }
 if(re > 0){
 tmp.num[i + j] = re;
 len = max(i + j + 1, len);
 }
 }
 if(len > k){
 len = k;
 }
 tmp.len = len;
 copy(a, &tmp);
}

void mulnum_(bignum *a, int n)
{
 int i;
 numtype re = 0;
 /* 忘记初始化 */
 for(i = 0; i < a->len; i++){
 a->num[i] = a->num[i] * n + re;
 re = a->num[i] / used;
 if(re > 0){
 a->num[i] %= used;
 }
 }
 if(re > 0){
 a->num[i] = re;
 a->len++;
 } 
}

int main(void)
{
 int i, j;
 int a, b;
 read(std);
 give(ans, 1);
 copy(&x, &std);
 give(ans, 1);
 scanf(%d, &k);
 for(i = 0; i < k; i++){
 copy(&num, &std);
 give(num1, 1);
 b = getnum(std, i);
 for(j = 1; j <= 10; j++){
 mul(num1, x);
 mul(num, x);
 a = getnum(num, i);
 if(a == b){
 copy(&x, &num1);
/* give(t, j);
 mul(ans, t);*/
 mulnum(ans, j);
 break;
 }
 }
 if(j > 10){
 printf(-1\\n);
 return 0;
 }
 }
 output(ans);
 return 0;
}