• 2022/8/11

    ​

    活动地址：CSDN21天学习挑战赛

    743C - Vladik and fractions

    通过样例就可以看出来了，x=n,y=n+1,z=n*(n+1)完全符合任何一种情况，当n=1时无解，感觉这题1500有点高了

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. #define lowbit(i) ((i)&(-i))
    5. const ll mod=10000;
    6. double eps=1e-8;
    7. ll n;
    8. int main(){
    9.     cin>>n;
    10.     if(n==1){
    11.         printf("-1\n");
    12.     }
    13.     else{
    14.         printf("%lld %lld %lld\n",n,n+1,n*(n+1));
    15.     }
    16.     system("pause");
    17.     return 0;
    18. }

    ​1165D - Almost All Divisors

    这题好多坑点，其实也是自己做这个题太莽了没注意到隐含的条件，想一下如果条件符合不是-1的情况下我们只需要输出d[1]*d[n]就可以了，可以试一试随便一个数都是等于第一个因子乘以最后一个的，前提是排好序的情况下；重点其实是判断-1的情况，wa了很多发，需要判断每个d[i]和d[n-i+1]的乘积是不是一样的，另外还需要判断每个d[i]的因子是否出现过，如果d[i]出现了因子却没出现这显然是不符合情况的

    1. #include 
    2. using namespace std;
    3. #define ll long long
    4. #define lowbit(i) ((i)&(-i))
    5. const ll mod=10000;
    6. double eps=1e-8;
    7. ll t,n,d[305],vis[1000006];
    8. ll lcm(ll a,ll b){
    9.     return a*b/__gcd(a,b);
    10. }
    11. bool su(ll x){
    12.     for(int i=2;i<=sqrt(x);i++)
    13.         if(x%i==0) return false;
    14.     return true;
    15. }
    16. int main(){
    17.     scanf("%lld",&t);
    18.     while(t--){
    19.         scanf("%lld",&n);
    20.         for(int i=1;i<=n;i++) scanf("%lld",&d[i]),vis[d[i]]=1;
    21.         sort(d+1,d+n+1);
    22.         ll flag=1,tm=d[1]*d[n];
    23.         for(int i=1;i<=n;i++){
    24.             for(int j=2;j<=sqrt(d[i]);j++){
    25.                 if(d[i]%j==0&&(vis[d[i]/j]==0||vis[j]==0)){flag=0;break;} 
    26.             }
    27.         }
    28.         for(int i=2;i<=(n+1)/2;i++){
    29.             if(d[i]*d[n-i+1]!=tm){flag=0;break;}
    30.         }
    31.         if(flag) printf("%lld\n",d[1]*d[n]);
    32.         else printf("-1\n");
    33.         for(int i=1;i<=n;i++) vis[d[i]]=0;
    34.     }
    35.     system("pause");
    36.     return 0;
    37. }

    Happy Necklace - HDU 6030 - Virtual Judge (vjudge.net) 矩阵快速幂

    好家伙连一个式子都推不出来，，，

    题意也弄错了，，应该是要求任意素数区间段内红色大于蓝色，问有多少种方案。

    我们先看2的时候，满足的有rr,br,rb,等于3的时候就要从2的时候转移过来只看后两位，rr可以变为rb,rr;br可以变为rr,rb不可以因为这样r就小于b了;rb可以变为br。可以看出rr可以有上一次的rr和br转移过来，br可以有上一次的rb转移过来，rb可以有上一次的rr转移过来，设a[i],b[i],c[i]为n=i时rr,br,rb的个数，则有a[i]=a[i-1]+b[i-1],b[i]=c[i-1],c[i]=a[i-1],而题目要求的是s[i]=a[i]+b[i]+c[i],所以

    s[i]=a[i]+b[i]+c[i]=2a[i-1]+b[i-1]+c[i-1]

    s[i-1]=2a[i-2]+b[i-2]+c[i-2]

    s[i-2]=2a[i-3]+b[i-3]+c[i-3]

    s[i-3]=2a[i-3]+b[i-3]+c[i-3]

    s[i]=2a[i-1]+b[i-1]+c[i-1]=3a[i-2]+2b[i-2]+c[i-2]

         =s[i-1]+a[i-2]+b[i-2]

         =s[i-1]+a[i-3]+b[i-3]+c[i-3]

         =s[i-1]+s[i-3];

    递推式就推出来了，转移矩阵也就好写了，注意要从4开始因为n>=2所以最小的s[n-1]是s[4]，另外最后乘起来的时候B矩阵的第一行所有的数都要参与乘法，即

    res.mat[0][0]*6LL%mod+res.mat[0][1]*4LL%mod+res.mat[0][2]*3LL%mod

     HDU - 6030 - Happy Necklace - （矩阵快速幂 ）_菜圾的博客-CSDN博客

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14. #include
    15. #include
    16. //HDU火车头
    17. //#include 
    18. #define ll long long
    19. #define lowbit(x) ((x)&(-x))
    20. using namespace std;
    21. const ll mod=1e9+7;
    22. double eps=1e-8;
    23.  
    24. struct matrix{
    25.     ll row,col;
    26.     ll mat[4][4];
    27.     matrix(){
    28.         memset(mat,0,sizeof(mat));
    29.     }
    30.     void init(){
    31.         *this=matrix();
    32.         row=col=3;
    33.         for(int i=0;i<3;i++) mat[i][i]=1;
    34.     }
    35.     matrix operator*(const matrix& a)const{
    36.         matrix res=matrix();res.row=row;res.col=col;
    37.         for(int i=0;i
    38.         for(int j=0;j
    39.         for(int k=0;k
    40.         res.mat[i][j]=(res.mat[i][j]+mat[i][k]*a.mat[k][j])%mod;
    41.         return res;
    42.     }
    43.     matrix matpow(ll b){
    44.         matrix res = matrix();
    45.         res.init();
    46.         matrix base=*this;
    47.         while(b){
    48.             if(b&1) res=res*base;
    49.             base=base*base;
    50.             b>>=1;
    51.         }
    52.         return res;
    53.     }
    54. };
    55. int main(){
    56.     ll t,n;
    57.     scanf("%lld",&t);
    58.     while(t--){
    59.         scanf("%lld",&n);
    60.         if(n==2) printf("3\n");
    61.         else if(n==3) printf("4\n");
    62.         else if(n==4) printf("6\n");
    63.         else{
    64.             matrix b=matrix();
    65.             b.row=b.col=3;
    66.             b.mat[0][0]=b.mat[0][2]=b.mat[1][0]=b.mat[2][1]=1;
    67.             matrix res=b.matpow(n-4LL);
    68.             //cout<
    69.             printf("%lld\n",(res.mat[0][0]*6LL%mod+res.mat[0][1]*4LL%mod+res.mat[0][2]*3LL%mod)%mod);
    70.         }
    71.     }
    72.     system("pause");
    73.     return 0;
    74. }
    75.

    Mathematician QSC - HDU 5895 - 矩阵快速幂+欧拉函数降幂

    这个题只要会矩阵快速幂的板子再加上欧拉函数的板子再加上欧拉降幂的公式就可以把这个题给过掉了，写代码花了很长时间，另外其实矩阵也不是很好推，但是由于昨天看的课中有个类型一样的式子就很快推出来了

    HDU 5895 矩阵快速幂+欧拉降幂公式+指数循环节_legend_PawN的博客-CSDN博客

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14. #include
    15. #include
    16. //HDU火车头
    17. //#include 
    18. #define ll long long
    19. #define lowbit(x) ((x)&(-x))
    20. using namespace std;
    21. ll mod=1e9+7;
    22. double eps=1e-8;
    23. struct matrix{
    24.     ll row,col;
    25.     ll mat[4][4];
    26.     matrix(){
    27.         memset(mat,0,sizeof(mat));
    28.     }
    29.     void init(){
    30.         *this=matrix();
    31.         row=col=4;
    32.         for(int i=0;i<4;i++) mat[i][i]=1;
    33.     }
    34.     matrix operator*(const matrix& a)const{
    35.         matrix res=matrix();res.row=row;res.col=col;
    36.         for(int i=0;i
    37.         for(int j=0;j
    38.         for(int k=0;k
    39.         res.mat[i][j]=(res.mat[i][j]+mat[i][k]*a.mat[k][j])%mod;
    40.         return res;
    41.     }
    42.     matrix matpow(ll b){
    43.         matrix res = matrix();
    44.         res.init();
    45.         matrix base=*this;
    46.         while(b){
    47.             if(b&1) res=res*base;
    48.             base=base*base;
    49.             b>>=1;
    50.         }
    51.         return res;
    52.     }
    53. };
    54. ll eulerfunc(ll x){
    55.     ll res=x;
    56.     for(ll i=2;i*i<=x;i++){
    57.         if(x%i==0){
    58.             res=res/i*(i-1);
    59.             
    60.             while(x%i==0) x/=i;
    61.         }
    62.     }
    63.     if(x>1) res=res/x*(x-1);
    64.     return res;
    65. }
    66. ll qpow(ll a,ll b,ll s){
    67.     ll res=1;
    68.     while(b){
    69.         if(b&1) res=res*a%s;
    70.         a=a*a%s;
    71.         b>>=1;
    72.     }
    73.     return res;
    74. }
    75. int main(){
    76.     ll t,n,y,x,s;
    77.     scanf("%lld",&t);
    78.     while(t--){
    79.         matrix b=matrix();
    80.         b.row=b.col=4;
    81.         b.mat[0][0]=b.mat[0][3]=b.mat[1][3]=b.mat[2][2]=b.mat[3][1]=1;
    82.         b.mat[0][1]=b.mat[0][2]=b.mat[1][1]=b.mat[1][2]=4;
    83.         b.mat[2][1]=2;
    84.         scanf("%lld%lld%lld%lld",&n,&y,&x,&s);
    85.         if(n*y==0){
    86.             printf("1\n");continue;
    87.         }
    88.         mod=eulerfunc(s+1);
    89.         matrix res=b.matpow(n*y-1);
    90.         ll g=(res.mat[0][0]+res.mat[0][1])%mod+mod;
    91.         //cout<
    92.         ll ans=qpow(x,g,s+1);
    93.         printf("%lld\n",ans);
    94.     }
    95.     system("pause");
    96.     return 0;
    97. }
    98.

    Matrix Power Series - POJ 3233 - 矩阵快速幂

    虽然题目变成矩阵了，但还是注意一下矩阵的特性，照样推就可以，忘了初始化c矩阵的行数和列数了，导致检错花费了半小时

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14. #include
    15. #include
    16. //HDU火车头
    17. //#include 
    18. #define ll long long
    19. #define lowbit(x) ((x)&(-x))
    20. using namespace std;
    21. ll mod=1e9+7;
    22. double eps=1e-8;
    23. int n,t,m,k;
    24. struct matrix{
    25.     int row,col;
    26.     int mat[62][62];
    27.     matrix(){
    28.         memset(mat,0,sizeof(mat));
    29.     }
    30.     void init(){
    31.         *this=matrix();
    32.         row=col=t;
    33.         for(int i=0;i1;
    34.     }
    35.     matrix operator*(const matrix& a)const{
    36.         matrix res=matrix();res.row=row;res.col=col;
    37.         for(int i=0;i
    38.         for(int j=0;j
    39.         for(int k=0;k
    40.         res.mat[i][j]=(res.mat[i][j]+mat[i][k]*a.mat[k][j])%mod;
    41.         return res;
    42.     }
    43.     matrix matpow(int b){
    44.         matrix res = matrix();
    45.         res.init();
    46.         matrix base=*this;
    47.         while(b){
    48.             if(b&1) res=res*base;
    49.             base=base*base;
    50.             b>>=1;
    51.         }
    52.         return res;
    53.     }
    54. };
    55.  
    56. int main(){
    57.     scanf("%d%d%d",&n,&k,&m);
    58.     mod=m;
    59.     t=2*n;
    60.     matrix b=matrix(),c=matrix();
    61.     b.row=b.col=c.row=c.col=t;
    62.     for(int i=0;i
    63.         b.mat[i][i]=1;
    64.         for(int j=0;j
    65.         scanf("%d",&c.mat[i][j]);
    66.         c.mat[i][j]%=mod;
    67.         c.mat[i+n][j]=c.mat[i][j];
    68.         b.mat[i][j+n]=c.mat[i][j];
    69.         b.mat[i+n][j+n]=c.mat[i][j];
    70.     }
    71.     }
    72.     
    73.     matrix res=b.matpow(k-1);
    74.     //cout<
    75.     //cout<
    76.     res=res*c;
    77.     for(int i=0;i
    78.         for(int j=0;j
    79.         printf("%lld ",res.mat[i][j]);
    80.         printf("\n");
    81.     }
    82.     system("pause");
    83.     return 0;
    84. }
    85.

    Kiki & Little Kiki 2 - HDU 2276 - 矩阵快速幂

    f[n][l]表示在第n秒，第l个字符的状态，则f[n][l]有两种情况

    1. f[n][l]=f[n-1][l]     //f[n-1][l-1]==0
    2. f[n][l]=1-f[n-1][l]   //f[n-1][l-1]==1

    进而发现可以转化成一种情况：f[n][l]=(f[n-1]l]+f[n-1][l-1])%2

    然后就可以造出转移矩阵

    \begin{bmatrix} f[n][1]\\ f[n][2]\\ ...\\ f[n][l] \end{bmatrix}=\begin{bmatrix} 1 & 0 &... & 0 & 1\\ 1& 1 &... & 0 & 0\\ & & ... & & \\ 0& 0 &... & 1 & 1 \end{bmatrix}*\begin{bmatrix} f[n-1][1]\\ f[n-1][2]\\ ...\\ f[n-1][l] \end{bmatrix}

    题目挺好的，玛德自己写的不知道为啥就是一直T，换了种题解的写法感觉并没有啥不同并且他还有memset，只是把求快速幂的函数从结构体中拿出来了，然后就能过，我他妈我的就不过，我的构造矩阵还不是n方，是n，玛德不让我过，这他妈的卡的那么严实吗，我浪费了得快一个小时，为了这个TLE，丫的毫无意义

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. #include
    14. #include
    15. #include
    16. //HDU火车头
    17. //#include 
    18. #define ll long long
    19. #define lowbit(x) ((x)&(-x))
    20. using namespace std;
    21. int mod=1e9+7;
    22. double eps=1e-8;
    23. int t,m;
    24. char s[110];
    25. struct matrix
    26. {
    27. 	int mat[150][150];
    28. 	matrix() {}
    29. 	matrix operator*(matrix const &b)const
    30. 	{
    31. 		matrix res;
    32. 		memset(res.mat, 0, sizeof(res.mat));
    33. 		for (int i = 0 ;i <=t; i++)
    34. 			for (int j = 0; j <= t; j++)
    35. 				for (int k = 0; k <=t; k++)
    36. 					res.mat[i][j] = (res.mat[i][j]+this->mat[i][k] * b.mat[k][j])%mod;
    37. 		return res;
    38. 	}
    39. };
    40. matrix pow_mod(matrix base, int n)
    41. {
    42. 	matrix res;
    43. 	memset(res.mat, 0, sizeof(res.mat));
    44. 	for (int i = 0; i 
    45. 		res.mat[i][i] = 1;
    46. 	while (n > 0)
    47. 	{
    48. 		if (n & 1) res = res*base;
    49. 		base = base*base;
    50. 		n >>= 1;
    51. 	}
    52. 	return res;
    53. }
    54. int main(){
    55.     while(~scanf("%d",&m)){
    56.     
    57.     scanf("%s",&s);
    58.     t=strlen(s);mod=2;
    59.     // matrix base;
    60.     // int x=t-1;
    61.     // for(int i=0;i
    62.     //     b.mat[i][x]=1;
    63.     //     x=(x+1)%t;
    64.     //     b.mat[i][x]=1;
    65.     //     c.mat[i][0]=s[i]-'0';
    66.     // }
    67.     matrix base;
    68.     for(int i=0;i
    69.             for(int j=0;j
    70.             base.mat[i][j]=0;
    71.         base.mat[0][0]=1;
    72.         base.mat[0][t-1]=1;
    73.         for(int i=1;i
    74.             for(int j=1;j
    75.         {
    76.             if(i==j)
    77.             {
    78.                 base.mat[i][j]=1;
    79.                 base.mat[i][j-1]=1;
    80.             }
    81.         }
    82.     
    83.      matrix res=pow_mod(base,m);
    84.     for(int i=0;i
    85.         int sum=0;
    86.         for(int j=0;j
    87.             {
    88.                 sum=(sum+res.mat[i][j]*(s[j]-'0'))%mod;
    89.             }
    90.         printf("%d",sum);
    91.     }
    92.     printf("\n");
    93.     }
    94.     system("pause");
    95.     return 0;
    96. }
    97.

  • 相关阅读:
    29.Xaml TreeView控件----＞树形控件，节点的形式显示数据
    基于Spring Boot应用Java原生JDBC操作数据库(查增改删)
    Netty高性能之Reactor模型
    弹框确认按钮，请求两个接口跳转刷新页面,并使用async和await将异步改成同步的数据?
    大数据技术学习笔记（二）—— Hadoop 运行环境的搭建
    CAA的VS Studio安装
    使用gradio创建一个提取pdf、excel中表格数据的demo
    nginx(五十七)ngx_http_upstream模块(二)一致性hash算法
    Spark+Hadoop环境搭建
    华为机试真题 C++ 实现【连接器问题】【2022.11 Q4新题】
  • 原文地址：https://blog.csdn.net/weixin_52621204/article/details/126283333