国庆训练10.2
开荒第一题题面题解源码
开荒第二题题面题解源码
开荒第一题
tag:简单，数论，费马小定理
题面
1917: [HNOI2008]越狱
时间限制:1秒 内存限制:162MB
题目描述 监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果 相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
输入 输入两个整数M，N.1<=M<=108,1<=N<=1012
输出 可能越狱的状态数，模100003取余 样例输入
2 3
样例输出
6
提示 6种状态为(000)(001)(011)(100)(110)(111)
题解
每个房间的一个人信仰M个宗教中的一种，则N个房间共有MN种状态，其中不可越狱的状态：第一个房间的人可从M个宗教中选一，剩余N-1个房间的人不能和前一个人的宗教相同(否则会越狱)，有(M-1)个宗教选择，共M*(M-1)(N-1)种状态。则最终可越狱的状态：MN- M*(M-1)(N-1)。最终答案：((MN- M*(M-1)(N-1)))%mod。运用费马小定理(ab%p=ab%(p-1)%p)进行降幂,并运用各种求余公式整理得： (MN%(mod-1)%mod- M%mod*((M-1)(N-1)%(mod-1)%mod)+mod)%mod 最后，对其进行计算即可。
源码
#include
<iostream
>
using namespace std
;
typedef long long ll
;
const ll mod
=1e5+3;
ll
fun(ll a
,ll b
){
ll i
;
ll ans
=1;
for(i
=0;i
<b
;i
++){
ans
*=a
;
ans
%=mod
;
}
return ans
;
}
int
main(int argc
, char
** argv
) {
ll n
,m
,a
,b
,c
,d
,e
;
cin
>>m
>>n
;
a
=n
%(mod
-1);
b
=fun(m
,a
);
c
=(n
-1)%(mod
-1);
d
=fun(m
-1,c
);
m
%=mod
;
d
*=m
;
d
%=mod
;
e
=(b
-d
+mod
)%mod
;
cout
<<e
;
return 0;
}
开荒第二题
tag:位运算，矩阵快速幂，状态压缩
题面
5758: [Jsoi2016]位运算
时间限制:20秒 内存限制:512MB
题目描述 JYY最近在研究位运算。他发现位运算中最有趣的就是异或（xor）运算。对于两个数的异或运算，JYY发现了一个结论：两个数的异或值为0当且仅当他们相等。于是JYY又开始思考，对于N个数的异或值会有什么性质呢？ 【问题描述】 JYY想知道，如果在0到R-1的范围内，选出N个不同的整数，并使得这N个整数的异或值为0，那么一共有多少种选择的方法呢？（选择的不同次序并不作重复统计，请参见样例）JYY是一个计算机科学家，所以他脑海里的R非常非常大。为了能够方便的表达，如果我们将R写成一个0-1串，那么R是由一个较短的0-1串S重复K次得到的。比如，若S=“101”，K=2，那么R的2进制表示则为“101101”。由于计算的结果会非常大，JYY只需要你告诉他选择的总数对10^9+7取模的结果即可。 输入 第一行包含两个正整数N和K。 接下来一行包含一个由0和1组成的字符串S 我们保证S的第一个字符一定为1。 3<=N<=7,1<=k<=10^5,1<=|S|<=50 输出 一行一个整数，表示选择的方案数对10^9+7取模的值。 样例输入
3 1 100
样例输出
1
提示 对于第一个样例， 唯一的一种选择方法是选择 {1, 2, 3}。
题解
我推出了规律：所有N个数的第i位中‘1’的个数必须为偶数，才能使最终结果为0，但是接下来就没有思路了…… 在网上搜了题解：题解链接，但是题解过于简单，代码也没啥注释，也许是wtcl并没有看明白，又研究了好久才搞懂，并把代码加上了注释。 大体思路是这样的：首先，定义了一个结构体用来定义矩阵，其中包括矩阵的初始化（类似于Java的构造方法）；然后定义了两个函数（方法）：矩阵的乘法和矩阵幂；以上都是辅助性质的。以下为主要内容：为实现N个数不相同，规定A1<A2<……<AN，用trans函数（方法）实现，然后进行状态压缩用lim的二进制值来表示N个数每一位的取值（0 or 1），最后求出一个|s|的结果，再运用矩阵快速幂求出k个|s|的结果。
源码
#include
<iostream
>
#include
<cstring
>
using namespace std
;
const int mod
=1e9+7;
int n
,k
,len
,lim
,f
[55][130];
char s
[55];
typedef unsigned long long ull
;
struct matrix
{
ull a
[130][130];
matrix(int t
=0) {
memset(a
,0,sizeof(a
));
for(int i
=0;i
<=lim
;i
++) a
[i
][i
]=t
;
}
}A;
matrix
fun(matrix a
,matrix b
) {
matrix
c(0);
for(int i
=0;i
<=lim
;i
++)
for(int k
=0;k
<=i
;k
++) if(a
.a
[i
][k
])
for(int j
=0;j
<=k
;j
++)
((c
.a
[i
][j
]+=(ull
)a
.a
[i
][k
]*b
.a
[k
][j
]) >= mod
) ? c
.a
[i
][j
]%=mod
: 0;
for(int i
=0;i
<=lim
;i
++)
for(int j
=0;j
<=i
;j
++)
(c
.a
[i
][j
]>=mod
) && (c
.a
[i
][j
]%=mod
);
return c
;
}
matrix
power(matrix a
,int b
){
matrix
rs(1);
for(;b
;b
>>=1, a
=fun(a
,a
)) if(b
&1) rs
=fun(rs
,a
);
return rs
;
}
int
trans(int pre
,int now
,int pos
) {
int c
=0;
for(int j
=n
-1;j
;j
--)
if((pre
>>j
)&1) {
int a
=(now
>>j
)&1, b
=(now
>>(j
-1))&1;
if(a
>b
) return -1;
if(a
==b
) c
|=(1<<j
);
}
if(pre
&1) {
int tl
=0;
while(tl
<n
&& (pre
>>tl
)&1)
if((now
>>tl
)&1 && s
[pos
]=='0') return -1;
else ++tl
;
if((now
&1)==s
[pos
]-'0') c
|=1;
}
return c
;
}
int
main(int argc
, char
** argv
) {
cin
>>n
>>k
>>(s
+1);
len
=strlen(s
+1);
lim
=(1<<n
)-1;
for(int i
=0;i
<=lim
;i
++) {
memset(f
,0,sizeof(f
));
f
[0][i
]=1;
for(int j
=1;j
<=len
;++j
)
for(int pre
=0;pre
<=lim
;++pre
)
for(int now
=0;now
<=lim
;++now
) {
if(__builtin_popcount(now
)&1) continue;
int t
=trans(pre
,now
,j
);
if(~t
) f
[j
][t
]=(f
[j
][t
]+f
[j
-1][pre
])%mod
;
}
for(int j
=0;j
<=lim
;j
++)
A.a
[i
][j
]=f
[len
][j
];
}
matrix
B=power(A,k
);
int ans
=B.a
[lim
][0]%mod
;
cout
<<ans
;
return 0;
}
