Znzryb's Blog
0%

Posted on Edited on

思路讲解

我们计算机嘛，这个推导对于我来说还是有点难了，不过结论很简单，就是b^(m-2)为其乘法逆元。

当然，你会说这个乘法逆元有什么用？ AcWing 886. 费马小定理， 快速幂， 求组合数 II  

这不求组合数就有用了吗！

参考以下题解

https://www.acwing.com/solution/content/16482/

image

AC代码

https://www.acwing.com/problem/content/submission/code_detail/40913617/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// Problem: 快速幂求逆元
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/878/
// Memory Limit: 64 MB
// Time Limit: 5000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];

ll binpow(ll a,ll k,const ll &p){
	ll res=1;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}

inline void solve(){
	ll a,p;
	cin>>a>>p;
	if(a%p==0) cout<<"impossible\n";
	else cout<<binpow(a,p-2,p)<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://www.acwing.com/problem/content/submission/code_detail/40913617/
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

参考以下题解

https://www.acwing.com/solution/content/15293/

这里有一个非递归写法

https://www.acwing.com/solution/content/16482/

AC代码

https://www.acwing.com/problem/content/submission/code_detail/40911595/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// Problem: 快速幂
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/877/
// Memory Limit: 64 MB
// Time Limit: 5000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;

ll binpow(ll a,ll k,const ll &p){
	ll res=1;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}

inline void solve(){
	ll a,k,p;
	cin>>a>>k>>p;
	cout<<binpow(a,k,p)<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://www.acwing.com/problem/content/submission/code_detail/40911595/
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

https://www.acwing.com/solution/content/16482/

这个题解非常好，我的快速幂以及逆元都是参考他的题解。

AcWing 876. 快速幂求逆元

AcWing 875. 快速幂

总的来说思路是很简单的，就是预处理公式法。但是除法这取模就会出问题，所以需要用逆元。

AC代码

https://www.acwing.com/problem/content/submission/code_detail/40914515/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// Problem: 求组合数 II
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/888/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,T;
ll fact[MAXN],infact[MAXN];

ll binpow(ll a,ll k,const ll &p){	// 迭代快速幂
	ll res=1;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}

inline void solve(){
	ll a,b;
	cin>>a>>b;
	cout<<(fact[a]*infact[b]%mod*infact[a-b])%mod<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	fact[0]=1;
	infact[0]=binpow(fact[0],mod-2,mod);;
	FOR(i,1,MAXN-5){
		fact[i]=(fact[i-1]*i)%mod;
		infact[i]=binpow(fact[i],mod-2,mod);
	}
#ifdef LOCAL
	FOR(i,1,15){
		cerr<<fact[i]<<" ";
	}
	cerr<<"\n";
	FOR(i,1,15){
		cerr<<infact[i]<<' ';
	}
	cerr<<"\n";
#endif
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://www.acwing.com/problem/content/submission/code_detail/40914515/
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

image

这个递推法其实就是把两种情况分开来考虑了（即选一个人的情况+不选一个人的情况）

AC代码

https://www.acwing.com/problem/content/submission/code_detail/40911169/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// Problem: 求组合数 I
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/887/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e3)+15,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,T,C[MAXN][MAXN];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	N=2010;
	C[1][1]=1;
	C[0][1]=1;
	FOR(i,1,N){
		C[0][i]=1;
	}
	FOR(i,2,N){
		FOR(j,1,i){
			C[j][i]=(C[j-1][i-1]+C[j][i-1])%mod;
		}
	}
	cin>>T;
	FOR(i,1,T){
		ll a,b;
		cin>>a>>b;
		cout<<C[b][a]<<"\n";
	}
	return 0;
}
/*
AC
https://www.acwing.com/problem/content/submission/code_detail/40911169/
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

参考这个题解（官解看不太懂，不知道为什么可以改写成那样）

https://atcoder.jp/contests/abc399/editorial/12582

【ABC399F - Range Power Sum题解.递推】 https://www.bilibili.com/video/BV1iZZaYiEHC/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

算了，我也不尝试论述怎么想到这个思路了，这个思路还是很难想的

image

我只能说多动笔吧，分析问题，特别是dp类问题，还是需要系统的分析，光空想是不够的。

sum的定义

1
2
//      k    i   (a1+...+ai)^k+(a2+...+ai)^k+...+(ai-1+...+ai)^k+ai^k
ll sum[15][MAXN];

AC代码

https://atcoder.jp/contests/abc399/submissions/64378660

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// Problem: F - Range Power Sum
// Contest: AtCoder - AtCoder Beginner Contest 399
// URL: https://atcoder.jp/contests/abc399/tasks/abc399_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=998244353;

ll N,K,T,A[MAXN];
//      k    i   (a1+...+ai)^k+(a2+...+ai)^k+...+(ai-1+...+ai)^k+ai^k
ll sum[15][MAXN];
ll infact[15],fact[15];
ll C[15][15];

ll binpow(ll a,ll k,const ll &p){	// 迭代快速幂
	ll res=1;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}

inline void solve(){
	cin>>N>>K;
	FOR(i,1,N){
		cin>>A[i];
	}
	FOR(i,1,K){
		FOR(j,1,N){
			// ll idx=0;
			FOR(k,0,i-1){
				sum[i][j]+=sum[i-k][j-1]*C[k][i]%mod*binpow(A[j],k,mod)%mod;
				// ++idx;
			}
			sum[i][j]=(sum[i][j]+j*binpow(A[j],i,mod))%mod;
// #ifdef LOCAL
    // cerr << i<<" "<< j<<" "<<sum[i][j]<< '\n';
// #endif
		}
	}
	ll ans=0;
	FOR(i,1,N){
		ans=(ans+sum[K][i])%mod;
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	fact[0]=1,infact[0]=1;
	FOR(i,1,13){
		fact[i]=fact[i-1]*i%mod;
		infact[i]=binpow(fact[i],mod-2,mod);
	}
	FOR(i,1,13){
		FOR(j,0,i){
			C[j][i]=fact[i]*infact[j]%mod*infact[i-j]%mod;
		}
	}
// #ifdef LOCAL
    // FOR(i,1,13){
		// FOR(j,0,i){
			// cerr<<C[j][i]<<" ";
		// }
		// cerr<<"\n";
	// }
// #endif
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc399/submissions/64378660
*/

心路历程（WA，TLE，MLE……）

一种比较常见的递推思路是

长度为1的区间→长度为2的区间→…→长度为n的区间（很正常的想法）