1957(div2)

A. Stickogon

给你长度为 $a_1,a_2,\dots ,a_n$ 的木条 $n$ 根。求你能同时拼出的正多边形（等边）的最大数量，使得：

• 多边形的每条边都正好由一根木棒组成。
• 多边形中使用的小棒不超过 $1$ 根。

注意：木棒不能折断。

忘记将 n 修改为 100 了

void solve() {
    int n;cin >> n;vector<int> a(110);
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;a[x]++;
    }
    int cnt = 0;
    for (int i = 1;i <= 100;i++) {
        cnt += a[i] / 3;
    }
    cout << cnt << '\n';
}

B. A BIT of a Construction

给定整数 $n$ 和 $k$ ，构造一个由 $n$ 非负数（即 $\ge 0$ ）整数 $a_1,a_2,\dots ,a_n$ 组成的序列，使得

1. $\sum _{i=1}^n{a}_i=k$
2. 使 $a_1|a_2|\dots |a_n$ 的二进制表示中 $1$ 的个数最大。

void solve() {
    int n, k;cin >> n >> k;
    if (n == 1) {
        cout << k << "\n";return;
    }
    bitset<32> b(k);
    int x = 0;
    for (int i = 31;i >= 0;i--) {
        if (b[i]) {
            x = (1ll << i);break;
        }
    }
    x--;
    int y = k - x;
    cout << x << " " << y << " ";
    for (int i = 2;i < n;i++)cout << "0 ";
    cout << '\n';
}

C . How Does the Rook Move?

给您一个 $n\times n$ 棋盘，您和电脑轮流在棋盘上分别放置白车和黑车。在放置车的过程中，您必须确保没有两只车互相攻击。如果两只车共用同一行或同一列，则无论颜色如何，都会互相攻击。

有效的一步棋是将一只车放在一个位置（ $r$ ， $c$ ）上，使它不会攻击任何其他车。

你先开始，当你在自己的回合中走了一步有效的棋，将白车置于位置（ $r$ ， $c$ ）时，电脑会照搬你的棋，在它的回合中将黑车置于位置（ $c$ ， $r$ ）。如果是 $r=c$ ，那么电脑就无法映射你的棋步，并跳过它的回合。

您已经与计算机下了 $k$ 步棋（计算机也会尝试复制这些棋步），您必须继续下棋直到没有剩余的有效棋步为止。在下完 $k$ 步之后，如果继续下棋，最终会有多少种不同的配置？可以保证 $k$ 步和隐含的计算机步都是有效的。由于答案可能较大，请打印出 ${10}^9+7$ 的模数。

如果存在一个坐标（ $r$ ， $c$ ），其中一个配置中有一个车，而另一个配置中没有，或者坐标上的车的颜色不同，那么这两个配置就被认为是不同的。

Solution

组合数学/DP

法一：DP 转移方程：f[i] = f[i - 1] + f[i - 2] * 2 * (i - 1)

若从后往前推：

对于棋下在对角线上时，选择 $(i,i)$ 这时消耗了 $1r\times 1l$ 则贡献为 $f[i-1]$

若没有下在对角线上：选定该行 $i(row)$ 后，则列可以在前面 $(i-1)$ 个位置任意挑选，列 $i(line)$ 同理，消耗 $2r\times 2l$，则贡献为 $2(i-1)f[i-2]$

#define int long long
constexpr int mod = 1e9 + 7;
int f[300010];
void solve() {
    int n, k;cin >> n >> k;int cnt = n;
    for (int i = 1;i <= k;i++) {
        int x, y;cin >> x >> y;cnt -= 2 - (x == y);
    }
    cout << f[cnt] << '\n';
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    f[0] = 1;f[1] = 1;f[2] = 3;
    for (int i = 3;i <= 3e5;i++) {
        f[i] = f[i - 1] + f[i - 2] * 2 * (i - 1);f[i] %= mod;
    }
    int _ = 1;
    cin >> _;
    while (_--)
        solve();
}

组合数学：

$C_n^m=\frac{n!}{(n-m)!\times m!}$

$cnt$ 代表可用的行列数，则： $ans=\sum _{i=0}^{cnt/2}(C_{cnt}^{2i}\times C_{2i}^i\times i!)\equiv \sum _{i=0}^{cnt/2}\left(\frac{cnt!}{(cnt-2i)!\times i!}\right)=\sum _{i=0}^{cnt/2}(C_{cnt}^{2i}\times \frac{2i!}{i!})$

不懂是如何推出的 $\dots$

#define int long long
constexpr int mod = 1e9 + 7;
int fac[300010];
int inv(int a, int b = mod - 2) {
    int ans = 1;
    while (b) {
        if (b & 1)ans = (ans * a) % mod;
        a = (a * a) % mod;b >>= 1;
    }
    return ans;
}
int c(int a, int b) {
    return fac[a] * inv(fac[a - b]) % mod * inv(fac[b]) % mod;
}
void solve() {
    int n, k;cin >> n >> k;int cnt = n;
    for (int i = 1;i <= k;i++) {
        int x, y;cin >> x >> y;cnt -= 2 - (x == y);
    }
    int ans = 0;
    for (int i = 0;i * 2 <= cnt;i++) {
        ans = (ans + c(cnt, 2 * i) * c(2 * i, i) % mod * fac[i]) % mod;
    }
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    fac[0] = fac[1] = 1;
    for (int i = 2;i <= 3e5;i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    int _ = 1;
    cin >> _;
    while (_--)
        solve();
}

D . A BIT of an Inequality

给你一个数组 $a_1,a_2,\dots ,a_n$ 。请找出有多少个图元（ $x,y,z$ ）符合下列条件：

• $1\le x\le y\le z\le n$ , 和
• $f(x,y)\oplus f(y,z)>f(x,z)$ .

定义 $f(l,r)=a_l\oplus a_{l+1}\oplus \dots \oplus a_r$。

Solution

位运算

$f(x,y)\oplus f(y,z)>f(x,z)⟹f(x,z)\oplus a_y>f(x,z)$

设前缀异或为 $s$，$s_i$ 代表前 $i$ 个数进行异或。

则可以将要求简化为求 $s_z\oplus s_{x-1}\oplus a_y>s_z\oplus s_{x-1}$ 的个数。

现在进行分类讨论：设 $s_z,s_{x-1}$ 当前比特位分别为 $r,l_{-1}$，$t$ 代表的是 $a_y$ 最高比特位的值

当 $t=0$ 时：无论 $r,l_{-1}$ 为 $0|1$，$s_z\oplus s_{x-1}$ 的值都不会变

当 $t=1$ 时，若此时 $r,l_{-1}$ 的值不同，则最终的值会变小，否则最终的值会变大

总结：变大的情况只有 $t=1\cap r=l_{-1}=0\text{ or }1$ 时才会出现。

这样对于 $a_i$，只要先找到其最高位为 1 的位置 $(j=\mathrm{\_}\mathrm{\_}lg(a_i))$

由题目可得 $z\in [i,n],x-1\in [0,i-1]$，所以答案就是 $i$ 两边都是 1 的情况加上两边都是 $0$ 的情况。

即 $[i,n]$ 中 1 的数量乘以 $[0,i-1]$ 中 1 的数量加上 $[i,n]$ 中 0 的数量乘以 $[0,i-1]$ 中 0 的数量

1 的数量算出来之后，这个区间 0 的数量就是区间长度减去 1 的数量。

#define int long long
int c[32][100010];
void solve() {
    int n;cin >> n;vector<int> a(n + 1), s(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];s[i] = s[i - 1] ^ a[i];
        for (int j = 0;j <= 30;j++) {
            c[j][i] = c[j][i - 1] + (s[i] >> j & 1);
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        int k = __lg(a[i]);
        ans += (c[k][n] - c[k][i - 1]) * c[k][i - 1];
        ans += (n - i + 1 - (c[k][n] - c[k][i - 1])) * (i - c[k][i - 1]);
    }
    cout << ans << '\n';
}

现在只需要进行预处理：需要得到的是 $f(l,r)=0\text{ or }1(\text{k bit})$，即：从 $l$ 到 $r$ 的元素的第 $k$ 位一起异或起来是 $0$ 还是 1

这里需要处理其前缀与后缀：(官方题解)

pre[i][j][k = 0] 代表 $a[1\sim j]$ 个数的第 $i$ 位是 $0$ 的个数，$k=1$ 同理。

suf[i][j][k = 0] 代表 $a[n\sim j]$ 个数的第 $i$ 位是 $0$ 的个数，$k=1$ 同理。

注意：由于这里没有错位的进行前缀与后缀计算，所以在对 $a_i$ 进行操作时，需要将 $a_i$ 归于

constexpr int Z = 30, MAX_N = 1e5 + 3;
int pref[Z][MAX_N][2];
int suff[Z][MAX_N][2];

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < Z; i++) suff[i][n + 1][0] = suff[i][n + 1][1] = 0;
    for (int i = 0; i < Z; i++) {
        for (int j = 1; j <= n; j++) {
            int t = (a[j] >> i) & 1;
            for (int k = 0; k < 2; k++) pref[i][j][k] = (t == k) + pref[i][j - 1][k ^ t];
        }
        for (int j = n; j >= 1; j--) {
            int t = (a[j] >> i) & 1;
            for (int k = 0; k < 2; k++) suff[i][j][k] = (t == k) + suff[i][j + 1][k ^ t];
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int z = __lg(a[i]); // <-> 31 - __builtin_clz(a[i])
        ans += 1ll * pref[z][i - 1][1] * (1 + suff[z][i + 1][0]);
        ans += 1ll * (1 + pref[z][i - 1][0]) * suff[z][i + 1][1];
    }
    cout << ans << "\n";
}

E. Carousel of Combinations

给你一个整数 $n$ 。函数 $C(i,k)$ 表示从集合 { $1,2,\dots ,i$ } 中选择 $k$ 个不同的数字并将它们围成一个圆圈 ${}^{†}$ 的不同方法的数目。

求

由于这个值可能非常大，因此求它的模数 ${10}^9+7$ 。

Solution

威尔逊定理

容易知道 $C(i,j)=Comb(i,j)\times (j-1)!=\frac{i!}{(i-j)!\times j}=\frac{i(i-1)(i-2)\dots (i-j+1)}{j}$

可以知道的是 $n\dots (n-j+1)$ 有 $j$ 项，由于是连续的 $j$ 个数，每个数对 $j$ 的 模数一定不一样 $(0\sim j-1)$，其中一定有一项能够被 $j$ 整除($0(\mathrm{mod}j)$)，至于其他项则构成了 $(j-1)!$

$⟹C(i,j)=(j-1)!\times \lfloor \frac{i}{j}\rfloor (\mathrm{mod}j)$

$\text{wilson}$ 定理：对于素数 $p$，$(p-1)!\equiv (p)-1(\mathrm{mod}p)$，对于合数 $(p\ne 4)$，$(p-1)!\equiv 0(\mathrm{mod}p)$

这里利用差分数组 $d$，对于位置 $i(i=k\times j,k=1,2,3\dots )$，则要使得 $\lfloor \frac{i}{j}\rfloor$ 的结果相同，$i\in [kj,kj+j-1]$ 即 $[i,i+j-1]$ 位置的贡献 $(\lfloor \frac{i}{j}\rfloor )$ 和 $i$ 位置相同，直到 $[i+j]$ 才使得 $\lfloor \frac{i}{j}\rfloor$ 增加了 1，所以在 $i$ 位置加上对应贡献，在 $[i+j]$ 位置减去相应贡献，这样，对 $d$ 数组进行前缀和后就能够计算出每个位置正确的贡献，对答案而言，是 $[1,n]$ 的贡献之和，所以还需要对 $d$ 数组再进行一次前缀和则就是对应的答案。

#define int long long
constexpr int N = 1e6, mod = 1e9 + 7;
int vis[N + 10], pri[N + 10], isp[N + 10];//判断是否是素数
int d[N + 10];
void init(int n) {//线性筛
    int cnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            pri[cnt++] = i;isp[i] = 1;
        }
        for (int j = 0; j < cnt; ++j) {
            if (i * pri[j] > n) break;
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
        }
    }
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    init(N);
    for (int j = 2;j <= N;j++) {
        if (j == 4 || isp[j]) {
            int v = (j == 4 ? 2 : j - 1);
            for (int i = j;i <= N;i += j) {//枚举j的倍数
                int t = v * (i / j) % j;
                d[i] = (d[i] + t) % mod;
                if (i + j <= N)d[i + j] = (d[i + j] - t + mod) % mod;
            }
        }
    }
    for (int i = 1;i <= N;i++)d[i] = (d[i] + d[i - 1]) % mod;
    for (int i = 1;i <= N;i++)d[i] = (d[i] + d[i - 1]) % mod;
    int _;cin >> _;
    while (_--) {
        int n;cin >> n;cout << d[n] << '\n';
    }
}