报数 （黄）
小清新筛子签到题
点击查看代码
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#define ff fflush(stdout)
using namespace std;
typedef long long ll;
int read() {
int x = 0;
char c;
bool f = 0;
while (!isdigit(c = getchar())) {
if (c == '-') f = 1;
}
do {
x = (x << 1) + (x << 3) + (c ^ 48);
} while (isdigit(c = getchar()));
if (f) return -x;
return x;
}
const int maxn = 1e7 + 3, mod = 1e9 + 7;
bool vis[maxn];
int ans[maxn];
void Euler(int x) { for (int i = x; i < maxn; i += x) vis[i] = 1; }
bool Check(int x) {
while (x) {
if (x % 10 == 7) return 1;
x /= 10;
}
return 0;
}
int main() {
for (int i = 1; i < maxn; ++i) if (Check(i)) Euler(i);
int lst = 0;
for (int i = 1; i < maxn; ++i) {
if (vis[i]) ans[i] = -1;
else ans[lst] = i, lst = i;
}
int T = read();
while (T--) printf("%d\n", ans[read()]);
}
数列 （蓝）
终于不鸽了）
看到数据范围果断乱搞高维 DP
设 \(f[i][j][k][l]\) 表示考虑到数列 \(a\) 中值小于等于 \(i\) 的项，其中有 \(j\) 个值没有确定，\(S\) 的二进制从 \(2 ^ i\) 对应的这一位开始的状态（状压），前面的二进制位有 \(l\) 个 1
这状态出来转移就好搞了
\(f[i + 1][j - u][(k >> 1) + u][l + (k \,\&\, 1)]+=f[i][j][k][u] * C_j^u * v_{i+1}^u\)
试了试用宏写 for 循环，发现非常好用）
点击查看代码
#include <bits/stdc++.h>
#define ff fflush(stdout)
#define fop(x, l, r) for (int x = l; x <= r; ++x)
#define fio(x, r, l) for (int x = r; x >= l; --x)
using namespace std;
typedef long long ll;
int read() {
int x = 0;
char c;
bool f = 0;
while (!isdigit(c = getchar())) {
if (c == '-') f = 1;
}
do {
x = (x << 1) + (x << 3) + (c ^ 48);
} while (isdigit(c = getchar()));
if (f) return -x;
return x;
}
const int maxn = 31, maxm = 101, mod = 998244353;
void Add(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
}
int Pow(ll a, int b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod, b >>= 1;
}
return ans;
}
int f[maxm][maxn][maxn][maxm];
int v[maxm];
int c[maxn][maxn];
int main() {
int n = read(), m = read(), ik = read();
fop(i, 0, m) v[i] = read();
fop(i, 0, maxn - 1) {
c[i][0] = c[i][i] = 1;
fop(j, 1, i - 1) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
fop(i, 0, n) f[0][i][n - i][0] = 1ll * c[n][i] * Pow(v[0], n - i) % mod;
fop(i, 0, m - 1) fop(j, 0, n) fop(k, 0, n) fop(l, 0, ik) fop(u, 0, j) {
Add(f[i + 1][j - u][(k >> 1) + u][l + (k & 1)], 1ll * f[i][j][k][l] * c[j][u] % mod * Pow(v[i + 1], u) % mod);
}
int ans = 0;
fop(k, 0, n) fop(l, 0, ik) {
if (__builtin_popcount(k) + l <= ik) Add(ans, f[m][0][k][l]);
}
printf("%d\n", ans);
}