CF2100分 D - Carry Bit
本人制作了一份CF板刷題單，結合了排序練習，單一重複練習，結構化練習等練習策略，避免了按演算法型別刷題導致做題沒方向，難度太大導致做題沒動力等問題，幫助ACMer高效提升演算法水平，未來將持續更新。此題單放在個人部落格中：http://reincarnate.cn/
tag:組合數學
problem types:計數題
D - Carry Bit
這題用DP複雜度太大，至少為
。
先思考什麼情況下我們會去進位，設
為
處的進位情況：
當
時，有
，
，
三種情況。
當
時，有
，
，
三種情況。
當
，
時，有
一種情況。
當
，
時，有
一種情況。
由此可見，當
時，可以排三種，當
時，可以排一種。設
為
的情況數（
），則在進位情況確定時，數目為
。
繼續考慮進位，由
可得有
個連續0序列，
個連續1序列。我們可以用隔板法把進位的數和不進位的數給分割成連續序列。
最後結果為
，累加起來即可。
當
時特判一下即可，因為0個進位切不開了。
#
include
<
bits
/
stdc
++
。
h
>
using
namespace
std
；
#define pb push_back
#define int long long
#define rep（i， a， n） for（int i = a； i <= n； i++）
#define per（i， a， n） for（int i = n； i >= a； i——）
typedef
pair
<
int
，
int
>
PII
；
const
int
N
=
1e6
+
10
；
const
int
mod
=
1e9
+
7
；
int
fact
［
N
］，
infact
［
N
］；
int
qmi
（
int
a
，
int
k
）{
if
（
k
<
0
）
return
0
；
int
res
=
1
；
while
（
k
）{
if
（
k
&
1
）
res
=
res
*
a
%
mod
；
a
=
a
*
a
%
mod
；
k
>>=
1
；
}
return
res
；
}
void
init
（）{
fact
［
0
］
=
infact
［
0
］
=
1
；
for
（
int
i
=
1
；
i
<
N
；
i
++
）{
fact
［
i
］
=
fact
［
i
-
1
］
*
i
%
mod
；
infact
［
i
］
=
infact
［
i
-
1
］
*
qmi
（
i
，
mod
-
2
）
%
mod
；
}
}
int
cal
（
int
a
，
int
b
）{
if
（
a
<
b
||
b
<
0
）
return
0
；
return
fact
［
a
］
*
infact
［
b
］
%
mod
*
infact
［
a
-
b
］
%
mod
；
}
void
solve
（）{
//try it again。
int
n
，
k
；
cin
>>
n
>>
k
；
if
（
k
==
0
）{
cout
<<
qmi
（
3
，
n
）
<<
‘\n’
；
return
；
}
int
ans
=
0
；
rep
（
q
，
0
，
n
）{
int
res
=
qmi
（
3
，
n
-
q
）
%
mod
*
cal
（
k
-
1
，
（
q
+
1
）
/
2
-
1
）
%
mod
*
cal
（
n
-
k
，
（
q
+
2
）
/
2
-
1
）
%
mod
；
ans
=
（
res
+
ans
）
%
mod
；
}
cout
<<
ans
<<
‘\n’
；
}
signed
main
（）{
ios
：：
sync_with_stdio
（
false
）；
cin
。
tie
（
0
）；
init
（）；
solve
（）；
}
