1 Description
http://uoj.ac/problem/300
2 Solution
2.1
根据Lucas定理，(nm)mod2=1
(
n
m
)
mod
2
=
1
的充要条件是n and m=m
n
a
n
d
m
=
m
。
发现很好DP，设fi
f
i
表示以i
i
结尾的序列方案数，每次加入、转移即可。
2.2
考虑优化。
用fi,jfi,j表示所有结尾的数的前9
9
位以ii为子集、后9
9
位为jj的方案数。
每次加入一个数x
x
时，答案加上Δ=Δ=所有的fx的前9位,j
f
x
的
前
9
位
,
j
（满足x
x
的后99位为j
j
的子集）
然后将所有的fi,x的后9位fi,x的后9位加上Δ
Δ
即可（满足i
i
为xx的前9
9
位的子集）
记得最后的答案要减去长度为11的。
3 Code
3.1
/************************************************
* Au: Hany01
* Prob: [BZOJ4903][CTSC2017] 吉夫特
************************************************/
inline int ad(int x, int y) { if ((x += y) >= Mod) return x - Mod; return x; }
int main()
{
#ifdef hany01
File("bzoj4903");
#endif
static int n = read(), t, x, Ans, f[233335];
while (n --) {
x = read();
for (t = x; t 3.2
/************************************************
* Au: Hany01
* Prob: [BZOJ4903][CTSC2017] 吉夫特
m************************************************/
#include
using namespace std;
typedef long long LL;
typedef pair PII;
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i = i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia
template inline bool chkmax(T &a, T b) { return a inline bool chkmin(T &a, T b) { return b '9'; c_ = getchar()) if (c_ == '-') __ = -1;
for ( ; c_ >= '0' && c_ = Mod) return x - Mod; return x; }
int main()
{
#ifdef hany01
File("bzoj4903");
#endif
static int T, n = read(), x, Ans, f[513][513], res, x1, x2;
for (T = 1; T > 9, x2 = x & 511, res = 1;
register int i;
for (i = x2; i 