A
各数位之和模 等于这个数模
。
。
C++
#include "bits/stdc++.h"
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
cout << n % 9 << '\n';
return 0;
}
Python
import sys
input = sys.stdin.readline
print(int(input()) % 9)
B
复数运算。
。
C++
#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
constexpr int P = 1000000007;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
i64 real = 1, imag = 0;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
i64 x = a * real - b * imag, y = a * imag + b * real;
real = (x % P + P) % P, imag = (y % P + P) % P;
}
cout << real << ' ' << imag << '\n';
return 0;
}
Python
import sys
input = sys.stdin.readline
P = 1000000007
n = int(input())
real, imag = 1, 0
for i in range(n):
a, b = map(int, input().split())
x, y = a * real - b * imag, a * imag + b * real
real, imag = (x % P + P) % P, (y % P + P) % P
print(real, imag)
C
。
。
C++
#include "bits/stdc++.h"
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> c(3), primes{2, 3, 5};
for (int i = 0; i < n; i++) {
int x;
cin >> x;
for (int j = 0; j < 3; j++) {
while (x % primes[j] == 0) {
x /= primes[j];
c[j]++;
}
}
}
cout << min({c[0], c[1], c[2]}) << '\n';
return 0;
}
Python
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
c = [0, 0, 0]
for i in range(n):
for j, k in enumerate([2, 3, 5]):
while a[i] % k == 0:
a[i] //= k
c[j] += 1
print(min(c))
D
对 取模的值只和结尾有关，以每个数结尾分别为
次。
。
C++
#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
constexpr int P = 1000000007;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
i64 fac = 1;
for (int i = 2; i < n; i++) {
fac = fac * i % P;
}
i64 ans = 0;
for (int i = 1; i <= n; i++) {
ans = (ans + i % 5) % P;
}
cout << ans * fac % P << '\n';
return 0;
}
Python
import sys
input = sys.stdin.readline
P = 1000000007
n = int(input())
fac = 1
for i in range(2, n):
fac = fac * i % P
ans = 0
for i in range(1, n + 1):
ans = (ans + i % 5) % P
print(ans * fac % P)
E
记 为从数组中取
个数字，和对
取模后的结果为
的方案数。
。
Python
import sys
input = sys.stdin.readline
P, V = 1000000007, 495
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
dpa = [[0 for i in range(V)] for i in range(n + 1)]
dpb = [[0 for i in range(V)] for i in range(n + 1)]
dpa[0][0] = dpb[0][0] = 1
for i in range(n):
for j in range(i, -1, -1):
for k in range(V):
dpa[j + 1][(k + a[i]) % V] = (dpa[j + 1][(k + a[i]) % V] + dpa[j][k]) % P
dpb[j + 1][(k + b[i]) % V] = (dpb[j + 1][(k + b[i]) % V] + dpb[j][k]) % P
for i in range(n):
for j in range(V):
dpb[i + 1][j] = (dpb[i + 1][j] + dpb[i][j]) % P
cnt = [0 for i in range(V)]
for i in range(n + 1):
for j in range(V):
for k in range(V):
cnt[(j + k) % V] = (cnt[(j + k) % V] + dpa[i][j] * dpb[i][k] % P) % P
print(*cnt)
F
一共有 种状态，考虑哪两个状态能拼出
。
这里使用了树状数组。
。
C++
#include "bits/stdc++.h"
using namespace std;
using i64 = int64_t;
template <class T>
struct Fenwick {
int n;
vector<T> a;
Fenwick(int n) : n(n), a(n, T()) {}
void modify(int i, T x) {
for (i++; i <= n; i += i & -i) {
a[i - 1] += x;
}
}
T get(int i) {
T r = T();
for (; i > 0; i -= i & -i) {
r += a[i - 1];
}
return r;
}
T sum(int l, int r) {
return get(r) - get(l);
}
};
vector<int> primes{3, 5, 11};
vector<int> get(int x) {
vector<int> c(3);
for (int i = 0; i < 3; i++) {
while (x % primes[i] == 0) {
x /= primes[i];
c[i]++;
}
}
c[0] = min(c[0], 2), c[1] = min(c[1], 1), c[2] = min(c[2], 1);
return c;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int id = 0;
map<vector<int>, int> mp;
vector<vector<int>> d(12);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
d[id] = {i, j, k};
mp[{i, j, k}] = id++;
}
}
}
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector f(12, Fenwick<int>(n));
for (int i = 0; i < n; i++) {
f[mp[get(a[i])]].modify(i, 1);
}
while (q--) {
int o, x, y;
cin >> o >> x >> y;
x--;
if (o == 1) {
f[mp[get(a[x])]].modify(x, -1);
f[mp[get(y)]].modify(x, 1);
a[x] = y;
} else {
i64 ans = 0;
vector<int> c(12);
for (int i = 0; i < 12; i++) {
c[i] = f[i].sum(x, y);
}
for (int i = 0; i < 12; i++) {
for (int j = i + 1; j < 12; j++) {
if (d[i][0] + d[j][0] > 1 && d[i][1] + d[j][1] && d[i][2] + d[j][2]) {
ans += i64(c[i]) * c[j];
}
}
if (d[i][0] + d[i][0] > 1 && d[i][1] + d[i][1] && d[i][2] + d[i][2]) {
ans += i64(c[i] - 1) * c[i] / 2;
}
}
cout << ans << '\n';
}
}
return 0;
}
Python
import sys
input = sys.stdin.readline
class Fenwick:
def __init__(self, n: int):
self.n = n
self.bit = [0 for i in range(n)]
def add(self, i, v):
i += 1
while i <= self.n:
self.bit[i - 1] += v
i += i & -i
def get(self, i):
r = 0
while i > 0:
r += self.bit[i - 1]
i -= i & -i
return r
def sum(self, l, r):
return self.get(r) - self.get(l)
def get(x):
c = [0, 0, 0]
for i, p in enumerate([3, 5, 11]):
while x % p == 0:
x //= p
c[i] += 1
c[0] = min(c[0], 2)
c[1] = min(c[1], 1)
c[2] = min(c[2], 1)
return tuple(c)
tot = 0
mp = {}
d = [None] * 12
for i in range(3):
for j in range(2):
for k in range(2):
d[tot] = (i, j, k)
mp[(i, j, k)] = tot
tot += 1
n, q = map(int, input().split())
a = list(map(int, input().split()))
f = [Fenwick(n) for _ in range(12)]
for i in range(n):
f[mp[get(a[i])]].add(i, 1)
for _ in range(q):
o, x, y = map(int, input().split())
x -= 1
if o == 1:
f[mp[get(a[x])]].add(x, -1)
f[mp[get(y)]].add(x, 1)
a[x] = y
else:
c = [0 for i in range(12)]
for i in range(12):
c[i] = f[i].sum(x, y)
ans = 0
for i in range(12):
for j in range(i + 1, 12):
if d[i][0] + d[j][0] > 1 and d[i][1] + d[j][1] > 0 and d[i][2] + d[j][2] > 0:
ans += c[i] * c[j]
if d[i][0] + d[i][0] > 1 and d[i][1] + d[i][1] > 0 and d[i][2] + d[i][2] > 0:
ans += (c[i] - 1) * c[i] // 2
print(ans)
京公网安备 11010502036488号