水。
枚举每个点，暴力判断。
LL Find(LL x, LL y){
LL cnt1 = 0, cnt2 = 0;
LL t1 = x, t2 = y;
while (t1 >= 1 && t2 >= 1 && t1 <= H && t2 <= W){
if (G[t1][t2] != '#')
break;
++ cnt1;
t1 --, t2 --;
}
t1 = x, t2 = y;
while (t1 >= 1 && t2 >= 1 && t1 <= H && t2 <= W){
if (G[t1][t2] != '#')
break;
++ cnt1;
t1 ++, t2 ++;
}
cnt1 --;
t1 = x, t2 = y;
while (t1 >= 1 && t2 >= 1 && t1 <= H && t2 <= W){
if (G[t1][t2] != '#')
break;
++ cnt2;
t1 --, t2 ++;
}
t1 = x, t2 = y;
while (t1 >= 1 && t2 >= 1 && t1 <= H && t2 <= W){
if (G[t1][t2] != '#')
break;
++ cnt2;
t1 ++, t2 --;
}
cnt2 --;
return min(cnt1, cnt2);
}
int main(){
Fcin;
cin >> H >> W;
for (LL i = 1; i <= H; i ++){
for (LL j = 1; j <= W; j ++){
cin >> G[i][j];
}
}
for (LL i = 1; i <= H; i ++){
for (LL j = 1; j <= W; j ++){
cnt[Find(i, j) / 2] ++;
}
}
for (LL i = 1; i <= min(H, W); i ++)
cout << cnt[i] << " ";
return 0;
}
因为 所以 最大可为 , 而 最大为 。枚举 再计数 即可。
而质数表的大小即为 的最值。 最小为 时， 最大为 约是 ，
LL Is[M], Len = 0, Prim[M];
void Init(){
Is[1] = 1;
for (LL i = 2; i <= (LL)1e6; i ++){
if (Is[i] == 0)
Prim[++ Len] = i;
for (LL j = 1; j <= Len && Prim[j] * i <= (LL)1e6; j ++){
Is[Prim[j] * i] = 1;
if (i % Prim[j] == 0)
break;
}
}
return ;
}
bool check(LL x){
if (x == 1)
return 0;
if (x == 2 || x == 3)
return 1;
for (LL i = 2; i * i <= x; i ++)
if (x % i == 0)
return 0;
return 1;
}
// ...
LL LimitA = (LL)pow(n, 0.2);
for (LL i = 1; Prim[i] <= LimitA; i ++){
LL LimitB = (LL)pow(n / Prim[i] / Prim[i], 0.33334);
for (LL j = i + 1; Prim[j] <= LimitB; j ++){
for (LL k = j + 1; Prim[k] * Prim[k] * Prim[i] * Prim[i] * Prim[j] <= n; k ++){
++ Ans;
}
}
}
显然，设 为从 变为 的概率，那么 。
所以直接记忆化搜索，记忆化用 map。
除法用快速幂求逆元即可。
map<LL, LL> mp;
LL Qpow(LL x, LL k, LL p){
LL tmp = x, res = 1;
while (k){
if (k & 1)
res = (res * tmp) % p;
tmp = (tmp * tmp) % p;
k >>= 1;
}
return res;
}
LL Inv(LL x, LL p){
return Qpow(x, p - 2, p);
}
LL DFS(LL x){
if (mp.count(x))
return mp[x];
if (x == n)
return 1;
if (x > n)
return 0;
LL res = 0;
for (LL i = 2; i <= 6; i ++)
res += DFS(x * i);
LL t = res * Inv5 % MOD;
mp[x] = t;
return t;
}
int main(){
Fcin;
cin >> n;
Inv5 = Inv(5, MOD);
cout << DFS(1);
return 0;
}