本文主要是介绍密码+a simple problem(太原理工大学重现赛卡住的题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
密码+a simple problem(太原理工大学重现赛卡住的题
#include<bits/stdc++.h>
#define mod int(1e9+7)
using namespace std;
int n,l,r,ans;
int main(){cin>>n;while(n--){cin>>l>>r;int res=0;//6种情况if(l%2==0&&r&1){if( (r-l+1)/2 &1 )res=1;else res=0;}if(l%2==0&&r%2==0){if((r-l)/2 &1)res=1^r;else res=0^r;}if((l&1)&&(r&1)){if((r-l)/2 &1)res=l^1;else res=l^0;}if((l&1)&&(r%2==0)){if((r-l+1)/2 &1)res=l^0^r;else res=l^1^r;}ans=(ans+res)%mod;}cout<<ans;
}
太原理工大学重现赛的最后一道题,当时没做出来,现在觉得好简单啊
接下来这道题是最难的一道题
根据题意所给,推出公式
弄出系数矩阵
用矩阵运算求解
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
typedef long long LL;
typedef int mat[8][8];void mul(mat a,mat b){mat c={};for(int i=0;i<8;i++)for(int j=0;j<8;j++)for(int k=0;k<8;k++)c[i][j]=(c[i][j] + a[i][k]*b[k][j] )%mod;for(int i=0;i<8;i++)for(int j=0;j<8;j++)a[i][j]=c[i][j];
}void qpow(mat b,int n){mat c;for(int i=0;i<8;i++)for(int j=0;j<8;j++)c[i][j]=(i==j);for(;n;n/=2,mul(b,b)){if(n&1)mul(c,b);} memcpy(b,c,sizeof(c));
}const int N=100010;
int f[N],h[N],I[N],F[N];int a,b,x;
signed main(){cin>>a>>b>>x;//这是最难搞出来的系数矩阵,你要多少个元素,你要定义多少个变量//都是取决于你化简出来的公式int t[8][8]={{1,0,0,0,0,0,0,0},{-1,1,0,0,0,0,0,0},{1,0,1,0,0,0,0,0},{1,1,1,1,0,0,0,0},{a,0,a,0,a,0,1,0},{a,a,a,a,a,a,0,1},{b,0,b,0,b,0,0,0},{2*b,b,2*b,b,2*b,b,0,0}};//初始的东西而已,最后的答案是ans【n】=ans【n-1】*系数矩阵的第一列f[0]=0,f[1]=1;h[0]=0,h[1]=1;I[0]=0,I[1]=1;F[0]=0,F[1]=1;qpow(t,x-1);int ans=0;int init[8]={1,1,1,1,1,1,0,0};//这个是原向量//n-1个系数矩阵相乘后,最后的一步运算(也就是第n次运算要用到这个init向量for(int i=0;i<8;i++)ans=(ans+init[i]*t[i][0])%mod;cout<<ans;
}
这道题真的难
看着题解写的,顺着思路写下来finish后感觉真的蛮难的
爽!
弄了一下午了
真的爽!!!!!
这篇关于密码+a simple problem(太原理工大学重现赛卡住的题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!