被吊打场。
T1. 数
题目简介
题目名称：
题目来源：
评测链接 ：https://loj.ac/p/3600
评测链接 ：https://www.luogu.com.cn/problem/P8386
形式化题意：求长度为 的序列 ，且值域在 ，满足这个序列能被刚好划分成若干个子序列且每一个子序列的左右端点全职相等，即对于每一个子序列 ，有 。所有子序列刚好覆盖整个序列且不重叠。求序列个数，对 取模。
数据范围：
因为是计数，考虑 ，设 表示前 个数中，第 位填 种数合法，当前整个序列是否合法的方案个数。
如果当前位填 合法的话，我们往后再填一个 依然合法，所以可以考虑其中一个转移：
那显然，如果填剩下的 种数的话，显然就不合法了，但此时我们填入的这一个数同样会成为 的一部分，因为我们之后填的话也会使其合法，所以转移为：
如果当前不合法，我们填入 种数就会使其变成合法，所以可以直接转移：
如果填入其他的话，显然也和上述的情况一样，转移为：
最后统计答案为：
时间复杂度 ，考场上写假了，各种意义上的。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
x=0;
char ch=getchar(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=3e3+10;
const int Mod=1e9+7;
int N,M;
inline void add(int &x,int y){ x=x+y>=Mod?x+y-Mod:x+y; }
int Dp[MAXN][MAXN][2];
int main()
{
read(N,M);
Dp[0][0][1]=1;
for(int i=0;i<N;++i)
for(int j=0;j<=i;++j)
{
if(Dp[i][j][1])
{
add(Dp[i+1][j][1],(ll)Dp[i][j][1]*j%Mod);
add(Dp[i+1][j+1][0],(ll)Dp[i][j][1]*(M-j)%Mod);
}
if(Dp[i][j][0])
{
add(Dp[i+1][j][1],(ll)Dp[i][j][0]*j%Mod);
add(Dp[i+1][j][0],(ll)Dp[i][j][0]*(M-j)%Mod);
}
}
int ans=0;
for(int i=0;i<=N;++i) add(ans,Dp[N][i][1]);
write(ans);
return 0;
}
|
T2. 典
题目简介
题目名称：经典游戏
题目来源：
评测链接 ：https://loj.ac/p/3680
评测链接 ：https://www.luogu.com.cn/problem/P8994
形式化题意：在一棵有 个结点的树上进行 次游戏，结点 初始存在 个棋子，每次游戏流程如下：
- 钦定根为 ，并在 处新增一个棋子。
- 先手可以将根移动一个距离，即可以钦定一个新根 满足 ，其中 可以是 。
- 后手必须在一个结点新增一个棋子。
- 每个人执行一次操作，将某一颗棋子移向其子树的任意一个结点上，如果在叶子结点则无法移动，无法执行操作的一方为输。
求对于先手，有多少种钦定根的方案使得无论后手在哪里新增棋子，都必胜。请注意第一步中在 处放入的棋子并不因游戏结束而消失。
数据范围：
我们首先找出所有结点的 函数，也就是其子树的 ，容易发现就是最深子树深度，记录为 ，则整个游戏的胜负条件就是：
根据 定理，当 时，先手必败。
而当后手放置棋子的时候，如果存在一个 ，则会使 ，则先手败，所以先手必胜的条件就是 。
于是，我们得到了一个更为人性化的题面：
形式化题意
给定一棵树，结点分为黑白色（），点权为其深度与其子树内最大深度的差，每次询问翻转 的颜色，求有多少个结点作为根时满足黑色点异或和大于最大深度且与 结点距离不超过 。
考虑如果只询问 的话，可以选择用一个数据结构，类似 维护异或值查询，但要求维护一个连通块，所以还需要一些其他的方法。