69 条题解

  • 3
    @ 2020-10-13 14:39:56
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <deque>
    using namespace std;
    
    namespace dts
    {
        typedef unsigned long long ull;
        
        ull N,M,K;
        
        struct matrix
        {
            ull n,m;
            vector<vector<ull>> mat;
            
            void set_size(ull nv,ull mv)
            {
                n=nv,m=mv;
                mat.resize(n);
                for (ull i=0;i<n;i++)
                    mat[i].resize(m,0);
            }
            
            matrix operator * (matrix ma)
            {
                //matrix A,B A*B時有A.m=B.n
                matrix ans;
                ans.set_size(n,ma.m);
                for (ull i=0;i<n;i++)
                    for (ull j=0;j<ma.m;j++)
                        for (ull k=0;k<m;k++)
                            ans.mat[i][j]+=mat[i][k]*ma.mat[k][j];
                return ans;
            }
            
            matrix operator *= (matrix ma)
            {
                return (*this)=(*this)*ma;
            }
            
            matrix pow(ull x)
            {
                matrix m,ans;
                m=(*this);
                ans.set_size(n,n);
                for (ull i=0;i<n;i++)
                    ans.mat[i][i]=1;
                for (ull i=x;i;m*=m,i>>=1)
                    if (i&1)
                        ans*=m;
                return ans;
            }
        };
        
        matrix a,op[10],opm,opp,ans;
        
        void main()
        {
            while (~scanf("%llu%llu%llu",&N,&M,&K))
            {
                a.set_size(N,N),opm.set_size(N,N);
                for (ull i=0;i<N;i++)
                    a.mat[0][i]=i,opm.mat[i][i]=1;
                for (ull i=0;i<M;i++)
                {
                    op[i].set_size(N,N);
                    for (ull j=0,temp;j<N;j++)
                    {
                        scanf("%llu",&temp);
                        op[i].mat[--temp][j]=1;
                    }
                    opm*=op[i];
                }
                opp=opm.pow(K/M);
                for (ull i=0;i<K%M;i++)
                    opp*=op[i];
                ans=a*opp;
                for (ull i=0;i<N;i++)
                    printf("%llu ",ans.mat[0][i]+1);
                printf("\n");
            }
        }
    }
    
    int main()
    {
        dts::main();
    }
    
  • 2
    @ 2019-10-20 20:24:31
    //矩阵快速幂?那是什么,能吃吗?
    //确实是用到了一点快速幂的思想,不过具体来说用倍增就能够实现
    //思路和倍增LCA类似,先搞出来跑完一轮后的情况,再搞出跑完2^i轮后的情况就行了
    //之后对k进行一个比较诡异的拆分
    //注意理解输入的部分,我们的数组[i][j]里存的是“i操作后j位置的数会去哪”,而原题给的是“i操作后j位置是原来哪个位置的数”,要转换一下
    #include<cstdio>
    using namespace std;
    int en[210],dp[60][210],cao[20][210];
    int main()
    {
        int n,m,k,i,j,ha;
        scanf("%d%d%d",&n,&m,&k);
        for(i=1;i<=m;i++)
         for(j=1;j<=n;j++)
         {
            scanf("%d",&ha);
            cao[i][ha]=j;
         }
        for(i=1;i<=n;i++)
         {
            ha=i;
            for(j=1;j<=m;j++)
             ha=cao[j][ha];
            dp[0][i]=ha;
         }
         for(i=0;(1<<i)*m<=k&&(1<<i)*m>=0;i++)
          for(j=1;j<=n;j++)
           dp[i+1][j]=dp[i][dp[i][j]];
        for(i=1;i<=n;i++)
         en[i]=i;
        ha=27;
        while(k&&ha>=0)
        {
            if((1<<ha)*m>k)
             {
                ha--;
                continue;
             }
            for(i=1;i<=n;i++)
             en[i]=dp[ha][en[i]];
            k-=(1<<ha)*m;
        }
        for(i=1;i<=k;i++)
         for(j=1;j<=n;j++)
          en[j]=cao[i][en[j]];
        for(i=1;i<=n;i++)
         for(j=1;j<=n;j++)
          if(i==en[j])
           printf("%d ",j);
        return 0;
    }
    
  • 1
    @ 2018-07-04 09:31:46

    置换+快速幂

    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    #define pos(x,y) (x+(y)*n)
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=1000000007;
    const double eps=1e-8;
    
    int n,m,k;
    int tmp[101];
    struct node {
        int x[101];
        node operator*(node a) {
            node res;
            FOR(i,n) res.x[i]=x[a.x[i]];
            return res; 
        }
        void operator=(node a) {
            FOR(i,n) x[i]=a.x[i];
        }
    } a[11];
    node s;
    node b;
    node qpow(node a,int b) {
        node res=s;
        while (b) {
            if (b&1) res=res*a;
            a=a*a;
            b>>=1;
        }
        return res;
    }
    int main() {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        cin>>n>>m>>k;
        FOR(i,m) FOR(j,n) {
            cin>>a[i].x[j];
        }
        int q=k/m,r=k%m;
        FOR(i,n) s.x[i]=i;
        b=a[1];
        REP(i,2,m) b=b*a[i];
        b=qpow(b,q);
        s=s*b;
        FOR(i,r) s=s*a[i];
        FOR(i,n) cout<<s.x[i]<<" ";
        cout<<endl;
        return 0;
    }
    
  • 1
    @ 2017-09-20 09:52:21

    先处理出变换m次的矩阵,然后用矩阵快速幂得到矩阵,如果有多余的,模拟

    #include<bits/stdc++.h>
    using namespace std;
    const int N=200,M=10+5;
    typedef long long ll;
    int n,m;ll K;
    struct matrix 
    {
        static const int MAXN=100+10;
        ll n,m,num[MAXN][MAXN];
        void init(int x,int y)
        {
            n=x;m=y;
            memset(num,0,sizeof(num));
        }
        void Ibuild(){if(n==m)for(int i=1;i<=n;i++)num[i][i]=1;}
    }step[M];
    matrix I,ans;
    matrix operator *(matrix a,matrix b)
    {
        matrix c;
        c.init(a.n,b.m);
        for(int i=1;i<=c.n;i++) 
            for(int j=1;j<=c.m;j++)
                for(int k=1;k<=a.m;k++) 
                    c.num[i][j]=(c.num[i][j]+a.num[i][k]*b.num[k][j]);
        return c;
    }
    matrix qpow(matrix a,ll y)
    {
        matrix ans;
        ans.init(a.m,a.m);
        ans.Ibuild();
        for(ll i=y;i;i>>=1)
        {
            if(i&1)ans=ans*a;
            a=a*a;
        }
        return ans;
    }
    int main()
    {
        scanf("%d%d%lld",&n,&m,&K);
        I.init(n,n);I.Ibuild();
        ans.init(1,n);
        for(int i=1;i<=n;i++)ans.num[1][i]=i;
        for(int i=1;i<=m;i++)
        {
            step[i].init(n,n);
            for(int j=1;j<=n;j++)
            {
                int x;scanf("%d",&x);
                step[i].num[x][j]=1;
            }
        }   
        for(int i=1;i<=m;i++) I=I*step[i];
        ll t=floor(K/m);
        I=qpow(I,t);
        for(int i=1;i<=K%m;i++) I=I*step[i];
        ans=ans*I;
        for(int i=1;i<=n;i++)printf("%lld ",ans.num[1][i]);
        return 0;
    }
    
  • 0
    @ 2017-09-13 13:45:16

    递归会RE!!!!!!!!!!不要递归快速幂!!!!!!!!!!

  • 0
    @ 2017-08-05 12:22:25
    
    var aa,ex,tmp,b:array[0..100]of longint;
    
    a:array[0..10,0..100]of longint;
    
    k:int64;
    
    j,circle,n,m,i,tot:longint;
    
    flag:boolean;
    
    procedure make(p:longint);
    
    var i:longint;
    
    begin
    
    tmp:=b;
    
    for i:=1 to m do
    
    b[i]:=tmp[a[p,i]];
    
    end;
    
    begin
    
    readln(m,n,k);
    
    for i:=0 to n-1 do
    
    for j:=1 to m do read(a);
    
    for i:=1 to m do b[i]:=i;
    
    i:=n-1;ex:=b;tot:=0;flag:=false;
    
    while k>0 do
    
    begin
    
    dec(k);
    
    tot:=tot+1;
    
    i:=(i+1)mod n;
    
    make(i);
    
    if tot=10000*n then begin flag:=true;aa:=b;break;end;
    
    end;
    
    if flag then begin
    
    while K>10000*n do
    
    begin
    
    k:=k-10000*n;
    
    tmp:=b;
    
    for j:=1 to m do b[j]:=tmp[aa[j]];
    
    end;
    
    i:=n-1;
    
    while k>0 do
    
    begin
    
    dec(k);
    
    i:=(i+1)mod n;
    
    make(i);
    
    end;
    
    end;
    
    for i:=1 to m-1 do write(b[i],' ');
    
    writeLn(b[m]);
    
    end.
    
  • 0
    @ 2016-11-16 20:44:01

    矩阵快速幂。好丑...
    M67的博客里有教程.
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;

    #define LL long long
    #define f(a,b,c) for(int a=(b);a<=(c);a++)
    #define f2(a,b,c) for(int a=(b);a>=(c);a++)

    #ifdef WIN32
    #define AUTO "%I64d"
    #else
    #define AUTO "%lld"
    #endif

    const int N=105;

    int n,m,k;

    struct Mat{
    int n,m;
    int s[N][N];
    Mat(){
    memset(s,0,sizeof(s)); n=m=0;
    }
    }mat[11],stt,ans;

    void show(Mat a)
    {
    f(i,1,a.n) {
    f(j,1,a.m) cout<<a.s[i][j]<<" ";
    cout<<endl;
    }
    cout<<endl;
    }

    Mat get_mat()
    {
    Mat ret; ret.m=ret.n=n;
    f(i,1,n) {
    int ai;
    scanf("%d",&ai);
    ret.s[i][ai]=1;
    }
    return ret;
    }

    Mat Init()
    {
    Mat ret; ret.m=1; ret.n=n;
    f(i,1,n) ret.s[i][1]=i;
    return ret;
    }

    Mat mat_mul(Mat a,Mat b)
    {
    Mat ret; ret.n=a.n; ret.m=b.m;
    f(i,1,a.n)
    f(kk,1,a.m) if(a.s[i][kk])
    f(j,1,b.m) ret.s[i][j]+=a.s[i][kk]*b.s[kk][j];
    return ret;
    }

    Mat Identity(int n)
    {
    Mat ret; ret.n=ret.m=m;
    f(i,1,n) ret.s[i][i]=1;
    return ret;
    }

    Mat mat_pow(Mat a,int x)
    {
    //if(x==0) return Identity(a.n);
    if(x==1) return a;
    Mat ret;
    ret=mat_pow(a,x>>1);
    ret=mat_mul(ret,ret);
    if(x%2) ret=mat_mul(ret,a);
    return ret;
    }

    int main()
    {
    freopen("in.txt","r",stdin);

    cin>>n>>m>>k;
    stt=Init();
    f(i,1,m) {
    mat[i]=get_mat();
    mat[0]= i==1? mat[i]:mat_mul(mat[i],mat[0]);
    //show(mat[0]);
    }

    mat[0]=mat_pow(mat[0],k/m);
    f(i,1,k%m) mat[0]=mat_mul(mat[i],mat[0]);
    ans=mat_mul(mat[0],stt);

    f(i,1,n) cout<<ans.s[i][1]<<" "; cout<<endl;
    return 0;
    }```

  • 0
    @ 2016-05-07 19:46:47

    测试数据 #0: Accepted, time = 0 ms, mem = 800 KiB, score = 8
    测试数据 #1: Accepted, time = 0 ms, mem = 804 KiB, score = 8
    测试数据 #2: Accepted, time = 0 ms, mem = 804 KiB, score = 8
    测试数据 #3: Accepted, time = 0 ms, mem = 800 KiB, score = 8
    测试数据 #4: Accepted, time = 0 ms, mem = 804 KiB, score = 8
    测试数据 #5: Accepted, time = 15 ms, mem = 800 KiB, score = 12
    测试数据 #6: Accepted, time = 0 ms, mem = 800 KiB, score = 12
    测试数据 #7: Accepted, time = 0 ms, mem = 804 KiB, score = 12
    测试数据 #8: Accepted, time = 0 ms, mem = 804 KiB, score = 12
    测试数据 #9: Accepted, time = 0 ms, mem = 800 KiB, score = 12
    Accepted, time = 15 ms, mem = 804 KiB, score = 100
    AC很简单~
    试了两次,第一次把k%m给写成了k/m,真无语了。

  • 0
    @ 2015-10-13 14:25:54

    快速幂+矩阵转换。
    将m次转换看作一次,利用快速幂的思想求解 [转换]^(k/m) ,剩下的k%m次转换补上。

  • 0
    @ 2014-10-07 10:55:08

    矩乘快速幂

  • 0
    @ 2012-09-14 00:01:43

    VijosNT Mini 2.0.5.7 Special for Vijos

    编译通过...

    ├ 测试数据 01:答案正确... (108ms, 832KB)

    ├ 测试数据 02:答案正确... (104ms, 832KB)

    ├ 测试数据 03:答案正确... (0ms, 832KB)

    ├ 测试数据 04:答案正确... (0ms, 832KB)

    ├ 测试数据 05:答案正确... (0ms, 832KB)

    ├ 测试数据 06:答案正确... (0ms, 832KB)

    ├ 测试数据 07:答案正确... (0ms, 832KB)

    ├ 测试数据 08:答案正确... (0ms, 832KB)

    ├ 测试数据 09:答案正确... (0ms, 832KB)

    ├ 测试数据 10:答案正确... (0ms, 832KB)

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 213ms / 832KB

    终于AC了~犯了一个很SB的错,查了很久,原来是数组开错了~无语~

    矩阵乘法~

    这题遇到的一个最大的问题就是一开始用递归写,爆栈~

    后来改为非递归形式,就AC了~

    也是看Matrix67的论文来搞的~~

    V5~

  • 0
    @ 2012-07-31 20:19:49

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 9ms

    ├ 测试数据 10:答案正确... 353ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:362ms

    最后一个点循环节挺长的,>100000

  • 0
    @ 2010-03-11 19:12:42

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 275ms

    ├ 测试数据 10:答案正确... 228ms

    第二次用矩阵

    结果还是把顺序写反了

  • 0
    @ 2009-11-08 19:32:48

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    秒杀不难呀

  • 0
    @ 2009-11-01 10:51:09

    快速幂...AC人数这么少

    评测机诡异...longint打成integer不runtime error 201反而有输出结果

    数组开小了也是这样

  • 0
    @ 2009-10-23 18:05:34

    我把N和M范围看倒了,结果arr类型设为ARRAY[1..10]……8个点杯具……

    现在AC了。

  • 0
    @ 2009-10-20 10:05:05

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 119ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 9ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:运行超时...

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:76 有效耗时:128ms

    二分居然超时- -

    但是flag显示我ac了

    好诡异的sunny

  • 0
    @ 2009-10-06 17:15:04

    Program Vijos_P1049;

    Type Arr= Array [1..100] Of Byte;

    Var

    a, b, c, t: Arr;

    i, j, m, n, p: Byte; k: dWord;

    Function Bh(k: dWord): Arr;

    Var d, t: Arr;

    Begin

    If k=1 Then Bh:=a Else Begin

    t:=Bh(k Shr 1);

    For j:=1 To n Do d[j]:=c[t[j]];

    For j:=1 To n Do Bh[j]:=d[t[j]];

    If Odd(k) Then Begin

    For j:=1 To n Do d[j]:=Bh[a[j]];

    Bh:=d

    End

    End

    End;

    Begin

    Read(n, m, k); For j:=1 To n Do c[j]:=j;

    a:=c; t:=c;

    For i:=1 To m Do Begin

    For j:=1 To n Do

    Begin Read(p); b[j]:=a[p] End;

    a:=b; If i=k Mod m Then t:=a

    End;

    k:=k Div m; If k=0 Then b:=c Else b:=Bh(k);

    For j:=1 To n Do Write(b[t[j]], ' ')

    End.

信息

ID
1049
难度
5
分类
组合数学 点击显示
标签
递交数
1415
已通过
477
通过率
34%
被复制
7
上传者