首页 > 其他分享 >合肥学院校赛热身赛题解

合肥学院校赛热身赛题解

时间:2022-12-03 20:44:55浏览次数:68  
标签:Matrix int 题解 矩阵 long base 校赛 热身赛 mod

A.codeforces

直接读入输入即可

#include <bits/stdc++.h>
int main()
{
    string s;
    cin>>s;
    cout<<"https://codeforces.com/profile/"<<s;
    return 0;
}

B.小美挑糖果

对给定的所有糖果按数量进行排序,然后取最大的前\(k\)袋糖果。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k;
int a[N];
int main()
{
    cin>>n>>k;
    int ans=0;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=n;k;i--,k--)
        ans+=a[i];
    cout<<ans<<endl;
    return 0;
}

C.你好 ACM!

直接输出即可,但是需要注意反斜杠需要进行转义,例如

printf("\\");

输出为:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    cout << " _    _          _   _                         _____   __  __   _" << endl;
    cout << "| |  | |        | | | |               /\\      / ____| |  \\/  | | |" << endl;
    cout << "| |__| |   ___  | | | |   ___        /  \\    | |      | \\  / | | |" << endl;
    cout << "|  __  |  / _ \\ | | | |  / _ \\      / /\\ \\   | |      | |\\/| | | |" << endl;
    cout << "| |  | | |  __/ | | | | | (_) |    / ____ \\  | |____  | |  | | |_|" << endl;
    cout << "|_|  |_|  \\___| |_| |_|  \\___/    /_/    \\_\\  \\_____| |_|  |_| (_)" << endl;
    return 0;
}

D 奇怪的数列

解法1

平方和求和公式
\(\sum_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}\)

证明:
\(i^{2}=i(i-1)+i\)

\(\sum_{i=1}^{n}i^{2}=\sum_{i=1}^{n}C_{i}^{1}+2*C_{i}^{2}=2*C_{n+1}^{3}+C_{n+1}^{2}=\frac{n(n+1)(2n+1)}{6}\)

直接套公式即可,注意数据范围很大,需要开\(long\ long\)。

对于取模操作,\(\frac{a}{b}mod\ N\ne \frac{a\ mod\ N}{b\ mod\ N}\)。

但是如果变成乘法,\(a*\frac{1}{b}\ mod\ N=\frac{a}{b}mod\ N\)。

所以我们需要求\(\frac{1}{6}\),即6的逆元

求逆元一定要满足\(a\)与\(mod\)互质。题目给出的模数\(10^{9}+7\)是质数,所以一定满足互质的条件。

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long qmi(long long a, long long b, long long mod)//快速幂求6的逆元
{
    long long res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int main()
{
    long long n;
    cin>>n;
    cout<<((n%mod)*((n+1)%mod))%mod*(2*n%mod+1)%mod*qmi(6,mod-2,mod)%mod;
    return 0;
}

解法2

比较典型的矩阵快速幂模板题。正常的线性递推求解的方法由于1e18的时间范围限制,
在时间复杂度上肯定是过不去的,而直接使用平方和公式求解答案时无法处理取模问题,所以本题我们考虑使用矩阵快速幂来求解。

先分析递推式:\(a_n = a_{n - 1} + n^2\)
这里为了构造第\(n\)项矩阵的通式,我们可以看出,第\(n\)项目前应该获取的值有\(a_n\)和\(n^2\)
同时还要获得前一项的值\(a_{n-1}\)和\((n-1)^2\)。

这里通过平方差公式,我们可以得到\(n^2=(n-1)^2+2n-1\)
所以除了上述信息,我们的第\(n\)项还需要获取\(n\)的值
通过这些信息,我们可以设第\(n\)项矩阵为:

\[\left\{\begin{matrix}a_n&n^2&n&1\end{matrix}\right\} \]

相应的,第\(n-1\)项矩阵应

\[\left\{\begin{matrix}a_{n-1}&(n-1)^2&n-1&1\end{matrix}\right\} \]

处理到这里,我们得到了第\(n-1\)项矩阵和第\(n\)项矩阵,而我们还需要最后一个\(base\)矩阵,构造出矩阵的乘法恒等式。学习过线性代数的知识后,通过矩阵的乘法规则,我们可以构造出

\(base\)=

\[\left\{\begin{matrix}1 & 0 & 0 & 0 \\1 & 1 & 0 & 0 \\2 & 2 & 1 & 0 \\1 & 1 & 1 & 1 \\\end{matrix}\right\} \]

这里我们可以得到恒等式:\(Matrix(a_n)=Matrix(a_{n-1})*base\)


写到这里,我们的原式就转化为了矩阵乘法的递推式,而我们的初始矩阵\(Matrix(a_0)\)可以从题面中直接获取,即\(\left\{\begin{matrix}0 & 0 & 0 & 1\end{matrix}\right\}\)
通过矩阵的乘法结合律我们将恒等式进一步优化为:
\(Matrix(a_n)(n>0)=Matrix(a_0)*\prod_{i=1}^{n}base\)
累乘这一部分的时间复杂度我们就可以使用矩阵快速幂的模板来将原本的时间复杂度由\(O(n)\)降到\(O(logn)\)级别。

#include<bits/stdc++.h>
using namespace std;

#define LL long long
const LL mod = 1e9 + 7;
const int N = 10;

struct Matrix {
    LL m[11][11];
};

LL n;
Matrix base, res;

Matrix Mul(Matrix x, Matrix y) {
    Matrix c;
    for (int i = 0; i < N; i ++ ) 
        for (int j = 0; j < N; j ++ ) c.m[i][j] = 0;
    for(int i = 0; i < N; i ++ )
        for(int j = 0; j < N; j ++ )
            for(int k = 0; k < N; k ++ )
                c.m[i][j] = c.m[i][j] % mod + x.m[i][k] * y.m[k][j] % mod;
    return c;
}

Matrix pow(Matrix x, LL y) {
    Matrix ans = x;
    while(y) {
        if(y & 1) ans = Mul(ans, x);
        x = Mul(x, x);
        y >>=1 ;
    }
    return ans;
}



void init() { 
	base.m[0][0] = 1; base.m[0][1] = 0; base.m[0][2] = 0; base.m[0][3] = 0; 
	base.m[1][0] = 1; base.m[1][1] = 1; base.m[1][2] = 0; base.m[1][3] = 0; 
	base.m[2][0] = 2; base.m[2][1] = 2; base.m[2][2] = 1; base.m[2][3] = 0; 
	base.m[3][0] = 1; base.m[3][1] = 1; base.m[3][2] = 1; base.m[3][3] = 1; 
	res.m[0][3] = 1;
}

int main() {
	cin >> n;
	if (!n) {
		cout << 0 << endl;
		return 0;
	}
	init();
	res = Mul(res, pow(base, n - 1));
	cout << res.m[0][0] << endl;
	return 0;
}

标签:Matrix,int,题解,矩阵,long,base,校赛,热身赛,mod
From: https://www.cnblogs.com/acmerbs/p/16948747.html

相关文章

  • [SCOI2014]方伯伯的玉米田题解
    [SCOI2014]方伯伯的玉米田题目描述方伯伯在自己的农田边散步,他突然发现田里的一排玉米非常的不美。这排玉米一共有\(N\)株,它们的高度参差不齐。方伯伯认为单调不下降序......
  • Ynoi2011题解
    d1t1初始化题意一个长度为\(n\)的序列,\(q\)次操作。询问\([l,r]\)的区间和。将所有\(\bmodx=y\)的下标位置加\(z\)。\(n,q\leq2\times10^5\)。题解......
  • CF1710 题解
    比赛链接:https://codeforces.com/contest/1711BD比以往的要难,E要更简单A水题//bySkyRainWind#include<cstdio>#include<vector>#include<cassert>#include<c......
  • 问题解决系列:从源码讲解为什么是 'JZ0SL_ Unsupported SQL type 1111'
    一、问题场景正在做代码改造,使用​​mybatis​​​+​​sybase​​进行数据库操作,运行过程中,提示以下报错:java.io.IOException:JZ0SL:UnsupportedSQLtype1111.本篇博客......
  • npm 报错:npm ERR! Maximum call stack size exceeded 超过最大栈问题解决方案
    先尝试将npm升级到最新版1234$npminstallnpm-g#检查版本$npm-v6.14.5运行以下命令删除当前路径下的node_modules目录1234$rmnode_mo......
  • 2022年Kubernetes CKA 认证真题解析完整版
    第一题RBAC授权问题权重:4%设置配置环境:[student@node-1]$kubectlconfiguse-contextk8sContext为部署管道创建一个新的ClusterRole并将其绑定到范围为特定的name......
  • 互联网最全cka真题解析-2022
    1、CKA真题解析kubectl自动补全及帮助信息1、配置kubectl自动补全aptinstallbash-completionsource<(kubectlcompletionbash)2、kubectlexplans帮助信息3、kubec......
  • 关于mac电脑突然搜不到家里wifi但手机却能连上的问题解决
    今天用mac电脑时,突然遇到一个奇怪的问题,家里wifi用的好好的,突然就连不上了,在看电脑能搜索到的wifi,居然家里的wifi都没有搜索到,但自己的手机却是正常的,然后我再看看我另外......
  • [ABC251Ex] Fill Triangle 题解
    [ABC251Ex]FillTriangleSolution目录[ABC251Ex]FillTriangleSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面存在序列$a_n$,将......
  • ABC246Ex 01? Queries 题解
    ABC246Ex01?QueriesSolution目录ABC246Ex01?QueriesSolution更好的阅读体验戳此进入浅谈DDP与广义矩阵乘法(戳此进入)引入例题#1广义矩阵乘法DDP例题#0例题#0.5......