【NOIP模拟赛】数字

2014年10月6日1,3052

【问题描述】

一个数字被称为好数字当他满足下列条件:

  1. 它有2*n个数位,n是正整数(允许有前导0)
  2. 构成它的每个数字都在给定的数字集合S中。
  3. 它前n位之和与后n位之和相等或者它奇数位之和与偶数位之和相等

例如对于n=2,S={1,2},合法的好数字有1111,1122,1212,1221,2112,2121,2211,2222这样8种。

已知n,求合法的好数字的个数mod 999983。

【输入格式】

第一行一个数n。

接下来一个长度不超过10的字符串,表示给定的数字集合。

【输出格式】

一行一个数字表示合法的好数字的个数mod 999983。

【样例输入】

2

0987654321

【样例输出】

1240

【数据规模】

对于20%的数据,n≤7。

对于100%的.据,n≤1000,|S|≤10。

题解

ANS=前n位之和与后n位之和相等的方案数+奇数位之和与偶数位之和相等的方案数-前n位之和与后n位之和相等且奇数位之和与偶数位之和相等的方案数

前2个需要+的方案数都很好求,直接递推,重点是最后一个要满足2个条件的方案数怎么求,其实也很简单:

因为前n位之和=后n位之和,奇数位之和=偶数位之和

所以前n位中奇数位之和=后n位中偶数位之和 且

前n位中偶数位之和=后n位中奇数位之和

现在只要求上面这个问题的方案数,由于两个等式中的元素无交集,也是十分好算的。

 

  • 曹军2014年10月6日 下午5:50 回复

    请问今天的模拟赛可以公布下吗

    #1  
    • hzwer2014年10月10日 下午9:52 回复
      admin

      这个是校内的模拟赛,可以联系我索要。。。但是好像在oj上不一定找得到

      #11