A A * B * C
暴力统计,非法情况剪枝即可.
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
int n;
int main()
{
IOS;
cin >> n;
LL res = 0;
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
{
if(i * j > n) break;
for(int k = 1; k <= n; ++ k)
if(i * j * k <= n) res ++;
else break;
}
cout << res << endl;
}
B A ^ B ^ C
只考虑 (A) 的最低位 (A_{low}) 即可,发现一位数的 (x) 次方的最低位是循环出现的,令循环数位为 (p) ,于是只需计算 (t = B ^ C) mod (p) 和 (A_{low} ^ t) mod (10) 即可.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
int p[10] = { 1, 1, 4, 4, 2, 1, 1, 4, 4, 2 };
int pow_mod(int a, int b, int c)
{
int res = 1;
a = a % c;
while(b)
{
if(b & 1) res = (LL)res * a % c;
a = a * a % c;
b >>= 1;
}
return res;
}
int main()
{
IOS;
int A, B, C;
cin >> A >> B >> C;
A = A % 10;
int t = pow_mod(B, C, p[A]);
if(!t) t = p[A];
cout << pow_mod(A, t, 10) << endl;
return 0;
}
考虑扩展欧拉定理
若 (gcd(a,m) = 1), (a^b equiv a ^ {b ; mod ; varphi(m)} ; (mod ; m))
若 (gcd(a,m) e 1), 且 (varphi(m) > b), (a^b equiv a ^ {b} ; (mod ; m))
若 (gcd(a,m) e 1), 且 (varphi(m) le b),(a^b equiv a ^ {b ; mod ; varphi(m) + varphi(m)} ; (mod ; m))
(varphi(10) = 4), 故可以对 (B^C) mod (4)
#include <iostream>
using namespace std;
typedef long long LL;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int pow_mod(int a, int b, int p)
{
int res = 1;
while(b)
{
if(b & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
b >>= 1;
}
return res;
}
int main()
{
IOS;
int a, b, c;
cin >> a >> b >> c;
int t = pow_mod(b, c, 4);
if(!t) t = 4;
cout << pow_mod(a, t, 10) << endl;
return 0;
}
C String Invasion
从后往前遍历,发现可以修改的就把后面全部修改成当前字母,遍历时记录当前每个字母的出现次数.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
typedef long long LL;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
const int N = 2e5 + 10;
char s[N];
map<int, int> cnt;
int main()
{
scanf("%s", s + 1);
int n = strlen(s + 1);
LL res = 0;
cnt[(int)s[n]] ++;
cnt[(int)s[n - 1]] ++;
for(int i = n - 2; i >= 1; -- i)
if(s[i] == s[i + 1] && s[i] != s[i + 2])
{
res += n - (i + 1) + 1 - cnt[(int)s[i]];
cnt.clear();
cnt[(int)s[i]] = n - i + 1;
}
else cnt[(int)s[i]] ++;
printf("%lld
", res);
return 0;
}
D Sky Reflector
使得 (max{A_i} le min{B_i})
枚举 (A_i) 和 (B_i) 的分界线 (t),(A_i) 只能选 (1) ~ (t) 之间的数, (B_i) 只能选 (t) ~ (k) 之间的数,为了防止重复计算, (A_i) 不能只选择前 (t - 1) 的数
答案即为 (sumlimits_{t = 1}^n(t^n - (t-1)^n) * (k - t + 1)^m)
对于只有一行或者一列的要特判
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
const int P = 998244353;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
int n, m, k;
int pow_mod(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1) res = (LL)res * a % P;
a = (LL)a * a % P;
b >>= 1;
}
return res;
}
int main()
{
IOS;
cin >> n >> m >> k;
if(n == 1 || m == 1)
{
if(n == 1 && m == 1) cout << k << endl;
else if(n == 1) cout << pow_mod(k, m) << endl;
else if(m == 1) cout << pow_mod(k, n) << endl;
}
else
{
LL res = 0;
for(int i = 1; i <= k; ++ i)
{
LL t = ((pow_mod(i, n) - pow_mod(i - 1, n)) % P + P) % P;
res = res + t * pow_mod(k - i + 1, m) % P;
res %= P;
}
cout << res << endl;
}
return 0;
}