2019.10.19考试解题报告
总结
期望得分：(60 + 30 + 0)
实际得分：(30 + 40 + 0)
又是没有相信自己的暴力，最后被自己的优化程序搞死的一天。
(T1)写了(60)暴力，本来想要优化一下下，结果想写(O(n))的判断，却变成了(O(无穷))的超时。。（瞎搞失败）
(T2)正解肯定是线段树，但是不会写(3)操作的东西，于是看到有(k=1)和(k=2)的部分分，就去瞎搞，以为能得(30)，没想到教师机跑的还挺快（可能是关了360的原因），拿了(40)（瞎搞成功）
(T3)树形(DP)，想写又不会写
思路
T1
推式子
T2
考虑用线段树来完成此题。对于每个节点我们维护一个(f[i](i in [1, 10]))，表示这个节点所对应区间选(i)个球的答案。
考虑如何合并两个节点(lc,rc)。(f[i] = sum（lc.f[j] * rc.f[i-j]) j in [0,i])
对于取相反数操作，只有当(i)是奇数时，才会改变(f[i])的符号。
对于一段区间(+c)的操作，设这段区间的长度为(len)，则新的(f[i])为(sum (f(j) * c^{i-j} * C(len - j, i - j)) jin [0,i]) 其中(C(n,m))表示(n)个数中选(m)个的组合数
这样我们就可以套用区间修改区间询问的线段树来解决这道题了，时间复杂度为(O(c^2nlogn))
T3
做法（(from solution)）
考虑用树形(dp)来解决这道问题。
设(f[i][j])表示在(i)的子树中(i)所在的连通块大小为(j)，且其他连通块大小均符合要求的删边方案数
对于每个点(i)我们一棵一棵地将其子树加进来，设新加入子树的根为(u)
若删除(u)与(i)之间的边，则用$f[i][j] * sum (f[u][s]) s in [k,n] (去更新)f[i][j](
若不删)u(与)i(之间的边，则枚举)u(所在连通块的大小)s(，并更新)f[i][j+s]$
时间复杂度 (O(n^3)) ？
考虑一个优化:每次新加一颗子树时，(j)只需枚举到前面已经加进来的子树大小之和，(s)也只需枚举到新子树的大小
这只是一个常数优化？其实每个点对相当于只在(lca)处被算了一次
故优化后的时间复杂度是(O(n^2))的,本题得以解决。
代码
T1
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int N=200010;
int n,m;
long long a[N],GCD=0;
set<long long> Set;
long long gcd(long long a,long long b)
{
return b?gcd(b,a%b):a;
}
long long qabs(long long x){return x<0?-x:x;}
int main()
{
freopen("ninja.in","r",stdin);
freopen("ninja.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(int i=2;i<=n;i++)
GCD=gcd(2LL*qabs(a[i]-a[1]),GCD);
if(GCD==0)GCD=1000000000LL*1000000000LL;
Set.insert(0LL);
for(int i=1;i<=n;i++)
Set.insert(((2*a[i])%GCD+GCD)%GCD);
while(m--)
{
long long q;
scanf("%lld",&q);
if(Set.find((q%GCD+GCD)%GCD)!=Set.end())
puts("Yes");
else
puts("No");
}
fclose(stdin);
fclose(stdout);
return 0;
}
T2
#include <cstdio>
#include <cstdlib>
#define MOD 1000000007
#define N 100005
typedef long long LL;
using namespace std;
struct Node {
LL f[11];
}node[N * 4];
LL a[N], lazy1[N * 4];
bool lazy2[N * 4];
LL C[N][11];
Node merge(Node lc, Node rc) {
Node o;
o.f[0] = 1;
for (int i = 1; i <= 10; i++) {
o.f[i] = 0;
for (int j = 0; j <= i; j++)
o.f[i] = (o.f[i] + lc.f[j] * rc.f[i - j] % MOD) % MOD;
}
return o;
}
void build(int o, int l, int r) {
if (l == r) {
for (int i = 0; i <= 10; i++) node[o].f[i] = 0;
node[o].f[0] = 1;
node[o].f[1] = (a[l] % MOD + MOD) % MOD;
return ;
}
int mid = (l + r) >> 1;
build(o * 2, l, mid);
build(o * 2 + 1, mid + 1, r);
node[o] = merge(node[o * 2], node[o * 2 + 1]);
return ;
}
void update1(int o, int l, int r, int c) {
int len = r - l + 1;
LL ff[11];
for (int i = 0; i <= 10; i++) ff[i] = node[o].f[i];
for (int i = 1; i <= 10; i++) {
node[o].f[i] = 0;
LL t = 1;
for (int j = 0; j <= i; j++) {
LL tmp = ff[i - j] * C[len - (i - j)][j] % MOD * t % MOD;
node[o].f[i] = (node[o].f[i] + tmp) % MOD;
t = t * c % MOD;
}
}
return ;
}
void push_down(int o, int l, int r) {
int mid = (l + r) >> 1;
if (lazy1[o]) {
if (lazy2[o * 2])
lazy1[o * 2] = (lazy1[o * 2] + MOD - lazy1[o]) % MOD;
else
lazy1[o * 2] = (lazy1[o * 2] + lazy1[o]) % MOD;
if (lazy2[o * 2 + 1])
lazy1[o * 2 + 1] = (lazy1[o * 2 + 1] + MOD - lazy1[o]) % MOD;
else
lazy1[o * 2 + 1] = (lazy1[o * 2 + 1] + lazy1[o]) % MOD;
update1(o * 2, l, mid, lazy1[o]);
update1(o * 2 + 1, mid + 1, r, lazy1[o]);
lazy1[o] = 0;
}
if (lazy2[o]) {
lazy2[o * 2] ^= 1;
lazy2[o * 2 + 1] ^= 1;
for (int j = 1; j <= 10; j += 2) {
node[o * 2].f[j] = MOD - node[o * 2].f[j];
node[o * 2 + 1].f[j] = MOD - node[o * 2 + 1].f[j];
}
lazy2[o] = 0;
}
}
void modify1(int o, int l, int r, int ll, int rr, int c) {
if (ll <= l && rr >= r) {
if (lazy2[o]) lazy1[o] = (lazy1[o] + MOD - c) % MOD;
else lazy1[o] = (lazy1[o] + c) % MOD;
update1(o, l, r, c);
return ;
}
int mid = (l + r) >> 1;
push_down(o, l, r);
if (ll <= mid) modify1(o * 2, l, mid, ll, rr, c);
if (rr > mid) modify1(o * 2 + 1, mid + 1, r, ll, rr, c);
node[o] = merge(node[o * 2], node[o * 2 + 1]);
return ;
}
void modify2(int o, int l, int r, int ll, int rr) {
if (ll <= l && rr >= r) {
for (int i = 1; i <= 10; i += 2) node[o].f[i] = MOD - node[o].f[i];
lazy2[o] ^= 1;
return ;
}
int mid = (l + r) >> 1;
push_down(o, l, r);
if (ll <= mid) modify2(o * 2, l, mid, ll, rr);
if (rr > mid) modify2(o * 2 + 1, mid + 1, r, ll, rr);
node[o] = merge(node[o * 2], node[o * 2 + 1]);
return ;
}
Node query(int o, int l, int r, int ll, int rr) {
if (ll <= l && rr >= r)
return node[o];
int mid = (l + r) >> 1;
push_down(o, l, r);
if (rr <= mid) return query(o * 2, l, mid, ll, rr);
if (ll > mid) return query(o * 2 + 1, mid + 1, r, ll, rr);
Node lc = query(o * 2, l, mid, ll, rr);
Node rc = query(o * 2 + 1, mid + 1, r, ll, rr);
return merge(lc, rc);
}
int main(int argc, char ** argv) {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
int n, m;
scanf("%d %d", &n, &m);
C[0][0] = 1;
for (int i = 1; i <= n; i++) {
C[i][0] = 1;
for (int j = 1; j <= 10; j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, 1, n);
for (int i = 1; i <= m; i++) {
int l, r, opt;
scanf("%d%d%d",&opt, &l, &r);
if (opt == 1) {
int c;
scanf("%d", &c);
c = (c % MOD + MOD) % MOD;
modify1(1, 1, n, l, r, c);
}
else if (opt == 2) {
modify2(1, 1, n, l, r);
}
else {
int k;
scanf("%d", &k);
Node o = query(1, 1, n, l, r);
printf("%d
", o.f[k] % MOD);
}
}
return 0;
}
T3
#include<cstdio>
#include<cstdlib>
#define N 5555
#define M 786433
using namespace std;
typedef long long LL;
struct edge
{
int t,n;
}e[N*2];
LL h[N],size[N],f[N][N],g[N],cnt[N];
int n,K,tote;
void add(int u,int v)
{
e[++tote].t=v;
e[tote].n=h[u];
h[u]=tote;
return ;
}
void dfs(int u,int fa)
{
size[u]++; f[u][1]=1;
for (int i=h[u];i;i=e[i].n)
{
int v=e[i].t;
if (v==fa) continue;
dfs(v,u);
for (int j=1;j<=size[u]+size[v];j++) g[j]=0;
for (int j=1;j<=size[u];j++) g[j]=cnt[v]*f[u][j]%M;
for (int j=1;j<=size[u];j++)
for (int k=1;k<=size[v];k++) g[j+k]=(g[j+k]+f[u][j]*f[v][k]%M)%M;
for (int j=1;j<=size[u]+size[v];j++) f[u][j]=g[j];
size[u]+=size[v];
}
for (int i=K;i<=size[u];i++) cnt[u]=(cnt[u]+f[u][i])%M;
return ;
}
int main()
{
freopen("cut.in","r",stdin);
freopen("cut.out","w",stdout);
scanf("%d %d",&n,&K);
for (int i=1;i<n;i++)
{
int u,v;
scanf("%d %d",&u,&v);
add(u,v); add(v,u);
}
dfs(1,1);
printf("%d
",cnt[1]);
fclose(stdin);
fclose(stdout);
return 0;
}