题解 - Vijos

4

Sky1231 (sky1231) LV 10 @ 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

猫粮寸断 LV 10 @ 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

Goodhao LV 10 @ 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

Lifel LV 8 @ 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

137shoebills LV 5 @ 2017-09-13 13:45:16

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

0

lixuanjing LV 9 @ 2017-08-21 15:42:32

http://blog.csdn.net/lixuanjing2016/article/details/77367640

0

qq913653500 LV 10 @ 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

Fop_zz LV 10 @ 2017-03-24 10:27:47

http://blog.csdn.net/Fop_zz/article/details/65627594

0

Odin. LV 8 @ 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

shenmiren LV 8 @ 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

hahalidaxin LV 8 @ 2015-10-13 14:25:54

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

0

wzms_hwj LV 10 @ 2014-10-07 10:55:08

矩乘快速幂

0

johnbug LV 5 @ 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

jiaoyunhao LV 10 @ 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

我不是你 LV 8 @ 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

dyqdwz LV 8 @ 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

grantlj LV 8 @ 2009-11-01 10:51:09

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

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

数组开小了也是这样

0

Mato完整版 LV 10 @ 2009-10-23 18:05:34

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

现在AC了。

0

Jungle LV 10 @ 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

hbmhalley LV 8 @ 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.

题解

69 条题解

送给圣诞夜的礼品

信息

状态

开发

支持

题解

69 条题解

送给圣诞夜的礼品

信息

状态

开发

支持

还没有账户？

登录