2022/8/11 状压+矩阵快速幂

        今天肚子不舒服，做的题有点少，咋加上看了个状压加快速幂的题目，直接emo了，，，​

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

701C - They Are Everywhere 双指针

一开始用的是vector存坐标然后52个字母暴力遍历起点，T了，，

然后又想了一个奇葩的优先队列每次弹出最小坐标，然后用最大坐标减去最小坐标更新答案，也T了，，但是没想到竟然冲到了73个样例

最后看了题解的提示才想起双指针来，让r从1到n开始遍历，然后l为1，如果满足条件了，l就开始向右走，一直走到条件不满足为止，在此期间不断更新答案

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=100000000;
const int N = 2e5+5;
ll n,m,vis[55];
map<char,ll>mp;
char s[100005];
ll ans=1e18;
int main(){
    for(char i='a';i<='z';i++) mp[i]=i-'a'+1;
    for(char i='A';i<='Z';i++) mp[i]=i-'A'+27;
    scanf("%lld%s",&n,s+1);
    for(int i=1;i<=n;i++){
        if(!vis[mp[s[i]]]) m++;
        vis[mp[s[i]]]=i;
    }
    memset(vis,0,sizeof(vis));
    ll l=1,cnt=0;
    for(int i=1;i<=n;i++){
        if(!vis[mp[s[i]]]) cnt++;
        vis[mp[s[i]]]++;
        if(cnt==m){
            while(l<=i){
                ans=min(ans,i-l+1);
                vis[mp[s[l]]]--;
                if(vis[mp[s[l]]]<=0) cnt--;
                l++;
                if(cntbreak;
            }
        }
    }
    printf("%lld\n",ans);
    system("pause");
    return 0;
}

1616C - Representative Edges

可以发现公式就是等差数列求n项和，所以问题转化为至少修改几处可以使得该序列变为一个等差数列，首先n<=2是不用修改的，之后由于数据很小所以我们可以直接n方枚举，固定两个点求出d，然后暴力检查一共需要修改几处更新答案就可以了，注意检查时代码的写法，

这样是不对的

if(k
                else if(a[k]!=a[i]+(k-i)*d) sum++;

但这样就对了

if(k
                else if((a[k]-a[i])/(k-i)!=d) sum++;

ac代码

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=100000000;
double eps=1e-8;
const int N = 2e5+5;
ll t,n;
double a[110];
ll ans=1e18;
int main(){
    scanf("%lld",&t);
    while(t--){
        ans=1e18;
        scanf("%lld",&n);
        for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
        if(n<=2){
            printf("0\n");continue;
        }
        for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++){
            double d=(a[j]-a[i])/(j-i);
            
            ll sum=0;
            for(int k=1;k<=n;k++){
                if(k==i||k==j) continue;
                if(k
                else if((a[k]-a[i])/(k-i)!=d) sum++;
            }
            //cout<
            ans=min(ans,sum);
        }
        printf("%lld\n",ans);
    }
    
    system("pause");
    return 0;
}

P1357 花园 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 状压dp 矩阵快速幂

哇，这题真的难搞，学完了矩阵快速幂再来看这个题的题解还是非常吃力，因为这个构造矩阵竟然是要通过类似状压dp的方式来构造，设f[i]为状态为i时可以构造出的方案数，矩阵mat[j][i]是用来求f[i]下一个状态的转移矩阵，通过类似状压dp的方式求出，初始状态是mat[i][i]=1,最后的答案就是mat[i][i]的总和

题解 P1357 花园 - 琉璃想要变得可爱 - 洛谷博客

#include 
using namespace std;
#define ll long long
#define lowbit(i) ((i)&(-i))
const ll mod=1e9+7;
double eps=1e-8;
const int N = 2e5+5;
ll n,m,K,t,ans;
struct matrix{
    ll row,col;
    ll mat[35][35];
    matrix(){
        memset(mat,0,sizeof(mat));
    }
    void init(){
        *this=matrix();
        row=col=t;
        for(int i=0;i1;
    }
    matrix operator*(const matrix& a)const{
        matrix res=matrix();res.row=row,res.col=col;
        for(int i=0;i
        for(int j=0;j
        for(int k=0;k
        res.mat[i][j]=(res.mat[i][j]+mat[i][k]*a.mat[k][j]%mod)%mod;
        return res;
    }
    matrix matpow(ll b){
        matrix res=matrix();
        res.init();
        matrix base=*this;
        while(b){
            if(b&1) res=res*base;
            base=base*base;
            b>>=1;
        }
        return res;
    }
};
int main(){
    scanf("%lld%lld%lld",&n,&m,&K);
    t=1<
    matrix b=matrix();b.row=b.col=t;
    for(int i=0,j;i
        if(__builtin_popcount(i)>K) continue;
        j=i>>1;
        //表示j可以推出i
        b.mat[j][i]=1;
        j=(i>>1)|(1<<(m-1));
        if(__builtin_popcount(j)<=K)
            b.mat[j][i]=1;
    }
    matrix res=b.matpow(n);
    for(int i=0;i
    printf("%lld\n",ans);
    system("pause");
    return 0;
}

矩阵快速幂

上面的题目用到了就来看一下

 

 

 

Fibonacci Numbers - HDU 3117 - Virtual Judge (vjudge.net)矩阵快速幂

这个题上一年就做过了，但是不大懂，今天又来做，有些地方还是不大会，所以看了题解理解的更深了，其实这题没啥难的，难就难在要输出前四位和后四位上

斐波那契的通项公式 

减号后面的由于很小就不管了，前面的由于很大需要取对数化为小数保存起来，用的时候乘以10000就行

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//HDU火车头
//#include 
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=10000;
double eps=1e-8;
const int N = 2e5+5;
ll n,t;
struct matrix{
    ll row,col;
    ll mat[35][35];
    matrix(){
        memset(mat,0,sizeof(mat));
    }
    void init(){
        *this=matrix();
        row=col=t;
        for(int i=0;i1;
    }
    matrix operator*(const matrix& a)const{
        matrix res=matrix();res.row=row,res.col=col;
        for(int i=0;i
        for(int j=0;j
        for(int k=0;k
        res.mat[i][j]=(res.mat[i][j]+mat[i][k]*a.mat[k][j]);
        if(res.mat[i][j]>=100000000)
            res.mat[i][j]%=mod;
        }
        return res;
    }
    matrix matpow(ll b){
        matrix res=matrix();
        res.init();
        matrix base=*this;
 
        while(b){
      //cout<
            if(b&1) res=res*base;
            base=base*base;
            b>>=1;
        }
        return res;
    }
};
int main(){
    
    while(scanf("%lld",&n)!=EOF){
        if(!n){printf("0\n");continue;}
        t=2;
        matrix b=matrix();
        b.row=b.col=t;
        b.mat[0][0]=b.mat[0][1]=b.mat[1][0]=1;
        matrix ans=b.matpow(n-1);
        //cout<
        if(n<40) printf("%lld\n",ans.mat[0][0]);
        else{
            double x = log10(1 / sqrt(5)) + n * log10((1 + sqrt(5)) / 2.0);
			double y = x - (int)(x);//取小数是为了求科学计数法的1.xxxx
			int res = (int)1000LL*pow(10.0, y);
            cout << res << "...";
            printf("%0.4d\n",ans.mat[0][0]%mod);
        }
    }
    system("pause");
    return 0;
}