问题描述&br&　　我们把一个数称为有趣的，当且仅当：&br&　　1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。&br&　　2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。&br&　　3. 最高位数字不为0。&br&　　因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：。&br&　　请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以的余数。&br&输入格式&br&　　输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。&br&输出格式&br&　　输出只有一行，包括恰好n 位的整数中有趣的数的个数除以的余数。&br&样例输入&br&4&br&样例输出&br&3&br&&br&这是题目 我的答案是 &br&&br&&div class=&highlight&&&pre&&code class=&language-cpp&&&span class=&cp&&#include &stdio.h&&/span&
&span class=&cp&&#include &iostream&&/span&
&span class=&cp&&#include &math.h& &/span&
&span class=&k&&using&/span& &span class=&k&&namespace&/span& &span class=&n&&std&/span&&span class=&p&&;&/span&
&span class=&kt&&int&/span& &span class=&nf&&main&/span&&span class=&p&&()&/span& &span class=&p&&{&/span&
&span class=&kt&&int&/span& &span class=&n&&panduan&/span&&span class=&p&&(&/span&&span class=&kt&&int&/span& &span class=&n&&n&/span&&span class=&p&&,&/span& &span class=&kt&&int&/span& &span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&mi&&1001&/span&&span class=&p&&]);&/span&
&span class=&kt&&int&/span& &span class=&n&&n&/span&&span class=&p&&;&/span&
&span class=&n&&scanf&/span&&span class=&p&&(&/span&&span class=&s&&&%d&&/span&&span class=&p&&,&/span& &span class=&o&&&&/span&&span class=&n&&n&/span&&span class=&p&&);&/span&
&span class=&k&&if&/span& &span class=&p&&(&/span&&span class=&n&&n&/span& &span class=&o&&&&/span& &span class=&mi&&4&/span& &span class=&o&&||&/span& &span class=&n&&n&/span&&span class=&o&&&&/span&&span class=&mi&&1000&/span&&span class=&p&&)&/span&
&span class=&k&&return&/span& &span class=&mi&&0&/span&&span class=&p&&;&/span&
&span class=&kt&&int&/span& &span class=&n&&i&/span&&span class=&p&&,&/span& &span class=&n&&j&/span&&span class=&p&&,&/span& &span class=&n&&num&/span&&span class=&p&&,&/span& &span class=&n&&r&/span&&span class=&p&&,&/span& &span class=&n&&e&/span&&span class=&p&&,&/span& &span class=&n&&sum&/span& &span class=&o&&=&/span& &span class=&mi&&0&/span&&span class=&p&&,&/span& &span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&mi&&1001&/span&&span class=&p&&];&/span&
&span class=&k&&for&/span& &span class=&p&&(&/span&&span class=&n&&i&/span& &span class=&o&&=&/span& &span class=&mi&&2013&/span&&span class=&p&&;&/span& &span class=&n&&i&/span& &span class=&o&&&&/span& &span class=&n&&pow&/span&&span class=&p&&(&/span&&span class=&mi&&10&/span&&span class=&p&&,&/span& &span class=&n&&n&/span&&span class=&p&&);&/span& &span class=&n&&i&/span&&span class=&o&&++&/span&&span class=&p&&)&/span&&span class=&c1&&//将i存入a数组&/span&
&span class=&p&&{&/span&
&span class=&n&&num&/span& &span class=&o&&=&/span& &span class=&n&&i&/span&&span class=&p&&;&/span&
&span class=&k&&for&/span& &span class=&p&&(&/span&&span class=&n&&j&/span& &span class=&o&&=&/span& &span class=&mi&&1&/span&&span class=&p&&;&/span& &span class=&n&&j&/span& &span class=&o&&&=&/span& &span class=&n&&n&/span&&span class=&p&&;&/span& &span class=&n&&j&/span&&span class=&o&&++&/span&&span class=&p&&)&/span& &span class=&p&&{&/span&
&span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&n&&j&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&n&&num&/span& &span class=&o&&/&/span& &span class=&n&&pow&/span&&span class=&p&&(&/span&&span class=&mi&&10&/span&&span class=&p&&,&/span& &span class=&p&&(&/span&&span class=&n&&n&/span& &span class=&o&&-&/span& &span class=&n&&j&/span&&span class=&p&&));&/span&
&span class=&n&&num&/span& &span class=&o&&=&/span& &span class=&n&&num&/span& &span class=&o&&-&/span& &span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&n&&j&/span&&span class=&p&&]&/span& &span class=&o&&*&/span& &span class=&p&&(&/span&&span class=&n&&pow&/span&&span class=&p&&(&/span&&span class=&mi&&10&/span&&span class=&p&&,&/span& &span class=&p&&(&/span&&span class=&n&&n&/span& &span class=&o&&-&/span& &span class=&n&&j&/span&&span class=&p&&)));&/span&
&span class=&p&&}&/span&
&span class=&n&&r&/span& &span class=&o&&=&/span& &span class=&n&&panduan&/span&&span class=&p&&(&/span&&span class=&n&&n&/span&&span class=&p&&,&/span& &span class=&n&&a&/span&&span class=&p&&);&/span&
&span class=&k&&if&/span& &span class=&p&&(&/span&&span class=&n&&r&/span& &span class=&o&&==&/span& &span class=&mi&&1&/span&&span class=&p&&)&/span& &span class=&p&&{&/span&
&span class=&n&&sum&/span&&span class=&o&&++&/span&&span class=&p&&;&/span&
&span class=&p&&}&/span&
&span class=&p&&}&/span&
&span class=&n&&sum&/span& &span class=&o&&=&/span& &span class=&n&&sum&/span& &span class=&o&&%&/span& &span class=&mi&&&/span&&span class=&p&&;&/span&
&span class=&n&&printf&/span&&span class=&p&&(&/span&&span class=&s&&&%d&&/span&&span class=&p&&,&/span& &span class=&n&&sum&/span&&span class=&p&&);&/span&
&span class=&k&&return&/span& &span class=&mi&&0&/span&&span class=&p&&;&/span&
&span class=&p&&}&/span&
&span class=&kt&&int&/span& &span class=&nf&&panduan&/span&&span class=&p&&(&/span&&span class=&kt&&int&/span& &span class=&n&&n&/span&&span class=&p&&,&/span& &span class=&kt&&int&/span& &span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&mi&&1001&/span&&span class=&p&&])&/span& &span class=&p&&{&/span&
&span class=&kt&&int&/span& &span class=&n&&i&/span& &span class=&o&&=&/span& &span class=&mi&&1&/span&&span class=&p&&,&/span& &span class=&n&&j&/span&&span class=&p&&;&/span&
&span class=&k&&for&/span& &span class=&p&&(&/span&&span class=&n&&i&/span& &span class=&o&&=&/span& &span class=&mi&&1&/span&&span class=&p&&;&/span& &span class=&n&&i&/span& &span class=&o&&&=&/span& &span class=&n&&n&/span&&span class=&p&&;&/span& &span class=&n&&i&/span&&span class=&o&&++&/span&&span class=&p&&)&/span& &span class=&p&&{&/span&
&span class=&k&&if&/span& &span class=&p&&(&/span&&span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&p&&]&/span& &span class=&o&&!=&/span& &span class=&mi&&0&/span& &span class=&o&&&&&/span& &span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&p&&]&/span& &span class=&o&&!=&/span& &span class=&mi&&1&/span& &span class=&o&&&&&/span& &span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&p&&]&/span& &span class=&o&&!=&/span& &span class=&mi&&2&/span& &span class=&o&&&&&/span& &span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&p&&]&/span& &span class=&o&&!=&/span& &span class=&mi&&3&/span&&span class=&p&&)&/span&
&span class=&k&&return&/span& &span class=&mi&&0&/span&&span class=&p&&;&/span&
&span class=&k&&if&/span& &span class=&p&&(&/span&&span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&p&&]&/span& &span class=&o&&==&/span& &span class=&mi&&1&/span&&span class=&p&&)&/span& &span class=&p&&{&/span&
&span class=&k&&for&/span& &span class=&p&&(&/span&&span class=&n&&j&/span& &span class=&o&&=&/span& &span class=&n&&i&/span& &span class=&o&&+&/span& &span class=&mi&&1&/span&&span class=&p&&;&/span& &span class=&n&&j&/span& &span class=&o&&&=&/span& &span class=&n&&n&/span&&span class=&p&&;&/span& &span class=&n&&j&/span&&span class=&o&&++&/span&&span class=&p&&)&/span& &span class=&p&&{&/span&
&span class=&k&&if&/span& &span class=&p&&(&/span&&span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&n&&j&/span&&span class=&p&&]&/span& &span class=&o&&==&/span& &span class=&mi&&0&/span&&span class=&p&&)&/span&
&span class=&k&&return&/span& &span class=&mi&&0&/span&&span class=&p&&;&/span&
&span class=&p&&}&/span&
&span class=&p&&}&/span&
&span class=&k&&if&/span& &span class=&p&&(&/span&&span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&p&&]&/span& &span class=&o&&==&/span& &span class=&mi&&3&/span&&span class=&p&&)&/span& &span class=&p&&{&/span&
&span class=&k&&for&/span& &span class=&p&&(&/span&&span class=&n&&j&/span& &span class=&o&&=&/span& &span class=&n&&i&/span& &span class=&o&&+&/span& &span class=&mi&&1&/span&&span class=&p&&;&/span& &span class=&n&&j&/span& &span class=&o&&&=&/span& &span class=&n&&n&/span&&span class=&p&&;&/span& &span class=&n&&j&/span&&span class=&o&&++&/span&&span class=&p&&)&/span& &span class=&p&&{&/span&
&span class=&k&&if&/span& &span class=&p&&(&/span&&span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&n&&j&/span&&span class=&p&&]&/span& &span class=&o&&==&/span& &span class=&mi&&2&/span&&span class=&p&&)&/span&
&span class=&k&&return&/span& &span class=&mi&&0&/span&&span class=&p&&;&/span&
&span class=&p&&}&/span&
&span class=&p&&}&/span&
&span class=&p&&}&/span&
&span class=&k&&if&/span& &span class=&p&&(&/span&&span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&mi&&1&/span&&span class=&p&&]&/span& &span class=&o&&==&/span& &span class=&mi&&0&/span&&span class=&p&&)&/span&&span class=&c1&&//第一个数不能为0&/span&
&span class=&k&&return&/span& &span class=&mi&&0&/span&&span class=&p&&;&/span&
&span class=&k&&for&/span& &span class=&p&&(&/span&&span class=&n&&j&/span& &span class=&o&&=&/span& &span class=&mi&&0&/span&&span class=&p&&;&/span& &span class=&n&&j&/span& &span class=&o&&&&/span& &span class=&mi&&4&/span&&span class=&p&&;&/span& &span class=&n&&j&/span&&span class=&o&&++&/span&&span class=&p&&)&/span& &span class=&p&&{&/span&
&span class=&k&&for&/span& &span class=&p&&(&/span&&span class=&n&&i&/span& &span class=&o&&=&/span& &span class=&mi&&1&/span&&span class=&p&&;&/span& &span class=&n&&i&/span& &span class=&o&&&=&/span& &span class=&n&&n&/span&&span class=&p&&;&/span& &span class=&n&&i&/span&&span class=&o&&++&/span&&span class=&p&&)&/span& &span class=&p&&{&/span&
&span class=&k&&if&/span& &span class=&p&&(&/span&&span class=&n&&a&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&p&&]&/span& &span class=&o&&==&/span& &span class=&n&&j&/span&&span class=&p&&)&/span&
&span class=&k&&break&/span&&span class=&p&&;&/span&
&span class=&p&&}&/span&
&span class=&k&&if&/span& &span class=&p&&(&/span&&span class=&n&&i&/span& &span class=&o&&==&/span& &span class=&n&&n&/span& &span class=&o&&+&/span& &span class=&mi&&1&/span&&span class=&p&&)&/span&
&span class=&k&&return&/span& &span class=&mi&&0&/span&&span class=&p&&;&/span&
&span class=&p&&}&/span&
&span class=&k&&return&/span& &span class=&mi&&1&/span&&span class=&p&&;&/span&
&span class=&p&&}&/span&
&/code&&/pre&&/div&&br&&br&但是系统说不对 请问为什么 谢谢！
问题描述　　我们把一个数称为有趣的，当且仅当：　　1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。　　2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。　　3. 最高位数字不为0。　　因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：。　　请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以的余数。输入格式　　输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。输出格式　　输出只有一行，包括恰好n 位的整数中有趣的数的个数除以的余数。样例输入4样例输出3这是题目 我的答案是 #include &stdio.h&
#include &iostream&
#include &math.h&
int main() {
int panduan(int n, int a[1001]);
scanf("%d", &n);
if (n & 4 || n&1000)
int i, j, num, r, e, sum = 0, a[1001];
for (i = 2013; i & pow(10, n); i++)//将i存入a数组
for (j = 1; j &= j++) {
a[j] = num / pow(10, (n - j));
num = num - a[j] * (pow(10, (n - j)));
r = panduan(n, a);
if (r == 1) {
sum = sum % ;
printf("%d", sum);
int panduan(int n, int a[1001]) {
int i = 1,
for (i = 1; i &= i++) {
if (a[i] != 0 && a[i] != 1 && a[i] != 2 && a[i] != 3)
if (a[i] == 1) {
for (j = i + 1; j &= j++) {
if (a[j] == 0)
if (a[i] == 3) {
for (j = i + 1; j &= j++) {
if (a[j] == 2)
if (a[1] == 0)//第一个数不能为0
for (j = 0; j & 4; j++) {
for (i = 1; i &= i++) {
if (a[i] == j)
if (i == n + 1)
#include &iostream&
using namespace std;
int dp[1001][16] = { 0 };
const int prime = ;
int main() {
dp[0][0] = 1;
for (int i = 0; i & n; i++) {
for (int j = 0; j & 16; j++) {
if (dp[i][j] == 0) continue;
if ((j & 2) == 0 && i != 0)
dp[i + 1][j | 1] = (dp[i + 1][j | 1] + dp[i][j]) % prime;
dp[i + 1][j | 2] = (dp[i + 1][j | 2] + dp[i][j]) % prime;
if ((j & 8) == 0)
dp[i + 1][j | 4] = (dp[i + 1][j | 4] + dp[i][j]) % prime;
dp[i + 1][j | 8] = (dp[i + 1][j | 8] + dp[i][j]) % prime;
cout && dp[n][15] && endl;
感觉可以用dp来做AC了的话我再给你分析EDIT: 留意到您的答案中比较有意思的结论答案其实可以枚举 0 和 1 在结果中的数目 i 个（至少 2 个，最多 x - 2 个）此时 2 和 3 的数目就有 x - i 个因为 0 不能开头，所以实际上选择的组合数是个（在除去开头一位以外的位置中选择 i 个位置）且 i 个 "01" 一共有 i - 1 种分配方案（从 1 个 0 到 i - 1 个 0）x - i 个 "23" 一共有 x - i - 1 种分配方案（从 1 个 2 到 x - i - 1 个 2）所以答案可以通过计算总的组合数得到通过对Factorial和Factorial的inverse进行打表，可以快速计算空间复杂度：存放阶乘、自然数的inverse、阶乘的inverse的空间均是O(N)时间复杂度：复杂度是O(N)细节见代码#include &iostream&
#include &cstdio&
using namespace std;
const int maxn = 1001;
int mod = ;
int factorial[maxn], inverse[maxn], inversefactorial[maxn];
inline long long c(int m, int n) {
return 1LL * factorial[m] * inversefactorial[n] % mod
* inversefactorial[m - n] % mod;
int main() {
factorial[0] = factorial[1] = 1;
inverse[0] = inverse[1] = 1;
inversefactorial[0] = inversefactorial[1] = 1;
for (int i = 2; i & maxn; i++) {
factorial[i] = 1LL * factorial[i - 1] * i % mod;
inverse[i] = mod - 1LL * mod / i * inverse[mod % i] % mod;
inversefactorial[i] = 1LL * inversefactorial[i - 1] * inverse[i] % mod;
while (scanf("%d", &x) == 1) {
int ans = 0;
for (int i = 2; i &= x - 2; ++i)
ans = (ans + c(x - 1, i) * (i - 1) * (x - i - 1)) % mod;
cout && ans && endl;
=========== 分割线
===========受
的回答的启发，此题还可以用矩阵乘法来做 容易观察得到结论，字符串必定以2开头把字符串中字符放入一个集合，我们可以统计长度为N，字符集合为S的合法字符串个数他们的关系满足f(1, {2}) = 1
f(1, {0, 2}) = 0
f(1, {2, 3}) = 0
f(1, {0, 1, 2}) = 0
f(1, {0, 2, 3}) = 0
f(1, {0, 1, 2, 3}) = 0
f(N+1, {2}) = f(N, {2})
f(N+1, {0, 2}) = f(N, {0, 2}) * 2 + f(N, {2})
f(N+1, {2, 3}) = f(N, {2}) + f(N, {2, 3})
f(N+1, {0, 1, 2}) = f(N, {0, 1, 2}) * 2 + f(N, {0, 2})
f(N+1, {0, 2, 3}) = f(N, {0, 2, 3}) * 2 + f(N, {0, 2}) + f(N, {2, 3})
f(N+1, {0, 1, 2, 3}) = f(N, {0, 1, 2, 3}) * 2 + f(N, {0, 2, 3}) + f(N, {0, 1, 2})
可以构造矩阵M =
| 1 0 0 0 0 0 |
| 1 2 0 0 0 0 |
| 1 0 1 0 0 0 |
| 0 1 0 2 0 0 |
| 0 1 1 0 2 0 |
| 0 0 0 1 1 2 |
使得| f(N+1, S) | = M * | f(N, S) |
此时答案可以通过矩阵快速幂求解得到 | f(N, S) | = M ^ (n-1) * | f(1, S) |
其中f(N, {0, 1, 2, 3})
枚举01个数，状态压缩DP都可以。&br&&br&不过这不是重点，同学你首先要认识到的一点是“代码是将程序员的解决问题的逻辑思考转化为计算机可以看懂的物理实现”，所以当一个代码没有产生正确的输出时，要么是你的解决问题的“逻辑”错了，要么是你将“逻辑”转化为代码的过程错了。&br&&br&就这个题来说，你的“逻辑”不对，因为计算机平均每秒只能做10^8左右次计算，你要枚举10^1000内的所有数字再去判断可能得计算到宇宙毁灭都计算不完，请参考其它回答了解怎样是解决这个题目的高效率的办法。&br&&br&然后，你的实现也不对，你要了解到C语言中int类型并不是真正意义上的整数，多数情况下它只能表示2^-31~2^31-1内的数。而pow(x,y)也不是真正意义上的实数，多数情况下它只有十多位有效数字的精度。去学习一下二进制相关知识和计算机中数字的表示吧。
枚举01个数，状态压缩DP都可以。不过这不是重点，同学你首先要认识到的一点是“代码是将程序员的解决问题的逻辑思考转化为计算机可以看懂的物理实现”，所以当一个代码没有产生正确的输出时，要么是你的解决问题的“逻辑”错了，要么是你将“逻辑”转化为代…
大体思路就是数位DP，应该也可以推公式计算，先做了数位DP的解法，有时间再去填公式的坑。&br&一共只有6种合法的状态分别是{2},{20},{201},{23},{203},{2031},表示只含这些数码，且满足约束条件，所以我们用dp[N][6]来存，当然因为{2}的个数永远是1，其实也可以用5个状态就可以了。&br&dp[i][j]表示第i长度时，第j状态的数目，然后考察一下状态转移和初始状态就可以了。具体的见代码吧。&br&&div class=&highlight&&&pre&&code class=&language-c&&&span class=&cp&&#include &stdio.h&&/span&
&span class=&k&&typedef&/span& &span class=&kt&&long&/span& &span class=&kt&&long&/span& &span class=&n&&LL&/span&&span class=&p&&;&/span&
&span class=&cp&&#define N
1001&/span&
&span class=&cp&&#define MOD &/span&
&span class=&n&&LL&/span& &span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&N&/span&&span class=&p&&][&/span&&span class=&mi&&6&/span&&span class=&p&&];&/span&
&span class=&n&&LL&/span& &span class=&nf&&solve&/span&&span class=&p&&(&/span&&span class=&kt&&int&/span& &span class=&n&&n&/span&&span class=&p&&){&/span&
&span class=&kt&&int&/span& &span class=&n&&i&/span&&span class=&p&&;&/span&
&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&mi&&4&/span&&span class=&p&&][&/span&&span class=&mi&&0&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&mi&&1&/span&&span class=&p&&;&/span&
&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&mi&&4&/span&&span class=&p&&][&/span&&span class=&mi&&1&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&mi&&7&/span&&span class=&p&&;&/span&
&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&mi&&4&/span&&span class=&p&&][&/span&&span class=&mi&&2&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&mi&&5&/span&&span class=&p&&;&/span&
&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&mi&&4&/span&&span class=&p&&][&/span&&span class=&mi&&3&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&mi&&3&/span&&span class=&p&&;&/span&
&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&mi&&4&/span&&span class=&p&&][&/span&&span class=&mi&&4&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&mi&&9&/span&&span class=&p&&;&/span&
&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&mi&&4&/span&&span class=&p&&][&/span&&span class=&mi&&5&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&mi&&3&/span&&span class=&p&&;&/span&
&span class=&k&&for&/span&&span class=&p&&(&/span&&span class=&n&&i&/span&&span class=&o&&=&/span&&span class=&mi&&5&/span&&span class=&p&&;&/span&&span class=&n&&i&/span&&span class=&o&&&=&/span&&span class=&n&&n&/span&&span class=&p&&;&/span&&span class=&n&&i&/span&&span class=&o&&++&/span&&span class=&p&&){&/span&
&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&p&&][&/span&&span class=&mi&&0&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&mi&&1&/span&&span class=&p&&;&/span&
&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&p&&][&/span&&span class=&mi&&1&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&p&&(&/span&&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&][&/span&&span class=&mi&&0&/span&&span class=&p&&]&/span& &span class=&o&&+&/span& &span class=&mi&&2&/span&&span class=&o&&*&/span&&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&][&/span&&span class=&mi&&1&/span&&span class=&p&&])&/span&&span class=&o&&%&/span&&span class=&n&&MOD&/span&&span class=&p&&;&/span&
&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&p&&][&/span&&span class=&mi&&2&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&p&&(&/span&&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&][&/span&&span class=&mi&&1&/span&&span class=&p&&]&/span& &span class=&o&&+&/span& &span class=&mi&&2&/span&&span class=&o&&*&/span&&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&][&/span&&span class=&mi&&2&/span&&span class=&p&&])&/span&&span class=&o&&%&/span&&span class=&n&&MOD&/span&&span class=&p&&;&/span&
&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&p&&][&/span&&span class=&mi&&3&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&p&&(&/span&&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&][&/span&&span class=&mi&&0&/span&&span class=&p&&]&/span& &span class=&o&&+&/span& &span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&][&/span&&span class=&mi&&3&/span&&span class=&p&&])&/span&&span class=&o&&%&/span&&span class=&n&&MOD&/span&&span class=&p&&;&/span&
&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&p&&][&/span&&span class=&mi&&4&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&p&&(&/span&&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&][&/span&&span class=&mi&&1&/span&&span class=&p&&]&/span& &span class=&o&&+&/span& &span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&][&/span&&span class=&mi&&3&/span&&span class=&p&&]&/span& &span class=&o&&+&/span& &span class=&mi&&2&/span&&span class=&o&&*&/span&&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&][&/span&&span class=&mi&&4&/span&&span class=&p&&])&/span&&span class=&o&&%&/span&&span class=&n&&MOD&/span&&span class=&p&&;&/span&
&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&p&&][&/span&&span class=&mi&&5&/span&&span class=&p&&]&/span& &span class=&o&&=&/span& &span class=&p&&(&/span&&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&][&/span&&span class=&mi&&2&/span&&span class=&p&&]&/span& &span class=&o&&+&/span& &span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&][&/span&&span class=&mi&&4&/span&&span class=&p&&]&/span& &span class=&o&&+&/span& &span class=&mi&&2&/span&&span class=&o&&*&/span&&span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&i&/span&&span class=&o&&-&/span&&span class=&mi&&1&/span&&span class=&p&&][&/span&&span class=&mi&&5&/span&&span class=&p&&])&/span&&span class=&o&&%&/span&&span class=&n&&MOD&/span&&span class=&p&&;&/span&
&span class=&p&&}&/span&
&span class=&k&&return&/span& &span class=&n&&dp&/span&&span class=&p&&[&/span&&span class=&n&&n&/span&&span class=&p&&][&/span&&span class=&mi&&5&/span&&span class=&p&&];&/span&
&span class=&p&&}&/span&
&span class=&kt&&int&/span& &span class=&nf&&main&/span&&span class=&p&&(){&/span&
&span class=&kt&&int&/span& &span class=&n&&n&/span&&span class=&p&&;&/span&
&span class=&n&&scanf&/span&&span class=&p&&(&/span&&span class=&s&&&%d&/span&&span class=&se&&\n&/span&&span class=&s&&&&/span&&span class=&p&&,&/span&&span class=&o&&&&/span&&span class=&n&&n&/span&&span class=&p&&);&/span&
&span class=&n&&printf&/span&&span class=&p&&(&/span&&span class=&s&&&%lld&/span&&span class=&se&&\n&/span&&span class=&s&&&&/span&&span class=&p&&,&/span&&span class=&n&&solve&/span&&span class=&p&&(&/span&&span class=&n&&n&/span&&span class=&p&&));&/span&
&span class=&k&&return&/span& &span class=&mi&&0&/span&&span class=&p&&;&/span&
&span class=&p&&}&/span&
&/code&&/pre&&/div&
大体思路就是数位DP，应该也可以推公式计算，先做了数位DP的解法，有时间再去填公式的坑。一共只有6种合法的状态分别是{2},{20},{201},{23},{203},{2031},表示只含这些数码，且满足约束条件，所以我们用dp[N][6]来存，当然因为{2}的个数永远是1，其实也可以…
已有帐号？
无法登录？
社交帐号登录
码农，ACM爱好者