1.普通ksm
1快速幂算法(全网最详细地带你从零开始一步一步优化)-CSDN博客
ll ksm(ll base,ll power){
ll result=1;
while(power>0){
if(power&1) result=(result*base)%mod;//为奇数,按位与,只比最后一位
power>>=1;
base=(base*base)%mod;//由于得到这个base时已经mod过了,不用((base%mod)*(base%mod))%mod
}
return result;
}
2.矩阵乘法
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 3;
int n, m;
void mul(int c[], int a[], int b[][N])
{
int temp[N] = {0};
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;
memcpy(c, temp, sizeof temp);
}
void mul(int c[][N], int a[][N], int b[][N])
{
int temp[N][N] = {0};
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
for (int k = 0; k < N; k ++ )
temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;
memcpy(c, temp, sizeof temp);
}
int main()
{
cin >> n >> m;
int f1[N] = {1, 1, 1};
int a[N][N] = {
{0, 1, 0},
{1, 1, 1},
{0, 0, 1}
};
n -- ;
while (n)
{
if (n & 1) mul(f1, f1, a); // res = res * a
mul(a, a, a); // a = a * a
n >>= 1;
}
cout << f1[2] % m << endl; // 当n = 1, m = 1时,余数应该是0,需要再对m取模
return 0;
}
1f1+2f2+3f3+...=?
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 4;
int n, m;
void mul(int c[][N], int a[][N], int b[][N]) // c = a * b
{
static int t[N][N];
memset(t, 0, sizeof t);
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
for (int k = 0; k < N; k ++ )
t[i][j] = (t[i][j] + (LL)a[i][k] * b[k][j]) % m;
memcpy(c, t, sizeof t);
}
int main()
{
cin >> n >> m;
// {fn, fn+1, sn, pn}
// pn = n * sn - tn
int f1[N][N] = {1, 1, 1, 0};
int a[N][N] = {
{0, 1, 0, 0},
{1, 1, 1, 0},
{0, 0, 1, 1},
{0, 0, 0, 1},
};
int k = n - 1;
// 快速幂
while (k)
{
if (k & 1) mul(f1, f1, a); // f1 = f1 * a
mul(a, a, a); // a = a * a
k >>= 1;
}
cout << (((LL)n * f1[0][2] - f1[0][3]) % m + m) % m << endl;
return 0;
}
作者:yxc
链接:https://www.acwing.com/activity/content/code/content/188826/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
有点像数位dp,不出现某段号码的号码有多少个
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25;
int n, m, mod;
char str[N];
int ne[N];
int a[N][N];
void mul(int c[][N], int a[][N], int b[][N]) // c = a * b
{
static int t[N][N];
memset(t, 0, sizeof t);
for (int i = 0; i < m; i ++ )
for (int j = 0; j < m; j ++ )
for (int k = 0; k < m; k ++ )
t[i][j] = (t[i][j] + a[i][k] * b[k][j]) % mod;
memcpy(c, t, sizeof t);
}
int qmi(int k)
{
int f0[N][N] = {1};
while (k)
{
if (k & 1) mul(f0, f0, a); // f0 = f0 * a
mul(a, a, a); // a = a * a
k >>= 1;
}
int res = 0;
for (int i = 0; i < m; i ++ ) res = (res + f0[0][i]) % mod;
return res;
}
int main()
{
cin >> n >> m >> mod;
cin >> str + 1;
// kmp
for (int i = 2, j = 0; i <= m; i ++ )
{
while (j && str[j + 1] != str[i]) j = ne[j];
if (str[j + 1] == str[i]) j ++ ;
ne[i] = j;
}
// 初始化A[i][j]
for (int j = 0; j < m; j ++ )
for (int c = '0'; c <= '9'; c ++ )
{
int k = j;
while (k && str[k + 1] != c) k = ne[k];
if (str[k + 1] == c) k ++ ;
if (k < m) a[j][k] ++ ;
}
// F[n] = F[0] * A^n
cout << qmi(n) << endl;
return 0;
}
作者:yxc
链接:https://www.acwing.com/activity/content/code/content/188887/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
例题
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 130, MOD = 1e9 + 7;
LL n;
int m;
int w[N][N];
void dfs(int x, int y, int u)
{
if (u == m) w[x][y] ++ ;
else if (x >> u & 1) dfs(x, y, u + 1);
else
{
if (u && !(y >> u & 1) && !(y >> u - 1 & 1))
dfs(x, y + (1 << u) + (1 << u - 1), u + 1);
if (u + 1 < m && !(y >> u & 1) && !(y >> u + 1 & 1))
dfs(x, y + (1 << u) + (1 << u + 1), u + 1);
if (u + 1 < m && !(x >> u + 1 & 1))
{
if (!(y >> u & 1)) dfs(x, y + (1 << u), u + 2);
if (!(y >> u + 1 & 1)) dfs(x, y + (1 << u + 1), u + 2);
}
}
}
void mul(int c[][N], int a[][N], int b[][N])
{
static int tmp[N][N];
memset(tmp, 0, sizeof tmp);
for (int i = 0; i < 1 << m; i ++ )
for (int j = 0; j < 1 << m; j ++ )
for (int k = 0; k < 1 << m; k ++ )
tmp[i][j] = (tmp[i][j] + (LL)a[i][k] * b[k][j]) % MOD;
memcpy(c, tmp, sizeof tmp);
}
int main()
{
cin >> n >> m;
for (int i = 0; i < 1 << m; i ++ )
dfs(i, 0, 0);
int res[N][N] = {0};
res[0][(1 << m) - 1] = 1;
while (n)
{
if (n & 1) mul(res, res, w);
mul(w, w, w);
n >>= 1;
}
cout << res[0][(1 << m) - 1] << endl;
return 0;
}
291. 蒙德里安的梦想
求把 N×M𝑁×𝑀 的棋盘分割成若干个 1×21×2 的长方形,有多少种方案。
例如当 N=2,M=4𝑁=2,𝑀=4 时,共有 55 种方案。当 N=2,M=3𝑁=2,𝑀=3 时,共有 33 种方案。
如下图所示:
输入包含多组测试用例。
每组测试用例占一行,包含两个整数 N𝑁 和 M𝑀。
当输入用例 N=0,M=0𝑁=0,𝑀=0 时,表示输入终止,且该用例无需处理。
每个测试用例输出一个结果,每个结果占一行。
1≤N,M≤111≤𝑁,𝑀≤11
状态计算:(限制条件:i-1列非空白位置可以不能放置小方格),在i列不同的放置方法就是不同的集合划分。
问题:第 i-2 列伸到 i-1 列的状态为 k , 是否能成功转移到 第 i-1 列伸到 i 列的状态为 j ?
需要满足如下条件:
j&k==0, i-2列伸到i-1的小方格 和i-1列放置的小方格 不重复。
每一列,所有连续着空着的小方格必须是偶数个
f[m][0]:
列数从0开始计数,m列不放小方格,前m-1列已经完全摆放好并且不伸出来的状态
#include<iostream>
#include<cstring>
using namespace std;
//数据范围1~11
const int N = 12;
//每一列的每一个空格有两种选择,放和不放,所以是2^n
const int M = 1 << N;
//方案数比较大,所以要使用long long 类型
//f[i][j]表示 i-1列的方案数已经确定,从i-1列伸出,并且第i列的状态是j的所有方案数
long long f[N][M];
//第 i-2 列伸到 i-1 列的状态为 k , 是否能成功转移到 第 i-1 列伸到 i 列的状态为 j
//st[j|k]=true 表示能成功转移
bool st[M];
//n行m列
int n, m;
int main() {
// 预处理st数组
while (cin >> n >> m, n || m) {
for (int i = 0; i < 1 << n; i++) {
// 第 i-2 列伸到 i-1 列的状态为 k ,
// 能成功转移到
// 第 i-1 列伸到 i 列的状态为 j
st[i] = true;
// 记录一列中0的个数
int cnt = 0;
for (int j = 0; j < n; j++) {
// 通过位操作,i状态下j行是否放置方格,
// 0就是不放, 1就是放
if (i >> j & 1) {
// 如果放置小方块使得连续的空白格子数成为奇数,
// 这样的状态就是不行的,
if (cnt & 1) {
st[i] = false;
break;
}
}else cnt++;
// 不放置小方格
}
if (cnt & 1) st[i] = false;
}
// 初始化状态数组f
memset(f, 0, sizeof f);
// 棋盘是从第0列开始,没有-1列,所以第0列第0行,不会有延伸出来的小方块
// 没有横着摆放的小方块,所有小方块都是竖着摆放的,这种状态记录为一种方案
f[0][0] = 1;
// 遍历每一列
for (int i = 1; i <= m; i++) {
// 枚举i列每一种状态
for (int j = 0; j < 1 << n; j++) {
// 枚举i-1列每一种状态
for (int k = 0; k < 1 << n; k++) {
// f[i-1][k] 成功转到 f[i][j]
if ((j & k) == 0 && st[j | k]) {
f[i][j] += f[i - 1][k]; //那么这种状态下它的方案数等于之前每种k状态数目的和
}
}
}
}
// 棋盘一共有0~m-1列
// f[i][j]表示 前i-1列的方案数已经确定,从i-1列伸出,并且第i列的状态是j的所有方案数
// f[m][0]表示 前m-1列的方案数已经确定,从m-1列伸出,并且第m列的状态是0的所有方案数
// 也就是m列不放小方格,前m-1列已经完全摆放好并且不伸出来的状态
cout << f[m][0] << endl;
}
return 0;
}
作者:松鼠爱葡萄
链接:https://www.acwing.com/solution/content/15616/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。