来晚了，补一下题。
A.小红取模
直接模拟即可。
void solve(){
string str;
cin >> str;
i64 res = 0;
for (int i = 0;i < str.size();i ++) res = (res + str[i] - '0') % 9;
cout << res << "\n";
}
B.小红的复数
同理，直接模拟即可，这里直接使用自己的模板了。
void solve(){
int n;cin >> n;
Complex<Z> res = {1,0};
for (int i = 1;i <= n;i ++){
Complex<Z> c;
cin >> c.real >> c.imag;
res *= c;
}
cout << res << "\n";
}
C.小红的k次方
质因数分解，只需统计质因子 这三个因子的个数即可。
void solve(){
int n;cin >> n;
vector<int> a(n);
for (int i = 0;i < n;i ++) cin >> a[i];
int c2 = 0,c3 = 0,c5 = 0;
for (int i = 0;i < n;i ++){
while(a[i] % 2 == 0) c2 ++,a[i] /= 2;
while(a[i] % 3 == 0) c3 ++,a[i] /= 3;
while(a[i] % 5 == 0) c5 ++,a[i] /= 5;
}
cout << min({c2,c3,c5}) << "\n";
}
D.小红模5
对于拼接，我们可以理解成每个数字乘上 再相加，可以发现在
意义下，只有末位有贡献。
只需计算对于每个元素作为末尾元素时的贡献即可，即
void solve(){
int n;cin >> n;
Z cnt = comb.A(n-1,n-1); // 组合数模板类
Z ans = 0;
for (int i = 1;i <= n;i ++){
ans += cnt * (i % 5);
}
cout << ans << "\n";
}
E.二小姐取数
考虑 dp，记 为当前余数为
下，选的
中的元素比
多了
个情况下的方案数。
然后就可以暴力转移了。
void solve(){
int n;cin >> n;
int m = 495;
vector<int> a(n),b(n);
for (int i = 0;i < n;i ++) cin >> a[i],a[i] %= m;
for (int i = 0;i < n;i ++) cin >> b[i],b[i] %= m;
vector<vector<Z>> dp(m,vector<Z>(n+1));
dp[0][0] = 1;
for (int i = 0;i < n;i ++){
auto dp2 = dp;
for(int d = 0;d < m;d ++){
for (int j = 0;j <= i;j ++){
dp2[(a[i] + d) % m][j+1] += dp[d][j];
}
}
swap(dp,dp2);
}
for (int i = 0;i < n;i ++){
auto dp2 = dp;
for(int d = 0;d < m;d ++){
for (int j = 1;j <= n;j ++){
dp2[(b[i] + d) % m][j-1] += dp[d][j];
}
}
swap(dp2,dp);
}
for (int d = 0;d < m;d ++){
cout << accumulate(dp[d].begin(),dp[d].end(),Z(0)) << " \n"[d==m-1];
}
}
F.二小姐的区间查询
将 质因数分解，可以发现是
，然后可以发现对结果有贡献的情况最多
种。
我们只需将这 种数字两两匹配求方案即可。
然后可以用树状数组或者线段树维护数量，直接查询即可。
注意：直接存 个余数的数量可能会 TLE。
时间复杂度为
代码写得有点烂，见谅。
void solve(){
int n,q;
cin >> n >> q;
vector<int> a(n+1);
for (int i = 1;i <= n;i ++) cin >> a[i];
int mod = 495;
vector<int> p = {1};
for (int x : {3,3,5,11}){
int sz = p.size();
for (int i = 0;i < sz;i ++){
p.push_back(p[i] * x);
}
}
ranges::sort(p);
p.erase(unique(begin(p),end(p)),end(p));
int sz = p.size();
cerr << sz << "\n";
vector<Fenwick<int>> tr(sz,Fenwick<int>(n));
auto fac = [](int x)->int{
int res = 1;
for (int y : {3,3,5,11}){
if (x % y == 0){
x /= y,res *= y;
}
}
return res;
};
vector<int> mp(mod);
for (int i = 0;i < mod;i ++) mp[i] = lower_bound(p.begin(),p.end(),fac(i))-p.begin();
for (int i = 1;i <= n;i ++) tr[mp[a[i] % mod]].add(i,1);
for (int _ = 1;_ <= q;_ ++){
int opt,l,r;cin >> opt >> l >> r;
if (opt == 2){
i64 res = 0;
for (int x : p){
for (int y : p){
if (y > x) break;
if ((x * y) % mod == 0){
i64 add = 0;
if (x == y) {
i64 c = tr[mp[x%mod]][r] - tr[mp[x%mod]][l-1];
add += c * (c - 1) / 2;
} else {
i64 c1 = tr[mp[x%mod]][r] - tr[mp[x%mod]][l-1];
i64 c2 = tr[mp[y%mod]][r] - tr[mp[y%mod]][l-1];
add += c1 * c2;
}
res += add;
}
}
}
cout << res << "\n";
} else {
tr[mp[(a[l] % mod)]].add(l,-1);
a[l] = r;
tr[mp[(a[l] % mod)]].add(l,1);
}
}
}
用到的模板
ModInt 和组合数(Combination)
template <long long MOD>
struct ModInt{
long long val = 0;
ModInt(long long x = 0):val(norm(x)){}
long long operator()(){ return val; }
constexpr ModInt operator-(){
return ModInt(MOD - val);
}
constexpr ModInt operator~(){
assert(val != 0);
return Pow(val,MOD-2);
}
constexpr ModInt& operator+=(ModInt x){
return val += x(),val = norm(val),*this;
}
constexpr ModInt& operator-=(ModInt x){
return val -= x(),val = norm(val),*this;
}
constexpr ModInt& operator*=(ModInt x){
return val *= x(),val = norm(val),*this;
}
constexpr ModInt& operator/=(ModInt x){
return val *= (~x)(),val = norm(val),*this;
}
constexpr ModInt& operator^=(long long y){
return val = Pow(*this,y)(),*this;
}
constexpr ModInt& operator++(){
return val ++,val = norm(val),*this;
}
constexpr ModInt operator++(int){
ModInt v = *this;
return val ++,val = norm(val),v;
}
constexpr ModInt& operator--(){
return val --,val = norm(val),*this;
}
constexpr ModInt operator--(int){
ModInt v = *this;
return val --,val = norm(val),v;
}
constexpr friend ModInt operator+(ModInt x, ModInt y){
return x += y;
}
constexpr friend ModInt operator-(ModInt x, ModInt y){
return x -= y;
}
constexpr friend ModInt operator*(ModInt x, ModInt y){
return x *= y;
}
constexpr friend ModInt operator/(ModInt x, ModInt y){
return x /= y;
}
constexpr friend ModInt operator^(ModInt x, long long y){
return x ^= y;
}
constexpr friend std::ostream& operator<<(std::ostream& os,ModInt x){
return os << x();
}
constexpr friend std::istream& operator>>(std::istream& is,ModInt &x){
is >> x.val, x.val = norm(x.val);
return is;
}
constexpr static long long norm(long long x){ return (x%MOD+MOD)%MOD;}
constexpr static ModInt Pow(ModInt x,long long y){
ModInt ans = 1;
for (;y; y >>= 1,x *= x)
if (y & 1) ans *= x;
return ans;
}
};
template <long long MOD>
struct Combination{
int siz = 0;
using Z = ModInt<MOD>;
std::vector<Z> fact,inv;
Combination():siz(1),fact(1,1),inv(1,1){}
void expend(int size){
if (siz >= size) return;
fact.resize(size),inv.resize(size);
for (int i = siz;i < size;i++) fact[i] = fact[i-1] * i;
inv[size-1] = 1 / fact[size-1];
for (int i = size - 2;i >= siz;i--) inv[i] = inv[i+1] * (i+1);
siz = size;
}
void check(int size){
if (siz >= size) return;
int n = siz;
while(n < size) n <<= 1;
n = std::min<unsigned int>(n,MOD);
expend(n);
}
Z A(int n,int m){
if (n < 0 || m < 0 || n < m) return 0;
check(n+1);
return fact[n]*fact[n-m];
}
Z C(int n,int m){
if (n < 0 || m < 0 || n < m) return 0;
if (n < MOD && m < MOD) {
check(n+1);
return fact[n] * inv[m] * inv[n - m];
} else return C(n/MOD,m/MOD)*C(n%MOD,m%MOD);
}
};
using CB = Combination<1000000007>;
复数(Complex)
template<typename T>
struct Complex{
T real,imag;
Complex(T x = 0,T y = 0):real(x),imag(y){}
constexpr Complex& operator+=(const Complex &x){
real += x.real,imag += x.imag;
return *this;
}
constexpr Complex& operator-=(const Complex &x){
real -= x.real,imag -= x.imag;
return *this;
}
constexpr Complex& operator*=(const Complex &x){
T rl = real * x.real - imag * x.imag;
imag = x.imag * real + x.real * imag;
real = rl;
return *this;
}
constexpr Complex& operator/=(const Complex &x){
T div = x.real * x.real + x.imag * x.imag;
T rl = (real*x.real+imag*x.imag) / div;
imag = (x.real * imag - real * x.imag) / div;
real = rl;
return *this;
}
constexpr friend Complex operator+(const Complex& x,const Complex y){
Complex r = x;
return (r += y);
}
constexpr friend Complex operator-(const Complex& x,const Complex y){
Complex r = x;
return (r -= y);
}
constexpr friend Complex operator*(const Complex& x,const Complex y){
Complex r = x;
return (r *= y);
}
constexpr friend Complex operator/(const Complex& x,const Complex y){
Complex r = x;
return (r /= y);
}
constexpr friend std::ostream& operator<<(ostream& os,Complex x){
return os << x.real << " " << x.imag;
}
constexpr friend std::istream& operator>>(ostream& is,Complex& x){
return is >> x.real >> x.imag;
}
constexpr static Complex Pow(Complex x,long long p){
Complex res = {1,0};
for (;p;p >>= 1,x *= x){
if (p&1) res *= x;
}
return res;
}
};
树状数组(Fenwick)
template<typename T>
struct Fenwick{
std::vector<T> value;
int size = 0;
Fenwick(int n = 0):size(n+1){
value.assign(size,T(0));
}
void add(int i,T x){
for (;i < size;i += i&(-i)) value[i] += x;
}
void remove(int i,T x){
for (;i < size;i += i&(-i)) value[i] -= x;
}
T presum(int i) const {
T ans = 0;
for (;i;i -= i & (-i)) ans += value[i];
return ans;
}
T operator[](const int i) const {
return presum(i);
}
};
京公网安备 11010502036488号