辽 icp 大连 网站建设,网站建设推广好做吗,Linux网站开发设计,网络管理系统有哪些Codeforces Round 785 (Div. 2) - C. Palindrome Basis
dp(9/100) 题目链接 思路#xff1a;整数划分基础上加一个判断回文的条件 整数划分思路#xff1a;背包容量为n#xff0c;物品有体积为1~n n种#xff0c;每种无数个#xff0c;求使背包恰好装满的方案数——完全背…Codeforces Round 785 (Div. 2) - C. Palindrome Basis
dp(9/100) 题目链接 思路整数划分基础上加一个判断回文的条件 整数划分思路背包容量为n物品有体积为1~n n种每种无数个求使背包恰好装满的方案数——完全背包问题传统的背包问题可能不会恰好装满但此问题中如果背包有空余可以用1补齐所以是一定会装满的
#include bits/stdc.h
// #pragma GCC optimize(3,Ofast,inline)
// #pragma GCC optimize(2)
using namespace std;
typedef long long LL;
#define int LL
const int mod 1e9 7;
const int N 4e4 5;
int f[N];void solve()
{ int n;cin n;cout f[n] endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t 1;cin t;f[0] 1;for (int i 1; i 4e4; i ){string a to_string(i);string b a;reverse(a.begin(), a.end());if(a b)for (int j i; j 4e4; j )f[j] (f[j] f[j - i]) % mod; }while(t -- ) solve(); system(pause);return 0;
}Codeforces Round 113 (Div. 2) - E. Tetrahedron
dp(18/100) 题目链接 走n步的路线数是走n-2步的三倍加上走n-1步的两倍 当走到n-2步到达D点时还可向A B C三个方向走一来一回 例如 f[0] 1(没有走动就在原点路线D f[2] 路线就有 D - A - D; D - B - D D - C - D 走到n-1步到达D点的情况可在当前步向除D以外的另外两点走一步再回到D。 例如 f[3] 路线有 D - A - B - D D - A - C - D D - B - A - D D - B - C -D D - C - A - D D - C- B - D
#include bits/stdc.h
using namespace std;
#define int long long
const int N 1e7 10, mod 1e9 7;
int f[N];void solve()
{int n;cin n;f[0] 1;f[1] 0;for (int i 2; i n; i )f[i] (2 * f[i - 1] 3 * f[i - 2]) % mod;cout f[n] endl;
}signed main()
{int t 1;// cin t;while(t -- ) solve();return 0;
}
