题目
链接：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数列也是有通项公式的，但是要怎么求呢？（当然参照书上的）
书写代码：
#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)。而公式法本质就是求幂，而求幂也存在依赖关系，且子问题都相同，没必要分割。穷举法倒可以保证子任务的独立性，不过计算量还是很大，当且仅当没有其他好方法的时候用。
公式法推导很复杂，耗时间，因此，用动态规划法是绝佳的。