华附 11.18

……
做题的时候太慌了……
细节把握得太不好了……

math

Prob.

求 $ \sum_{i=1}^n \sum_{j=1}^m [(i,j)=1] \min\\{\lfloor\tfrac{n}{i}\rfloor,\lfloor\tfrac{m}{j}\rfloor\\} $.

Sol.

分块反演一下即可。
但不用这么麻烦。
注意本题性质，发现其意义为枚举斜率后该斜率表示的直线上的点数。
……简单说来就是问 $ n\times m $ 上有多少个点。

Code

这都要代码？？？

jznumber

Prob.

给 $ n $ 个数 $ \\{a_n\\} $，求有多少种方案使得按位与和为 $ 0 $.

Sol.

之前遇到的时候也是看了题解才懂。
考虑一种特殊的数位DP，令 $ f_k(x) := $ 满足 $ A_i $ 与 $ x $ 前 $ k $ 位按位与和为 $ x $ 且其余位相等的个数。
显然有转移 $ f_k(x) = f_{k-1}(x) + [2^k\not| x]f_{k-1}(x + 2^k) $.
对所求为0的方案数，考虑容斥 $ \sum_x cnt(x)2^{f_{20}(x)} $，其中 $ cnt(x) := (-1)^k, k := x $ 二进制下 $ 1 $ 的个数。
这里的妙处在枚举之前位后假定余下位相等。有空总结一下这种想法。（坑）

忘记输出取模控制。难过。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}    
const int maxn = 1e6 + 5, mod = 1e9 + 7;
long long power(long long a, long long b)
{
    long long ret = 1;
    for(; b; b >>= 1, (a *= a) %= mod) if(b & 1)
        (ret *= a) %= mod;
    return ret;
}
int cnt[1 << 20];
long long a[maxn], f[21][1 << 20];
int main()
{
    freopen("jznumber.in", "r", stdin);
    freopen("jznumber.out", "w", stdout);
    int n; read(n);
    int _max = 1 << 20;
    for(int i = 0; i < n; ++i) read(a[i]), ++f[0][a[i]];
    for(int i = 1; i <= 20; ++i) 
    for(int j = 0; j < _max; ++j)
    {
        (f[i][j] += f[i - 1][j]) %= mod;
        if((j >> (20 - i) & 1) == 0) (f[i][j] += f[i - 1][j + (1 << (20 - i))]) %= mod;
    }
    long long ans = 0; 
    for(int i = 0; i < _max; ++i) (ans += ((cnt[i] = cnt[i >> 1] ^ (i & 1)) == 0 ? 1 : -1) * power(2, f[20][i]) % mod) %= mod;
    if(ans < 0) ans += mod;
    printf("%lld\n", ans);
    return 0;
}

product

Prob.

求 $ \prod_{i=1}^n \prod_{j=1}^m f_{(i,j)} $.

Sol.

考虑枚举 $ d=(i,j) $，有

$$ \begin{align} f(d) &= \sum_{1\le i\le n, 1 \le j \le m} [(i,j)=d] \\\\ &= \sum_{1\le i\le \lfloor\tfrac{n}{d}\rfloor, 1\le j\le \lfloor\tfrac{m}{d}\rfloor} [(i,j)=1]\\\\ &= \sum_{1\le i\le \lfloor\tfrac{n}{d}\rfloor, 1\le j\le \lfloor\tfrac{m}{d}\rfloor} \sum_{d'|(i,j)} \mu(d') \\\\ &= \sum_{d'=1}^{\lfloor\tfrac{n}{d}\rfloor} \mu(d') \lfloor\tfrac{n}{\lfloor\tfrac{n}{d}\rfloor}\rfloor \lfloor\tfrac{m}{\lfloor\tfrac{m}{d}\rfloor}\rfloor \\\\ \end{align} $$

用下取整函数的分段性质。