Sep 1, 2019 由 小羊
就考察一下你是不是真的理解了拓展欧拉定理。
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 1e6+5;
int pri[MAXN], pcn, phi[MAXN];
bool isnp[MAXN];
lld fpow(lld a, lld k, lld m)
{
lld b = 1;
for (; k; k>>=1, a=a*a%m)
if (k&1) b=b*a%m;
return b;
}
bool judge(lld a, lld k, lld m)
{
lld b = 1;
while (k)
{
b = b * a;
if (b >= m) return true;
k--;
}
return false;
}
lld getAns(int a, int b, int m)
{
if (m == 1) return a < m ? 0 : m;
if (b == 0) return 1;
lld t = getAns(a, b-1, phi[m]);
lld ans = fpow(a, t, m);
bool lg = t < phi[m] ? judge(a, t, m) : true;
if (lg) ans += m;
//printf("f(%d,%d,%d)=%lld\n", a, b, m, ans);
return ans;
}
void solve()
{
int a, b, m;
scanf("%d %d %d", &a, &b, &m);
printf("%lld\n", getAns(a,b,m)%m);
}
int main()
{
phi[1] = 1;
for (int i = 2; i < MAXN; i++)
{
if (!isnp[i]) pri[pcn++] = i, phi[i] = i-1;
for (int j = 0; j < pcn; j++)
{
int k = i * pri[j];
if (k >= MAXN) break;
isnp[k] = true;
if (i % pri[j] == 0) { phi[k] = phi[i] * pri[j]; break; }
else phi[k] = phi[i] * (pri[j] - 1);
}
}
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
抄题解。令 ,则有
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 1e5+5;
const int MOD = 998244353, G = 3;
const int SQRT2 = 116195171;
int phi[MAXN], sp[MAXN], qwq[MAXN], A[262144], B[262144];
inline lld fpow(lld a, lld k)
{
lld b = 1;
for (; k; k>>=1, a=a*a%MOD)
if (k & 1) b=b*a%MOD;
return b;
}
inline void init_prime()
{
static int pri[MAXN], pcn;
static bool isnp[MAXN];
phi[1] = sp[0] = 1; sp[1] = fpow(SQRT2, MOD-2);
for (int i = 2; i < MAXN; i++)
{
if (!isnp[i]) pri[pcn++] = i, phi[i] = i-1;
sp[i] = fpow(SQRT2, MOD-1-1ll*i*i%(MOD-1));
for (int j = 0; j < pcn; j++)
{
if (i * pri[j] >= MAXN) break;
isnp[i * pri[j]] = true;
if (i % pri[j] == 0) { phi[i * pri[j]] = phi[i] * pri[j]; break; }
else phi[i * pri[j]] = phi[i] * (pri[j] - 1);
}
}
}
inline void dft(int a[], int DFT, int N)
{
static int rev[262144], wmk[262144];
for (int i = 0; i < N; i++)
rev[i] = (rev[i>>1]>>1)|((i&1)?(N>>1):0);
for (int i = 0; i < N; i++)
if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int m = 2, m2 = 1; m <= N; m <<= 1, m2 <<= 1) {
wmk[0] = 1, wmk[1] = fpow(G, (MOD-1)/m*DFT+(DFT==-1?MOD-1:0));
for (int j = 2; j < m2; j++) wmk[j] = 1ll * wmk[j-1] * wmk[1] % MOD;
for (int k = 0; k < N; k += m)
for (int j = 0, u, t; j < m2; j++)
t = 1ll * wmk[j] * a[k+j+m2] % MOD, u = a[k+j],
a[k+j] = (u+t)%MOD, a[k+j+m2] = (u-t+MOD)%MOD;
}
if (DFT == -1)
for (int i = 0, invN = fpow(N, MOD-2); i < N; i++)
a[i] = 1ll * a[i] * invN % MOD;
}
inline void solve()
{
int n; scanf("%d", &n);
int len = 1; while (len < n+1) len <<= 1; len <<= 1;
for (int i = 0; i < len; i++) A[i] = B[i] = 0;
for (int i = 0; i <= n; i++) B[i] = sp[i], A[phi[i]]++;
for (int i = 0; i <= n; i++)
qwq[i] = A[i] = 1ll * i * A[i] % MOD * fpow(SQRT2, 1ll*i*i%(MOD-1)) % MOD;
dft(A, 1, len); dft(B, 1, len);
for (int i = 0; i < len; i++) A[i] = 1ll * A[i] * B[i] % MOD;
dft(A, -1, len); lld ans = 0;
for (int i = 1; i <= n; i++)
ans += (2ll * A[i] - qwq[i]) * qwq[i] % MOD;
ans %= MOD; if (ans < 0) ans += MOD;
printf("%lld\n", ans);
}
int main()
{
init_prime();
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
考虑从 出发,到达 的期望步数,逆向建图拓扑排序搞定。
再考虑从 出发,到达 的期望消耗天数累计值,则有
其实是乱搞猜结论出来的,但是后面那个 的意义其实可以理解为,我这一步到终点的天数,是由路径上的每条边叠加得到的。
这个期望的期望好像题解没给证明,先这样吧QAQ。
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 1e5+5;
vector<int> G[MAXN];
int d[MAXN], d2[MAXN], Q[MAXN];
double one[MAXN], dp[MAXN], dp2[MAXN];
void run(double dp[], double dist[], int n)
{
int front = 0, rear = 0; Q[rear++] = n;
memcpy(d, d2, sizeof(d));
while (front < rear)
{
int u = Q[front++];
if (u != n) dp[u] = (d2[u]+1.0)/d2[u]*dist[u] + dp[u]/d2[u];
for (auto v : G[u])
{
d[v]--; if (d[v] == 0) Q[rear++] = v;
dp[v] += dp[u];
}
}
}
void solve()
{
int n, m; scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
dp2[i] = dp[i] = d2[i] = 0, G[i].clear(), one[i]=1;
for (int i = 0, u, v; i < m; i++)
scanf("%d %d", &u, &v), G[v].push_back(u), d2[u]++;
run(dp, one, n);
run(dp2, dp, n);
printf("%.2lf\n", dp2[1]);
}
int main()
{
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
套路变换。
合并,后面那个等比数列求和,注意特判 ,所以需要得到 和 。
杜教筛部分看起来像是 ,那么配上 。
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MOD = 1e9+7;
const int MAXN = 3e6+5;
int _G1[MAXN];
void init_prime()
{
static int pri[MAXN], pcn;
static bool isnp[MAXN];
_G1[1] = 1;
for (int i = 2; i < MAXN; i++)
{
if (!isnp[i]) pri[pcn++] = i, _G1[i] = (1ll * i * i-1) % MOD;
for (int j = 0; j < pcn; j++)
{
if (i * pri[j] >= MAXN) break;
isnp[i * pri[j]] = true;
if (i % pri[j] == 0)
{
_G1[i * pri[j]] = _G1[i] * 1ll * pri[j] % MOD * pri[j] % MOD;
break;
}
else
{
_G1[i * pri[j]] = _G1[i] * (1ll * pri[j] % MOD * pri[j] - 1)% MOD;
}
}
}
for (int i = 1; i < MAXN; i++)
_G1[i] = (_G1[i-1] + _G1[i]) % MOD;
}
lld sumG(int n)
{
static map<int,lld> _G2;
if (n < MAXN) return _G1[n];
if (_G2.count(n)) return _G2[n];
lld ans = n * (n+1ll) % MOD * (2ll*n+1) % MOD * ((MOD+1)/6) % MOD;
for (int L = 2, R; L <= n; L = R+1)
{
R = n / (n / L);
ans -= (R-L+1) * sumG(n/L) % MOD;
}
ans %= MOD; if (ans < 0) ans += MOD;
return _G2[n] = ans;
}
inline lld fpow(lld a, lld k)
{
lld b = 1;
for (; k; k>>=1, a=a*a%MOD)
if (k&1) b=a*b%MOD;
return b;
}
inline lld powers(int ns, int k, int k2)
{
if (ns == 1) return k2-1;
lld ans = fpow(ns, k+1) - 1ll * ns * ns % MOD;
ans = ans * fpow(ns-1, MOD-2) % MOD;
return ans;
}
inline void solve()
{
int n, k = 0, k2 = 0; lld ans = 0;
static char kk[MAXN];
scanf("%d %s", &n, kk);
for (int i = 0; kk[i]; i++)
k = (k * 10ll + kk[i] - '0') % (MOD-1),
k2 = (k2 * 10ll + kk[i] - '0') % MOD;
for (int L = 1, R; L <= n; L = R+1)
{
R = n / (n / L);
ans += (sumG(R) - sumG(L-1)) * powers(n/L, k, k2) % MOD;
}
ans %= MOD; if (ans < 0) ans += MOD;
printf("%lld\n", ans);
}
int main()
{
init_prime();
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
参考题解。我怎么写了一坨屎QAQ。
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
inline lld sum1(lld c) { return c*(c+1)/2; }
inline lld sum2(lld c) { return c*(c+1)*(2*c+1)/6; }
// count the pairs for [1,a] + [1,b] <= [1,c]
inline lld func1(lld a, lld b, lld c)
{
if (a > b) swap(a, b); c--;
if (a < 1 || b < 1) return 0;
if (c <= 0) return 0;
else if (c < a) return sum1(c)*(c+1) - sum2(c);
else if (c <= b) return (c+1-a)*(c+1-a)*a - sum1(c-a)*a + sum1(a-1)*(c+1) - sum2(a-1);
else if (c < a+b) return (c-b)*(a+b)*(c+1) - (a+b+c+1)*(sum1(c)-sum1(b)) + (sum2(c)-sum2(b)) + (b+1-a)*(c+1-a)*a - sum1(b-a)*a + sum1(a-1)*(c+1) - sum2(a-1);
else return a*(a+b)*(c+1) - (a+b+c+1)*(sum1(a+b)-sum1(b)) + (sum2(a+b)-sum2(b)) + (b+1-a)*(c+1-a)*a - sum1(b-a)*a + sum1(a-1)*(c+1) - sum2(a-1);
}
// calc the valid pairs of ([1,a], [1,b], [1,c], d)
inline lld func2(lld a, lld b, lld c, lld d)
{
return a * b * c
- func1(b, c, a-d)
- func1(a, c, b-d)
- func1(a, b, c-d)
- func1(a, b, d-1)
+ func1(a, b, d-c-1);
}
// calc the valid pairs of ([la,ra], [lb,rb], [lc,rc], d)
inline lld func3(pair<int,int> a, pair<int,int> b, pair<int,int> c, int d)
{
return func2(a.second, b.second, c.second, d)
- func2(a.second, b.first-1, c.second, d)
- func2(a.first-1, b.second, c.second, d)
- func2(a.second, b.second, c.first-1, d)
+ func2(a.first-1, b.first-1, c.second, d)
+ func2(a.first-1, b.second, c.first-1, d)
+ func2(a.second, b.first-1, c.first-1, d)
- func2(a.first-1, b.first-1, c.first-1, d);
}
inline void solve()
{
pair<int,int> iv[4]; lld ans = 0;
for (int i = 0; i < 4; i++)
scanf("%d %d", &iv[i].first, &iv[i].second);
for (int i = iv[3].first; i <= iv[3].second; i++)
ans += func3(iv[0], iv[1], iv[2], i);
printf("%lld\n", ans);
}
int main()
{
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}