P13417 [COCI 2012/2013 #4] DLAKAVAC 题解

· · 题解

令最初患病 n 位居民编号分别为 a_1,a_2,\dots,a_n。注意到在第 k 天，被感染的居民一定能被表示为 a_1^{p_1} a_2^{p_2} \dots a_n^{p_n} \pmod m（其中 p_1,p_2,\dots,p_n \ge 0 且 \sum p = n）。

这个结构很像矩阵快速幂，但是如果你建出矩阵来就有 O(m^3) 了根本过不去。事实上这题根本用不到矩阵，我们用两个序列做相乘就行了。

怎么乘啊？譬如说我们现在有 a 和 b 两个 bool 序列，分别是在 k_1 天和 k_2 天时每位居民是否患病的情况（1 表示患病，0 表示未患病），而根据上面提到的，如果存在一个 a_x = 1 和一个 b_y = 1，显然在第 k_1 + k_2 天时居民 a_x b_y \pmod m 肯定是患病的。于是我们就能实现一个 O(m^2) 的乘法了。

用快速幂的思想做即可，总时间复杂度 O(m^2 \log k)。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 1505;
struct Mat{bool a[N];}Ans,Bas;
LL Day,n,m;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
Mat Mul(Mat A,Mat B){
    Mat C;for(int i=0;i<n;i++)C.a[i]=0;
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)
        if(A.a[i]&&B.a[j])C.a[i*j%n]=1;return C;
}
int main(){
    Day=read(),n=read(),m=read();Ans.a[1]=1;
    for(int i=1;i<=m;i++){int x=read();Bas.a[x]=1;}
    while(Day){
        if(Day&1)Ans=Mul(Ans,Bas);
        Bas=Mul(Bas,Bas),Day>>=1;
    }for(int i=0;i<n;i++)
        if(Ans.a[i])cout<<i<<" ";cout<<"\n";
    return 0;
}

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！