#include <iostream>
using namespace std;

typedef long long LL;

int qmi(int a, int b, int p)
{
    int res = 1;
    while(b)
    {
        if(b & 1)
            res = (LL)res * a % p;
        b >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a, b, p;
        cin >> a >> b >> p;
        cout << qmi(a, b, p) << endl;
    }

    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
/*
状态表示f[i,j]
    集合：总和为i，总个数为j的方案
    属性：cnt
状态计算
    把集合分为最小值是1的和最小值不是1的，则
        最小值是1，即f[i-1,j-1]
        最小值不是1，即f[i-j,j]
            将所有数都减去1，则此方案集合在数量上等价于
            总和是i-j，总个数还是j的方案集合
    因此，f[i,j] = f[i-1,j-1] + f[i-j,j]
*/
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];

int main()
{
    cin >> n;
    // 初始化总和为1，总个数为1的方案（当然只有{1}这一种情况）
    f[1][1] = 1;
    for(int i=2; i<=n; i++)
        for(int j=1; j<=i; j++)
            f[i][j] = (f[i-1][j-1] + f[i-j][j]) % mod;

    // 统计总和为n的所有不同个数的方案数
    int res = 0;
    for(int i=1; i<=n; i++)
        res = (res + f[n][i]) % mod;

    cout << res;

    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
/*
状态表示f[i,j]
    集合：总和为i，总个数为j的方案
    属性：cnt
状态计算
    把集合分为最小值是1的和最小值不是1的，则
        最小值是1，即f[i-1,j-1]
        最小值不是1，即f[i-j,j]
            将所有数都减去1，则此方案集合在数量上等价于
            总和是i-j，总个数还是j的方案集合
    因此，f[i,j] = f[i-1,j-1] + f[i-j,j]
*/
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];

int main()
{
    cin >> n;
    // 初始化总和为1，总个数为1的方案（当然只有{1}这一种情况）
    f[1][1] = 1;
    for(int i=2; i<=n; i++)
        for(int j=1; j<=i; j++)
            f[i][j] = (f[i-1][j-1] + f[i-j][j]) % mod;

    // 统计总和为n的所有不同个数的方案数
    int res = 0;
    for(int i=1; i<=n; i++)
        res = (res + f[n][i]) % mod;

    cout << res;

    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
/*
状态表示f[i,j]
    集合：以[i,j]为起点的路径
    属性：max
状态计算
    每个结点可以往四个方向下滑
    见视频。
*/
const int N = 310;
int n, m;
int g[N][N], f[N][N];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int dp(int x, int y)
{
    int &v = f[x][y];
    if(v != -1)
        return v;

    v = 1;
    for(int i=0; i<4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx>=1 && nx<=n && ny>=1 && ny<=m && g[nx][ny]<g[x][y])
            v = max(v, dp(nx, ny) + 1);
    }

    return v;
}


int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >> g[i][j];

    memset(f, -1, sizeof f);

    int res = 0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            res = max(res, dp(i, j));

    cout << res;
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
/*
状态表示f[i,j]
    集合：以[i,j]为起点的路径
    属性：max
状态计算
    每个结点可以往四个方向下滑
    见视频。
*/
const int N = 310;
int n, m;
int g[N][N], f[N][N];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int dp(int x, int y)
{
    int &v = f[x][y];
    if(v != -1)
        return v;

    v = 1;
    for(int i=0; i<4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx>=1 && nx<=n && ny>=1 && ny<=m && g[nx][ny]<g[x][y])
            v = max(v, dp(nx, ny) + 1);
    }

    return v;
}


int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >> g[i][j];

    memset(f, -1, sizeof f);

    int res = 0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            res = max(res, dp(i, j));

    cout << res;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
状态表示f[i,0], f[i,1]
    集合：（用0、1表示）邀请/不邀请i号职员参加舞会
    属性：max
状态计算
    不选i，则f[i,0] += max(f[s,0], f[s,1])
        其中，遍历所有子结点。子结点当然可选可不选，故取其max
    选i，则f[i,1] += f[s,0]
        同样遍历所有子结点。子结点只能不选（因为父结点i选了）
*/
const int N = 6010;
int n;
int happy[N];
int h[N], e[N], ne[N], idx;
int f[N][2];
bool has_father[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u)
{
    // 初始化选的情况
    f[u][1] = happy[u];
    for(int i=h[u]; i!=-1; i=ne[i])
    {
        int j = e[i];
        // 先递归到底，自底往上算出f
        dfs(j);
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> happy[i];

    memset(h, -1, sizeof(f));
    for(int i=0; i < n-1; i++)
    {
        int a, b;
        cin >> a >> b;
        has_father[a] = true;
        add(b, a);
    }

    // 计算“最后”一个根节点
    int root = 1;
    while(has_father[root])
        root++;

    dfs(root);

    cout << max(f[root][0], f[root][1]);
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
状态表示f[i,0], f[i,1]
    集合：（用0、1表示）邀请/不邀请i号职员参加舞会
    属性：max
状态计算
    不选i，则f[i,0] += max(f[s,0], f[s,1])
        其中，遍历所有子结点。子结点当然可选可不选，故取其max
    选i，则f[i,1] += f[s,0]
        同样遍历所有子结点。子结点只能不选（因为父结点i选了）
*/
const int N = 6010;
int n;
int happy[N];
int h[N], e[N], ne[N], idx;
int f[N][2];
bool has_father[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u)
{
    // 初始化选的情况
    f[u][1] = happy[u];
    for(int i=h[u]; i!=-1; i=ne[i])
    {
        int j = e[i];
        // 先递归到底，自底往上算出f
        dfs(j);
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> happy[i];

    memset(h, -1, sizeof(f));
    for(int i=0; i < n-1; i++)
    {
        int a, b;
        cin >> a >> b;
        has_father[a] = true;
        add(b, a);
    }

    // 计算“最后”一个根节点
    int root = 1;
    while(has_father[root])
        root++;

    dfs(root);

    cout << max(f[root][0], f[root][1]);
}

#include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
状态表示f[i,j]
    集合：经过i表示的结点，从0到j的所有路径
    属性：最小值
状态计算
    把每条路径不重不漏地分类，可以这么分：
    枚举每条路径的倒数第二个结点，例如：
    0-j可分为倒数第二个结点是
    0、1、2、...、n-1
    若此结点是k，则
    路径分划分为0->k->j，其中k->j = w[k][j]
    而0->k则等于f[i-{j}][k]
    即所有从0到k，经过结点为i（二进制）除去j的路径
*/
const int N = 21, M = 1<<N;
int n;
int w[N][N], f[M][N];

int main()
{
    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> w[i][j];

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;

    for(int i=0; i < 1<<n; i++)
        for(int j=0; j<n; j++)
            // 判断路径是否合法（j结点是否在i表示的集合中）
            if(i>>j & 1)
                // 枚举倒数第二个结点
                for(int k=0; k<n; k++)
                    // 判断路径是否合法（k结点是否在i表示的集合中）
                    if(i>>k & 1)
                        f[i][j] = min(f[i][j], f[i-(1<<j)][k] + w[k][j]);

    // 不重不漏地经过每个点恰好一次，所以i是111111
    cout << f[(1<<n)-1][n-1];
}

#include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
/*
状态表示f[i,j]
    集合：经过i表示的结点，从0到j的所有路径
    属性：最小值
状态计算
    把每条路径不重不漏地分类，可以这么分：
    枚举每条路径的倒数第二个结点，例如：
    0-j可分为倒数第二个结点是
    0、1、2、...、n-1
    若此结点是k，则
    路径分划分为0->k->j，其中k->j = w[k][j]
    而0->k则等于f[i-{j}][k]
    即所有从0到k，经过结点为i（二进制）除去j的路径
*/
const int N = 21, M = 1<<N;
int n;
int w[N][N], f[M][N];

int main()
{
    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> w[i][j];

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;

    for(int i=0; i < 1<<n; i++)
        for(int j=0; j<n; j++)
            // 判断路径是否合法（j结点是否在i表示的集合中）
            if(i>>j & 1)
                // 枚举倒数第二个结点
                for(int k=0; k<n; k++)
                    // 判断路径是否合法（k结点是否在i表示的集合中）
                    if(i>>k & 1)
                        f[i][j] = min(f[i][j], f[i-(1<<j)][k] + w[k][j]);

    // 不重不漏地经过每个点恰好一次，所以i是111111
    cout << f[(1<<n)-1][n-1];
}

参考：

AcWing 275. 证明传纸条为何可以使用方格取数的代码
AcWing 275. 传纸条

#include <iostream>
using namespace std;

const int N = 51;
int m, n;
int x, y, w;
int g[N][N];
int f[N*2][N][N];

const int N = 51;
int m, n;
int x, y, w;
int g[N][N];
int f[N*2][N][N];

int main()
{
    cin >> m >> n;
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            cin >> g[i][j];

    for(int k=2; k<=n+m; k++)
        for(int j=1; j<=n; j++)
            for(int b=1; b<=n; b++)
            {
                int i = k-j, a = k-b;
                if(i>=1 && i<=m && a>=1 && a<=m)
                {
                    f[k][j][b] = max(max(f[k-1][j][b], f[k-1][j-1][b]),
                                     max(f[k-1][j][b-1], f[k-1][j-1][b-1]));
                    if(j == b)
                        f[k][j][b] += g[i][j];
                    else
                        f[k][j][b] += (g[i][j] + g[a][b]);
                }
            }
    cout << f[n+m][n][n];

}