头像

儒雅随和の总分没有751不换名字

CQYCZX




离线:3个月前


新鲜事 原文

祝NOIP rp++


新鲜事 原文

CSP-S T1出题人和出数据人 nmsl



开了各种玩意才艹过去

看没有题解,就交了个(


很有趣的一道题

看到这种求数列的题就感觉是矩阵快速幂

接近于求个斐波拉契数列

但是中间会有转移方程不同的地方

很烦

那么我们就可以想到通过要减一的地方分段矩阵快速幂,那就可以解决这一个问题

很显然,斐波拉契在$mod\space p$下是会有循环节的

那么就可以通过找到循环节然后进行分段了

但是我们还有一个性质

如果$fib_{i-1}+fib_{i-2}\equiv 1\pmod k$

那么$fib_i=fib_{i-1}+fib_{i-2}-1$

否则$fib_i=fib_{i-1}+fib_{i-2}$

那么我们可以发现一个有趣的性质

如果满足$fib_{i-1}+fib_{i-2}\equiv 1\pmod k$

那么$fib_i\equiv 0 \pmod k$

而且$fib_{i+1}=fib_{i+2}$

那么我们把$fib_i\equiv 0\pmod k$的数拿来分段

我们可以发现每一段的数都是数列普通斐波拉契与一个数的乘积

那么我们关键便是找出这个数字

我们发现他满足同余方程$x*fib_j \equiv1 \pmod{k}$

那么我们只要预处理出所有的$fib_j$的逆元即可

然后通过矩阵快速幂分段搞即可,矩阵也很好推

#include<bits/stdc++.h>
#pragma GCC optimize("2")
#pragma GCC optimize("3")
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#define re return
#define ll long long
#define N 2000011
using namespace std;
ll n,k,p;
struct Jack{
    ll f[4][4];
    Jack(){memset(f,0,sizeof(f));}
    inline Jack operator *(const Jack &b)const{
        Jack ans;
        int i,j,k;
        for(k=1;k<=3;++k)
        for(i=1;i<=3;++i)
        for(j=1;j<=3;++j)
        ans.f[i][j]=((ans.f[i][j]+f[i][k]*b.f[k][j]%p)%p+p)%p;
        re ans;
    }
    inline void one( ){
        int i,j;
        for(i=1;i<=3;++i)f[i][i]=1;
    }
    inline void pre_one( ){
        f[1][1]=f[1][2]=f[2][1]=f[3][3]=1;
    }
    inline void pre_two( ){
        pre_one( );
        f[3][1]=-1;
    }
    inline void pre_three( ){
        f[3][1]=f[3][3]=1;
    }
};
inline Jack qui(Jack a,ll b){
    Jack ans;
    ans.one( );
    while(!!b){
        if(b&1)ans=ans*a;
        a=a*a,b>>=1;
    }
    re ans;
}
inline void exgcd(ll a,ll b,ll &x,ll &y,ll &d){
    if(!b){d=a,x=1,y=0;return;}
    exgcd(b,a%b,y,x,d);
    y-=a/b*x;
}
inline ll getinv(ll a,ll p){
    ll x,y,d;
    exgcd(a,p,x,y,d);
    if(d!=1)re -1;
    re (x%p+p)%p;
}
ll f[N],len[N],tot,q[N],vis[N];
int main( ){
    scanf("%lld%lld%lld",&n,&k,&p);
    int i;
    f[1]=f[2]=1;
    if(n<=2){puts("1");re 0;}
    for(i=3;i<=2e6;++i){
        f[i]=(f[i-1]+f[i-2])%k;
        if(f[i]==1&&!len[1])len[1]=i;
        ll inv(getinv(f[i],k));
        if(inv!=-1&&!len[inv])len[inv]=i;
    }
    ll now(1),t(0),l;
    int flag(0);
    while(1){
        l=len[now];
        q[++tot]=now,vis[now]=tot;
        if(!l){
            for(i=1;i<tot;++i)t+=len[q[i]];
            flag=1;
            break;
        }
        now=(now*f[l-1])%k;
        if(!!vis[now]){
            for(i=1;i<vis[now];++i)t+=len[q[i]];
            break;
        }
    }
    Jack a,tr1,tr2;
    tr1.pre_one( ),tr2.pre_two( ),a.pre_three( );
    if(n<=t){
        --len[1],--n;
        for(i=1;i<vis[now];++i)
        if(n>=len[q[i]]){
            a=a*qui(tr1,len[q[i]]-1)*tr2;
            n-=len[q[i]];
        }else{
            printf("%lld\n",(a*qui(tr1,n)).f[3][1]);
            re 0;
        }
    }else{
        --len[1];
        n-=t;
        for(i=1;i<vis[now];++i)a=a*qui(tr1,len[q[i]]-1)*tr2;
        if(!!flag){
            printf("%lld\n",(a*qui(tr1,n)).f[3][1]);
            re 0;
        }else{
            ll size(0);
            Jack tr;
            tr.one( );
            for(i=vis[now];i<=tot;++i){
                tr=tr*qui(tr1,len[q[i]]-1)*tr2;
                size+=len[q[i]];
            }
            a=a*qui(tr,n/size);
            n=n%size;
            for(i=vis[now];i<=tot;++i)
            if(n>=len[q[i]]){
                a=a*qui(tr1,len[q[i]]-1)*tr2;
                n-=len[q[i]];
            }else{

                printf("%lld\n",(a*qui(tr1,n)).f[3][1]);
                re 0;
            }
        }
    }
//  puts("WORK");
}



记得开O2!!!

记得开O2!!!

记得开O2!!!


我们可以发现这是一个裸的01背包,不过w的值十分大,导致O(nw)T

那么我们要考虑性质$w=a*2^b,a\leq10,b\leq30$

那么可以发现如果w过于庞大的话那么久浪费了那么全为零的部分

然后我们可以将w分为两个部分,一个大于等于$2^{15}$,一个小于$2^{15}$

那么我们可以把大于的右移15位,然后就可以分成两个部分dp然后合并即可

#include<bits/stdc++.h>
#pragma GCC optimize("2")
#pragma GCC optimize("3")
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#define Up(i,x,y) for(int i(x);i<=y;++i)
#define Dw(i,y,x) for(int i(y);i>=x;--i)
#define N 111
#define M 3010001
using namespace std;
struct BB{
    int n,sum;
    int w[N],v[N];
    int f[M];
    inline void clear(){n=0;memset(f,0,sizeof(f));sum=0;}
    inline void insert(int W,int V){w[++n]=W,v[n]=V;sum+=W;}
    inline void dp( ){
        Up(i,1,n)
        Dw(j,sum,w[i])
        f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
    inline void out( ){
        Up(i,1,n)
        printf("%d %d\n",w[i],v[i]);
    }
}f1,f2;
int n,m;
const int P(1<<12);
inline void work( ){
    f1.clear( ),f2.clear( );
    scanf("%d%d",&n,&m);
    if(n==m&&n==-1)exit(0);
    int w,v;
    Up(i,1,n){
        scanf("%d%d",&w,&v);
        if((w&(-w))<=P){
            f1.insert(w,v);
//          printf("f1:%d %d\n",w,v);
        }else{
            f2.insert(w>>12,v);
//          printf("f2:%d %d\n",w,v);
        }
    }
//  puts("f1:");
//  f1.out( );
//  puts("f2:");
//  f2.out( );
//  puts("ans:");
    f2.sum=min(f2.sum,262144);
    f1.dp( );f2.dp( );
    int ans(0),fuck;
    Up(i,0,f2.sum){
        if(m<(i<<12))break;

        if(ans<f1.f[min(m-(i<<12),f1.sum)]+f2.f[i]){
            ans=f1.f[min(m-(i<<12),f1.sum)]+f2.f[i];
            fuck=i;
        }
    }
    printf("%d\n",ans);
}
int main( ){
//  freopen("r.in","r",stdin);
//  freopen("r.out","w",stdout);
    while(1)work( );
}



感觉这个数据+时间把正解都卡了QwQ



新鲜事 原文

为什么感觉学计算机的人均都有女朋友...



如何用Dev.c++实现将光标移到指定位置,指定一个位置使其填充为另外一个字符

本人oier,可以的话只用给函数就行,对原理不感兴趣,解释一下参数就行QwQ

拒绝0回复惨案



新鲜事 原文

我有npy了!!!


新鲜事 原文

我真的遇得到!!! jf教练就为了一天训练就义正言辞地把毕业典礼旷了????


新鲜事 原文

老师叫写题解三部曲 1.写 2.给老师看 3.交到ACWING