• 2022 ICPC Gran Premio de Mexico 1ra Fecha （B、D、E、F）

    小技巧：
    stoi(str,0,2) 将从0开始的二进制串转化为十进制串
    不是标准函数，慎用（一般应该没问题吧……）

    本次补的题应该都是铜、银牌题，可能欧洲场简单很多
    D. Different Pass a Ports
    好久没做快速幂的题目了，换了个题目背景，差点没看出来。
    分析：
    1.只要存在双向线路，便可去往别的港口，但不能停着不动。
    2.港口间可重复访问。线路便可看作对矩阵的初始化。从港口1开始，需要初始化一个值为1的矩阵，每次对线路进行选择，即乘上初始化的矩阵。
    分析下来，可简化为矩阵1*线路矩阵^k^

    #include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
//const int N=7e5+5;
const int inf=1e18;
const int mod=1e9+7;
int fac[40];
int qpow(int a,int b){
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int x){return qpow(x,mod-2);}
int C(int a,int b)
{
    return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
}
int n,m,k;
struct Matrix
{
	static const int N=102;  //开设的矩阵
	int a[N][N];
	Matrix(int e=0)          //矩阵清0
	{
		for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
            a[i][j]=e*(i==j);
	}
	Matrix mul(Matrix A,Matrix B)   //矩阵的乘法运算   A*B
	{
		Matrix ans(0);    //初始化全为0的矩阵
		for (int i=1;i<=n;i++)
        {
			for (int j=1;j<=n;j++)
			{
				for (int k=1;k<=n;k++)
				{			//模拟乘法运算
					ans.a[i][j]=(ans.a[i][j]+A.a[i][k]*B.a[k][j])%mod;
				}
			}
		}
		return ans;  //返回
	}
	Matrix ksm(Matrix A,int b){
		Matrix ans(1);   //初始化为1的矩阵
		while (b)
        {
			if (b&1)ans=mul(ans,A);   //快速幂
			A=mul(A,A);
			b>>=1;
		}
		return ans;
	}
};
Matrix A;
void solve()
{
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        A.a[u][v]=1;A.a[v][u]=1;
    }
    Matrix B=A.ksm(A,k);
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=(ans+B.a[1][i])%mod;
    cout<<ans<<endl;
}
signed main()
{
    ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}


    • 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

    B. Building 5G antennas
    思路：
    1.f[v][dis]表示点v，对于当天的距离为j，最早可到达的天数。
    2.使用set容器记录前一天可连接点的最小值，此处利用了set的自动排序功能。
    3.每次将当天可到达的点记录下，压入到队列中，在都放入集合中。

    #include
//#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=1e5+5;
const int inf=1e18;
const int mod=1e9+7;
int fac[40];
int qpow(int a,int b){
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int x){return qpow(x,mod-2);}
int C(int a,int b)
{
    return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
}
int n,k,f[N][105];
struct node
{
    int x,dis,fa;
};
bool vis[N];
vector<int>e[N],ans;
set<int>st;queue<node>q;

void solve()
{
    cin>>n>>k;
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        e[u].push_back(v),e[v].push_back(u);
    }
    for(int i=1;i<=n;i++) for(int j=0;j<105;j++) f[i][j]=inf;
    vis[1]=1;
    st.insert(1);           //set容器默认将小值放前面
    for(int i=0;i<n;i++)    //每天建造的网线
    {
        if(!st.size()) break;
        int x=*st.begin();
        st.erase(st.begin());
        q.push({x,0,0});
        f[x][0]=i+1;
        ans.push_back(x);
        while(!q.empty())
        {
            auto tmp=q.front();
            int u=tmp.x,dis=tmp.dis;
            q.pop();
            if(!vis[u])
            {
                vis[u]=1;st.insert(u);
            }
            if(dis<k)
            {
                for(int v:e[u])
                {
                    if(v==tmp.fa) continue;
                    if(f[v][dis+1]>f[u][dis])
                    {
                        f[v][dis+1]=f[u][dis];
                        q.push({v,dis+1,u});
                    }
                }
            }
        }
    }
    for(int x:ans) cout<<x<<" ";
    cout<<endl;
}
signed main()
{
    ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

    • 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

    E. Erudite of words
    思路：
    1.本题为数学推公式的题目。在M个字母中选取K个字母构成长度为N的字符串的方案数。
    2.首先能想到从M个字母中选取k个字母为方案数为C(m,k)
    3.长度为n，将k个字母随机放到n个位置。求出由k个字母构成的总方案数减去由c个字母构成的字符串（c 4.f[i]表示由i个字母构成的长度为n的字符串。f[i]=i^n^-(1~j)*C(i,j)*f[j]的累加和
    5.最后再乘上C(m,k)

    #include
#define int long long
#define endl '\n'
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N=1e6+5;
const int inf=1e18;
const int mod=1e9+7;
int n,m,k,fac[N],f[5005],inv[N];
int qpow(int a,int b){
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int getinv(int x){return qpow(x,mod-2);}
int C(int a,int b)
{
    return (fac[a]*inv[a-b]%mod)*inv[b]%mod;
}
void init()
{
    fac[0]=1;
    for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%mod;
    /* 线性求逆元 受数据范围限制
    inv[1]=1;
    for(int i=2;i
    inv[N]=getinv(fac[N]);
    for(int i=N-1;i>=0;i--)
        inv[i]=inv[i+1]*(i+1)%mod;
}
void solve()
{
    init();
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
    {
        f[i]=qpow(i,n)%mod;
        for(int j=1;j<i;j++)
            f[i]=(f[i]-C(i,j)*f[j]%mod+mod)%mod;
    }
    cout<<f[k]*C(m,k)%mod<<endl;
}
signed main()
{
    ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}


    • 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

    矩阵快速幂使用情况：
    1.数据规模很大
    2.有递推公式

    F. Froginald the frog
    需要再打一个表，能省很多时间。不然每一段都要进行一次快速幂，会tle。看的一篇题解也tle了，数据更新了，需要打表优化下。明天试试

    优化后，多过了20多组样例，时间上没问题了，但runtime error了，不知道为啥。

    思路：
    1.被多个点分成了多个区间，答案为各个区间得累乘。
    2.当两个点值差值为1时，到不了终点；为2、3时，只有一种情况；差值为4时有2种情况，符合斐波那契，eg：4、8，可行区间为【5，7】

    #include
#define int long long
#define endl '\n'
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

using namespace std;
const int N=2e6+5;
const int inf=1e18;
const int mod=1e9+7;
int n,m,a[N],ans[N];
struct Matrix
{
	static const int N=3;  //开设的矩阵
	int a[N][N];
	int n=2;
	Matrix(int e=0)          //矩阵清0
	{
		for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
            a[i][j]=e*(i==j);
	}
	Matrix mul(Matrix A,Matrix B)   //矩阵的乘法运算   A*B
	{
		Matrix ans(0);    //初始化全为0的矩阵
		for (int i=1;i<=n;i++)
        {
			for (int j=1;j<=n;j++)
			{
				for (int k=1;k<=n;k++)
				{			//模拟乘法运算
					ans.a[i][j]=(ans.a[i][j]+A.a[i][k]*B.a[k][j])%mod;
				}
			}
		}
		return ans;  //返回
	}
	Matrix ksm(Matrix A,int b){
		Matrix ans(1);   //初始化为1的矩阵
		while (b)
        {
			if (b&1)ans=mul(ans,A);   //快速幂
			A=mul(A,A);
			b>>=1;
		}
		return ans;
	}
};

void solve()
{
    Matrix A;
    A.a[1][1]=A.a[1][2]=A.a[2][1]=1;
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>a[i];
    Matrix B(1);
    for(int i=1;i<=N;i++)
    {
        B=B.mul(B,A);
        ans[i]=(B.a[1][1]+B.a[1][2])%mod;
    }
    sort(a+1,a+m+1);
    a[0]=-1;
    m++,a[m]=n+1;
    int ss=1;
    for(int i=1;i<=m;i++)
    {
        if(a[i]-a[i-1]==1)
        {
            cout<<0<<endl;return;
        }
        else if(a[i]-a[i-1]==2||a[i]-a[i-1]==3)
            continue;
        else
        {
            ss=ss*ans[a[i]-a[i-1]-3]%mod;
        }
    }
    cout<<ss<<endl;
}
signed main()
{
    ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}



    • 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
  • 相关阅读:
    QT:QSS自定义 QCheckBox实例
    杭电oj 2043 密码 C语言
    JAVA-----集合初解
    Linux学习：初识Linux
    docker--基础（一）
    地图结构 | 图解占据栅格地图原理(附Matlab建图实验)
    安全防御设备——防火墙总结【2】
    【LeetCode】6. N 字形变换
    计算机毕业设计node.js+vue在线日程管理系统
    2022年全球市场砷化铟镓引脚模块总体规模、主要生产商、主要地区、产品和应用细分研究报告
  • 原文地址：https://blog.csdn.net/weixin_51934288/article/details/126919888