解法1：设置三状态dp，根据状态转移式递推求解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
ll dp[N][3];
int main () {
int n; cin >> n;
// 定义dp状态
// dp[i][0] : 无us子序列的长度为i的字符串的数量
// dp[i][1] : 有u但是无us的长度为i的字符串的数量
// dp[i][2] : 有us子序列的长度为i的字符串的数量
dp[1][0] = 25;
dp[1][1] = 1;
dp[1][2] = 0;
ll ans = 0;
// 状态转移
for (int i = 2; i <= n; i++) {
//在前i-1个字符无us的基础上 + 除u以外的任意字符(25个)
dp[i][0] = (dp[i - 1][0] * 25) % mod;
//在前i-1个字符无us的基础上 + 一个u字符(1个)
//或在前i-1个字符有u无us的基础上 + 除s以外的任意字符(25个)
dp[i][1] = (dp[i - 1][0] * 1 + dp[i - 1][1] * 25) % mod;
//在前i-1个字符有u无us的基础上 + 一个s字符(1个)
//或在前i-1个字符有us的基础上 + 任意字符(26个)
dp[i][2] = (dp[i - 1][1] * 1 + dp[i - 1][2] * 26) % mod;
// 累加各长度的数量
ans = (ans + dp[i][2]) % mod;
}
cout << ans << endl;
return 0;
}
解法2：
组合数求解，反向推导
先求不存在us的情况，由 所有情况 - 不存在us的情况 得到解
不存在的情况：
1）没有s， 则必定不存在us，pow(25, n)
2）有s，且s前面没u，则必定不存在us
倒数第一位是s，其他位置不能是u，pow(25, n - 1)
倒数第二位是s，s前面的位置不能是u，s后面考虑到和之前的情况冲突，不能是s， pow(25, n - 1)
倒数第三位是s，s前面的位置不能是u，s后面依旧不能是s，pow(25, n - 1)
……
第一位是s，s后面均不能为s，pow(25, n - 1)
所以：pow(25, n - 1) * n
不存在us的总结果： pow(25, n) + pow(25, n - 1) * n
综合：ans = pow(26, n) - pow(25, n) - pow(25, n - 1) * n
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll qpow(ll a, int b) {
ll ans = 1L;
while (b) {
if (b & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
int main() {
int n; scanf("%d", &n);
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans = (ans + (qpow(26, i) - qpow(25, i - 1) * i - qpow(25, i)) % mod) % mod;
}
cout << (ans + mod) % mod << endl;
return 0;
}
解法1：
#include<bits/stdc++.h>
using namespace std;
int main() {
int n; scanf("%d", &n);
if (n == 0) {
printf("(\n");
return 0;
}
int l = (int) sqrt(n); // 左边
for (int i = 0; i < l; i++) putchar('(');
int r = n / l; // 右边
if (l * r == n) {
for (int i = 0; i < r; i++) putchar(')');
puts("");
}
else {
int rem = n % l; // rem补充括号
// 比如 7 = 2 * 3 + 1 : (())()
// 将一个左括号补充在倒数第一个右括号的左边，就能补充1对括号
for (int i = 0; i < r - rem; i++) putchar(')');
putchar('('); // 补充 rem 对括号
for (int i = 0; i < rem; i++) putchar(')');
puts("");
}
return 0;
}
解法2：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; scanf("%d", &n);
int l = n / 50000; // n <= 100000, 直接对半分，暴力构造
for (int i = 1; i <= l; i++) printf("(");
int rem = n % 50000;
for (int i = 1; i <= 50000; i++) {
if (i == 50000 - rem + 1) printf("(");
printf(")");
}
return 0;
}
I - 限制不互素对的排列
思路：
由于每个排列种[n / 2]个偶数，如果k < n / 2是可以找到k+1个偶数，组成k对gcd>1，而如果k = = n / 2是只能找到k个偶数，找不到k+1个偶数的，但是对于6，是可以单独提出来配合3组成一对gcd>1的。
如果 k < n / 2，可以直接从2依次输出k+1个偶数（这k+1个数可以组成k对gcd>1），接着从1开始将其他数都输出即可；
如果 k == n / 2，可以直接从2依次输出k-1个偶数（不包括6），然后输出6和3，接着从1开始将其他数都输出即可。
特殊情况n < 6 && k = = n / 2 时无解（可以自行论证）
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
bool vis[maxn];
int main() {
int n, k; cin >> n >> k;
if (n <= 5 && k == n / 2) cout << "-1" << endl;
else {
if (k == n / 2) {
int x = 2;
while (k--) {
if (x != 6) {
cout << x << " ";
vis[x] = true;
}
x += 2;
}
cout << "6 3 ";
vis[6] = vis[3] = true;
for (int i = 1; i <= n; i++) {
if (!vis[i]) cout << i << " ";
}
cout << endl;
}
else {
k++;
int x = 2;
while (k--) {
cout << x << " ";
vis[x] = true;
x += 2;
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) cout << i << " ";
}
cout << endl;
}
}
return 0;
}
J - 一群小青蛙呱蹦呱蹦呱
思路：
2将所有2^k去掉
3将所有3^k去掉
5将所有5^k去掉
…
保留下来的数字符合的条件为：具有两种以上不同的质因子
对保留下来的数求lcm，假定保留下来的数为
p1 ^ a1 * p2 ^ a2 * p3 ^ a3 … * pn ^ an （pi为质因子）
p1 ^ b1 * p2 ^ b2 * p3 ^ b3 … * pn ^bn
p1 ^ c1 * p2 ^ c2 * p3 ^ c3 … * pn ^ cn
…
则对他们求lcm，结果为 p1 ^ max(a1,b1,) * p2 ^ max(a2,b2,),* pn ^ max(an,bn,)
所以只需要求得各个质数pi的最大幂即可，即对a * pi ^ k <= n 求最大k (因为留下来的数至少需要两种不同质因子，所以a也是质数)。
对于 pi == 2时， a * 2 ^ k <= n, 为使得k最大，则应将a = 3，
所以有：3 * 2 ^ k <= n，即 k = log_2_[n / 3]；
对于 pi > 2 时， a * pi ^ k <= n, 为使得k最大，则应将a = 2，所以有：2 * pi ^ k <= n，即 k = log_pi_[n / 2]；
ps ： 由于需要至少两种不同质数，所以 pi <= n / 2，且需要对2~n/2线性筛打表。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 8e7 + 1000;
//N不能等于n,数组开不下,题目质数 p <= n / 2, N = n / 2足够使用
const int mod = 1e9 + 7;
bool is_prime[N];
ll prime[N], cnt = 0;
void get_prime() { //不能传入n, n <= 1.6*10^8, n是有可能大于N的
for (int i = 2; i < N; i++) { // 注意边界,不能等于N,避免数组越界
if (!is_prime[i]) prime[cnt++] = i;
for (int j = 0; j < cnt && i * prime[j] < N; j++) {
is_prime[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
}
int main() {
int n; cin >> n;
if (n < 6) {
cout << "empty" << endl;
return 0;
}
get_prime();
// 3 * 2 ^ k <= n; k = log_2_[n/3];
ll ans = 1, t = 1, p = 2;
while (t * p <= n / 3) t *= p;
ans = (ans * t) % mod;
// 2 * pi ^ k <= n; k = log_pi_[n/2];
for (int i = 1; prime[i] <= n / 2; i++) {
p = prime[i], t = 1;
while (t * p <= n / 2) t *= p;
ans = (ans * t) % mod;
}
cout << (ans + mod) % mod << endl;
return 0;
}
未完待续