Singapore NOI2012 MODSUM题解

MODSUM（modsum.pas/c/cpp）

【问题描述】

在本题中，你得到了一个含有n个参数的函数f：

f(x1,…,x2)=(((x1+x2+…+xn)4+2*(x1+x2+…+xn)2) mod 5)+1

为了避免出现争议，函数f只接受整数参数。你的任务是计算f的所有函数值的和，每个参数xi是从vi到wi之间的整数。也就是说，你需要计算

例如，如果n=3，v1=2，w1=3.v2=10，w2=12，v3=17，w3=17，那么这个结果应该是19。因为f(2，10，17) = 4, f(2，11，17) = 1, f(2，12，17) = 4, f(3，10，17) = 1,f(3，11，17) = 4 and f(3，12，17) = 5。

重要提示：你可以认为这个结果是总小于1,000,000的。

【输入】

你的程序必须从标准输入中读取数据。输入包含一个数n（1≤n≤1000），跟在n后面有n对数，vi和wi，你可以认为vi≤wi，vi和wi都是0~100之间的整数。比如上面这个例子，输入是：

3 2 3 10 12 17 17

【输出】

你的程序必须从标准输出中输出。输出计算出的和。比如上面这个例子，输出则是：

19

【数据范围】

你的程序将会被5套测试数据测试：

1. （5分）n≤6；

2. （5分）n≤20；

3. （5分）n≤100；

4. （5分）n≤200；

5. （5分）n≤1000.

【题目分析】

看到本题，我们第一个反应到的算法应该就是搜索算法，深度优先搜索解答树，即枚举每个数从vi到wi的值，逐个计算函数值，最后累加。但是分析一下极端情况我们会发现，枚举量会达到1011000，这个枚举量是难以接受的，但是题目中给了我们一个重要信息——最后的值不会超过1,000,000，每一个函数值最小为1，最大为5，和不超过1,000,000，也就代表着最多枚举量不会超过1,000,000。这样我们使用DFS搜索解答树完全是可行的。但是由于循环的层数不固定，所以我们通过递归的方式来变相的达到循环的效果。

比如题目中所给的例子的解答树是：

但是从DFS可以看出，它计算了很多重复的值，浪费了很多的时间。那么我们可以考虑采用BFS的思想，逐层进行DP的方式进行处理。

在此之前，我们先计算出一个表格，用来计算当Σxi%5分别等于 0,1,2,3,4时f(x1,…,xn)的取值，方便后面的计算。

Σxi%5

f(x1,…,xn)

0

1

1

4

2

5

3

5

4

4

那么，我们设f[i][y]表示前i个数里面，Σxi%5=y的种类数。那么状态转移方程为：

（其中，c[i][z]表示第i个数所在的范围vi到wi之间除以5余z的数的数量。边界f[0][0]=1）

例如：f[4][0]=f[3][0]*c[4][0]+f[3][1]*c[4][4]+f[3][2]*c[4][3]+f[3][3]*c[4][2]+f[3][4]*c[4][1]。

样例分析：前四个数的和除以5余0的可能有：前三个数的和余0的数再加上第四个数的范围内余0的数，最终和余数仍为0（种类用乘法）；前三个数的和余1的数再加上第四个数的范围内余4的数，最终和余数仍为0（种类用乘法）…以此类推。

而最后，我们把f[n][0]~f[n][4]中的数分别和上表的数相乘，再相加即为最终答案。

【程序源代码】

1. 递归计算代码：

 
  1. //modsum.cpp by JerryXie   
  2.   
  3. #include<cstdio>   
  4. using namespace std;   
  5. struct para //定义结构体用来表示变量   
  6. {   
  7.   int v,w;   
  8. };   
  9.   
  10. int n,xx[1001],finalans=0;   
  11. para p[1001];   
  12. int f() //计算函数值    
  13. {   
  14.     int i,sum=0,ans=0,temp;   
  15.     for(i=1;i<=n;i++)   
  16.       sum+=xx[i];   
  17.     sum%=5;   
  18.     temp=sum;   
  19.     sum=sum*sum*sum*sum;   
  20.     sum%=5;   
  21.     ans+=sum;   
  22.     sum=temp;   
  23.     sum=sum*sum*2;   
  24.     sum%=5;   
  25.     ans+=sum;   
  26.     ans%=5;   
  27.     ans++;   
  28.     return ans;   
  29. }   
  30. void work(int xi) //递归取数    
  31. {   
  32.      int i;   
  33.      for(i=p[xi].v;i<=p[xi].w;i++)   
  34.      {   
  35.        xx[xi]=i; //循环选定每一层的数    
  36.        if(xi==n) //如果已经选完    
  37.          finalans+=f(); //计算函数值    
  38.        else //没选完    
  39.          work(xi+1); //继续递归下一层    
  40.      }   
  41. }   
  42. int main() //主函数    
  43. {   
  44.     int i;   
  45.     scanf("%d",&n);   
  46.     for(i=1;i<=n;i++)   
  47.       scanf("%d%d",&p[i].v,&p[i].w);   
  48.     work(1); //调用递归函数计算    
  49.     printf("%d",finalans);   
  50.     return 0;   
  51. }   

2. 动态规划代码：

 
  1. //modsum.cpp by JerryXie   
  2.   
  3. #include<cstdio>   
  4. using namespace std;   
  5. struct para //定义结构体用来表示变量    
  6. {   
  7.   int v,w;   
  8. };   
  9.   
  10. para p[1001];   
  11. int f[1001][10],a[10],c[1001][10];   
  12. void create() //初始化    
  13. {   
  14.     a[0]=1;a[1]=4;a[2]=5;a[3]=5;a[4]=4; //初始化计算的参数和与函数值的关系    
  15.     f[0][0]=1; //初始化DP边界    
  16.     return;    
  17. }   
  18. int main()   
  19. {   
  20.     int i,j,k,n,temp,ans=0;   
  21.     scanf("%d",&n);   
  22.     create();   
  23.     for(i=1;i<=n;i++)   
  24.     {   
  25.       scanf("%d%d",&p[i].v,&p[i].w); //读数    
  26.       for(j=p[i].v;j<=p[i].w;j++) //计算第i个数的取值范围中除以5与temp的数量    
  27.       {   
  28.         temp=j%5;   
  29.         c[i][temp]++;   
  30.       }   
  31.     }   
  32.     for(i=1;i<=n;i++) //开始DP    
  33.     {   
  34.       for(j=0;j<=4;j++)   
  35.       {   
  36.         for(k=0;k<=4;k++)   
  37.         {   
  38.           f[i][j]+=f[i-1][(j+5-k)%5]*c[i][k];   
  39.         }   
  40.       }   
  41.     }   
  42.     for(i=0;i<=4;i++) //计算最终结果    
  43.       ans+=f[n][i]*a[i];   
  44.     printf("%d",ans);   
  45.     return 0;   
  46. }   

欢迎鄙视。

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/jerryxie/p/4780693.html