题目

链接:bajdcc/ACM

描述

在所有的N位数中,有多少个数中有偶数个数字3?结果模12345。(1<=N<=10000)

样例输入

2

样例输出

73

方法一:穷举

评价:最简单又是效率最低的方法。

缺陷:N很大时,用来遍历的i用long long就放不下了,gg。但是首先,你要耐心等到long long溢出。耗时就不算了,太慢。

#include <iostream>

using namespace std;

#define LL long long
#define NUM 3 int main() {
LL m,n,i,j,t,count;
cin>>n;
for(i=0,m=1;i<n;i++) m*=10; // 求N位数上界
for(i=m/10,count=0;i<m;i++) { // 从10..000 ~ 99..999
for (j=0,t=i;t;t/=10) // 取每一位
if (t%10==NUM) j++; // 如果是NUM计数j加一
if (j%2==0) {
count++; // 偶数个NUM计数count加一
count%=12345;
}
}
cout<<count;
return 0;
}

方法二:递推

穷举法有着天生的缺陷:遍历的i范围有限,除非用高精度才能避免。

进一步思考,将题目改为“有多少个数中有偶数个4”,结果记为N4。那么我想N4应该跟N3是一样的,对称性嘛。证明:对应每个数中有偶数个3的数,我都可以找到相应的数,只要将原数中的3跟4对调下即可,比如133242,调下变144232,欧了。当然了,想到这个结论然并卵,我们目前只证得N1~N9是相等的,理所应当,假如知道了N1~N9的和,那只要平均下就能得出结果。然而还是手足无措,那就用递推来想想。

假如目前有数6XXXXX,以6开头的符合条件的数有多少呢?好吧,无视6,得出f(6XXXXX)=f(XXXXX),因为6根本没必要算进去嘛,欧了!我们发现一个重要结论:有些子问题是重复的!所以无脑穷举法太慢的原因就是计算了重复的子问题。好吧,现在来找找哪些是重复的子问题。

设下函数f(n)和g(n),n是位数,f表示有偶数个3的总数,g表示有奇数个3的总数。从一位数开始,0不算,f(1)=8,g(1)=1,只要看有没有3就行了。

现在是N位数XY,想一想,如果Y有奇数个3同时X有奇数个3,那么f函数欧了;如果Y有偶数个3同时X有偶数个3,那么f函数欧了。如果Y有奇数个3同时X有偶数个3,那么g函数欧了;如果Y有偶数个3同时X有奇数个3,那么g函数欧了。最后,我们将X定为最高一位,Y定为后N-1位,用来递推,这样的话X就不能是0,这就决定了f(1)=8而不是9,说到底,0还是要考虑到,不过是作为后n-1位了,体现在下面推导式右边的乘数9上。

有点思路了,现在把f和g的推导式写出来。边界:f(1)=8,g(1)=1。如果第n位是3,那么加上g(n-1);如果第n位不是3,那么加上9*f(n-1),因为不是3的话有9种可能,乘法原理。

整理下:

  • f(1)=8,g(1)=1
  • f(n)=g(n-1)+9*f(n-1)
  • g(n)=f(n-1)+9*g(n-1)

书写代码:

#include <iostream>

using namespace std;

int g(int n);
int f(int n) {
return n==1?8:(g(n-1)+9*f(n-1))%12345;
} int g(int n) {
return n==1?1:(f(n-1)+9*g(n-1))%12345;
} int main() {
int n;
cin>>n;
cout<<f(n);
return 0;
}

运行速度明显快多了。

方法三:动态规划

方法二还是需要改进,f和g函数有重复的递归调用,当然可以用记忆化去搞定。这里既然有了递推式,状态转移方程就呼之欲出了,方法二中已写出。

#include <iostream>

using namespace std;

int f[10002][2];//f[][0]=偶数个3,f[][1]=奇数个3

int main() {
int n;
cin>>n;
f[1][0]=8,f[1][1]=1;
for (int i=2;i<=n;i++) {
f[i][0]=(9*f[i-1][0]+f[i-1][1])%12345;
f[i][1]=(f[i-1][0]+9*f[i-1][1])%12345;
}
cout<<f[n][0];
return 0;
}

方法四:打表法

略。

方法五:公式法

没想到吧,这也能用公式做!Fibonacci数列也是有通项公式的,但是要怎么求呢?(当然参照书上的)

【NOI】9272 偶数个三-LMLPHP

书写代码:

#include <iostream>

using namespace std;

#define MOD 12345

// 快速幂取模
int fast(int a, int N, int mod) {
long long r = 1, aa=a;
while(N) {
//取N的二进制位,是一则乘上相应幂并求余
if (N & 1) r = (r * aa) % mod;
N >>= 1;
aa = (aa * aa) % mod;
}
return (int)r;
} // 快速幂取模(2为底)
int fast2(int N, int mod) {
static long long a=(1LL<<62)%mod;
int s=N%62,t=N/62;// 2^N=2^s*a^t
int r = (1LL<<s) % mod;
if (t>0) {
r *= fast(a,t,mod);// 2^s*a^t % mod
r %= mod;
}
return (int)r;
} int main() {
int n;
cin>>n;
//化简:
// an=1/2*{7*2^(3n-3)+9*2^(n-1)*5^(n-1)}
// an=2^(n-2)*{9*5^(n-1)+7*2^(2n-2)}
int a=fast2(n-2,MOD);
int b=a<<1;
int ans=a*(9*fast(5,n-1,MOD)+7*((b*b)%MOD));
ans%=MOD;
cout<<ans<<endl;
return 0;
}

可以看出,为了优化,代码显得不怎么美观,如果题目不要求精确值的话,那么用浮点数以及pow我想应该可以让速度再快一点。

比较而言,其实动态规划法是最简洁且高效的

总结

一个题目,多种方法,其实从本质而言,以计算机的思维做,自然是DP,以数学家的思维做,就是推导通项公式。然而,通项公式中有幂,让计算机做本质上也不高效。

从多线程优化的角度来看,DP法的本质是一层层递推的计算,后者依赖前者,计算并不独立,不能分解成小任务,最快就是O(n)。而公式法本质就是求幂,而求幂也存在依赖关系,且子问题都相同,没必要分割。穷举法倒可以保证子任务的独立性,不过计算量还是很大,当且仅当没有其他好方法的时候用。

公式法推导很复杂,耗时间,因此,用动态规划法是绝佳的。

05-11 13:51