今天的题很有难度啊。然而我10：40才看题……

高一学堂

在美丽的中山纪念中学里面，有一座高一学堂。所谓山不在高，有仙则名；水不在深，有龙则灵。高一学堂，因为有了yxr，就成了现在这个样子 = =。

由于yxr 的语言太过雷人，每次他发微往往都会有一石激起千层浪的效果，具体就是所有关注他的人都会转发，同时@他，接着关注这些人的人也会转发，同时@他关注的人（注意转发内容本身会有@yxr），以此类推。这样导致每次yxr 发微博都会被@上兆次，而yxr 又特别喜欢发，sina 支持不了如此庞大的数据量，特出规定，每次转发时，@的人不能超过K 人，好友在转发时如果超过了，就把最早那人删掉。现在yxr 刚发了一条微博“求满分”，他想知道每个与他有联系的人分别会被@多少次。

输入格式：
输入第一行有三个整数,N,K，表示人数和K。
接下来N-1 行，每行有2 个整数a，b，表示a 和b 有关注关系。
输入给出一棵以1 号点为根的树，一号点代表yxr，对于任意一个点，他的儿子都关注他。

输出格式：
输出有N 行，每行有一个整数，这个人会被@多少次。

样例输入：
5 2
1 2
2 3
2 4
4 5

样例输出：
3
3
0
1
0

数据范围：
对于30%的数据，N≤100；
对于60%的数据，N≤2000，K≤100；
对于100%的数据，N≤100000, K≤N。

时间限制：
1S
空间限制：
256M

题解

求一个点向下至多k层的子树节点个数。

可以按深度排序后，主席树+dfs序解决，时空复杂度\(O(n \log n)\)

当然还有更简单的做法，用子树大小减去深度大于k的即可。而这个只需要在每个节点的时候把它的k+1级祖先的记录数组+1，向上更新记录数组即可。类似树上差分。

时间复杂度\(O(n)\)。

#include <bits/stdc++.h>
 
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 10;
const LL MOD = 1e9 + 7;
 
inline LL in()
{
    LL x = 0, flag = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * flag;
}
 
int n, m;
 
int head[MAXN], nume;
struct Adj { int nex, to; LL w; } adj[MAXN << 1];
void addedge(int from, int to, LL w)
{
    adj[++ nume] = (Adj) { head[from], to, w };
    head[from] = nume ;
}
 
int dep[MAXN], rec[MAXN];
LL tag[MAXN];
void mark(int u)
{
    if (dep[u] - m >= 1) tag[rec[dep[u] - m - 1]] --;
    else tag[0] --;
    tag[rec[dep[u] - 1]] ++;
}
void DFS(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    rec[dep[u]] = u;
    mark(u);
    for (int i = head[u]; i; i = adj[i].nex)
    {
        int v = adj[i].to;
        if (v == fa) continue;
        DFS(v, u);
    }
}
void DFS2(int u, int fa)
{
    for (int i = head[u]; i; i = adj[i].nex)
    {
        int v = adj[i].to;
        if (v == fa) continue;
        DFS2(v, u);
        tag[u] += tag[v];
    }
}
 
int main()
{
    n = in(), m = in();
    for (int i = 1; i < n; ++ i)
    {
        int u = in(), v = in();
        addedge(u, v, 0);
        addedge(v, u, 0);
    }
    DFS(1, 0);
    DFS2(1, 0);
    for (int i = 1; i <= n; ++ i) printf("%lld\n", tag[i]);
    return 0;
}

高二学堂

在美丽的中山纪念中学中，有座高二学堂，同样也是因为一个人，让它们变成了现在这个样子~那就是我们伟大的级主任。

因为他，我们又迎来了一个木有电影，只有对答案的段考日；又迎来了一个不是大礼拜，而是小礼拜的周末。因为是小礼拜，同学们都不回家，所以干脆就
回到宿舍去玩牌了。而由于三国杀太out 了，所以现在他们都玩四国杀。

四国杀（说白了就是扑克牌~）是Wayne 发明的，源于他对升级、斗地主、锄大地等等玩法都感到厌倦了。于是他提出了这个新的玩法：

Wayne 有一副加强版的扑克牌，强大到任意取一个自然数x，在牌堆里都恰有4 张数值为x 的牌。每次，Wayne 随机生成两个正整数n 和k，然后在牌堆里选取不超过k 张牌，使得牌面数字之和恰为n。已知Wayne 玩了若干盘，每盘都算出了对应的方案数，他想请你也算出各盘方案数，以验算他的结果是否正确。

结果可能比较大，你只需要求出方案数mod 1000000009 的值即可。

输入格式：
输入文件包含不超过10 组数据。
每行包含两个整数，表示上文中的n 和k。
输入数据以两个0 表示结束。

输出格式：
输出文件中，每组数据输出一行，为对应的方案数。

样例输入：
2 1
2 2
2 3
50 5
0 0

样例输出：
4
10
10
1823966

数据范围：
对于10%的数据，k=1；
对于20%的数据，n≤10，k≤4；
对于40%的数据，n≤1000；
对于60%的数据，n≤100000；
对于另外20%的数据，只有1 组数据；
对于100%的数据，n≤10^9，k≤10。

时间限制：
1S
空间限制：
256M

题解

这边的人怎么一拿到题就开始插多项式或者BM……

BM是可以过这道题的……留坑。

这题刘老爷切了。二到四名的代码一模一样。

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int SZ=500;
ll dp[12][10010];
int n, k;
const int MOD=1e9+9;
ll qp(ll a,ll b)
{
    ll x=1; a%=MOD;
    while(b)
    {
        if(b&1) x=x*a%MOD;
        a=a*a%MOD; b>>=1;
    }
    return x;
}
namespace linear_seq {
inline vector<int> BM(vector<int> x)
{
    vector<int> ls,cur;
    int pn=0,lf,ld;
    for(int i=0;i<int(x.size());++i)
    {
        ll t=-x[i]%MOD;
        for(int j=0;j<int(cur.size());++j)
            t=(t+x[i-j-1]*(ll)cur[j])%MOD;
        if(!t) continue;
        if(!cur.size())
        {cur.resize(i+1); lf=i; ld=t; continue;}
        ll k=-t*qp(ld,MOD-2)%MOD;
        vector<int> c(i-lf-1); c.pb(-k);
        for(int j=0;j<int(ls.size());++j) c.pb(ls[j]*k%MOD);
        if(c.size()<cur.size()) c.resize(cur.size());
        for(int j=0;j<int(cur.size());++j)
            c[j]=(c[j]+cur[j])%MOD;
        if(i-lf+(int)ls.size()>=(int)cur.size())
            ls=cur,lf=i,ld=t;
        cur=c;
    }
    vector<int>&o=cur;
    for(int i=0;i<int(o.size());++i)
        o[i]=(o[i]%MOD+MOD)%MOD;
    return o;
}
int N; ll a[SZ],h[SZ],t_[SZ],s[SZ],t[SZ];
inline void mull(ll*p,ll*q)
{
    for(int i=0;i<N+N;++i) t_[i]=0;
    for(int i=0;i<N;++i) if(p[i])
        for(int j=0;j<N;++j)
            t_[i+j]=(t_[i+j]+p[i]*q[j])%MOD;
    for(int i=N+N-1;i>=N;--i) if(t_[i])
        for(int j=N-1;~j;--j)
            t_[i-j-1]=(t_[i-j-1]+t_[i]*h[j])%MOD;
    for(int i=0;i<N;++i) p[i]=t_[i];
}
inline ll calc(ll K)
{
    for(int i=N;~i;--i) s[i]=t[i]=0;
    s[0]=1; if(N!=1) t[1]=1; else t[0]=h[0];
    for(;K;mull(t,t),K>>=1) if(K&1) mull(s,t); ll su=0;
    for(int i=0;i<N;++i) su=(su+s[i]*a[i])%MOD;
    return (su%MOD+MOD)%MOD;
}
inline int gao(vector<int> x,ll n)
{
    if(n<int(x.size())) return x[n];
    vector<int> v=BM(x); N=v.size(); if(!N) return 0;
    for(int i=0;i<N;++i) h[i]=v[i],a[i]=x[i];
    return calc(n);
}
}
int main() {
    dp[0][0] = 1;
    int N=300,K=10;
    for(int i = 1; i <= N; i++)
        for(int j = K; j >= 0; j--)
            for(int l = 0; l <= N; l++) {
                if(l >= 1 * i && j >= 1) dp[j][l]=(dp[j][l]+4ll*dp[j-1][l-1*i])%MOD;
                if(l >= 2 * i && j >= 2) dp[j][l]=(dp[j][l]+6ll*dp[j-2][l-2*i])%MOD;
                if(l >= 3 * i && j >= 3) dp[j][l]=(dp[j][l]+4ll*dp[j-3][l-3*i])%MOD;
                if(l >= 4 * i && j >= 4) dp[j][l]=(dp[j][l]+dp[j-4][l-4*i])%MOD;
            }
    for(int i = 1; i <= K; i++)
        for(int j = 0; j <= N; j++) dp[i][j]=(dp[i][j]+dp[i - 1][j])%MOD;
    //puts("233");
    while(scanf("%d%d",&n,&k)!=EOF){
        if(n==0&&k==0) break;
        vector<int> orz;orz.push_back(0);
        for(int i=1;i<=N;++i) orz.push_back(dp[k][i]);
        printf("%d\n",linear_seq::gao(orz,n));
    }
    return 0;
}

高三楼

参观完各种饭堂，学校还有什么著名的景点呢？当然是教室了，此时此刻我们来到了高三楼。你会发现高三楼门口会有以身份认证系统，这东西还有着一段疼人的历史。

每年的九月到来，高三的童鞋大多不习惯学校的作息时间，有人迟到的情况在所难免，2013 届的moreD 同志作为当年的纪检部部长，创造了一种十分厉害的身份认证系统。他会给每位童鞋的饭卡加上一个电子认证信息：一个n*n的矩阵，其中，每行每列都有两个特殊的点。moreD 同志设计的身份认证系统会把这些矩阵读进来，并且对此进行解析，由于每个同学都带有独特的矩阵，系统就可以在0.00001s 内认证出童鞋的身份。这样迟到的童鞋被登记的速度就会加快（刷卡嘛），大家上课的时间就不会耽误了，简单、快捷、方便统计。这一切都要感谢moreD 神牛。

但是，有一个IQ 超高的，经常迟到的童鞋，为了不扣分，他破解了moreD的身份认证系统，并对自己的认证信息做了更改。moreD 得知这个消息后立即对此等不良bug 进行改进。

他发现对于一些矩阵，只要把与之“重复”的矩阵取出，假身份认证信息的制造率会降低很多。

“重复”的定义为矩阵a，通过任意次行列变换，变成了矩阵b，矩阵a,b就视为重复。

例如：对于3*3 的矩阵，其中矩阵a 与矩阵b 被视为“重复”矩阵。

moreD 想知道对于一个n，可以有多少种不“重复”的矩阵，来填写不同学生的信息，moreD 忙着更改身份认证系统，这个艰巨的任务就交给你了,你只需要输出答案mod 100000007 的值就可以了，因为高一的学生可没有这么多。

输入格式：
第一行，一个整数t，表示数据组数。
接下来t 行，每行一个整数n，表示一组数据。

输出格式：
T 行，每行一个整数，表示方案数。由于答案可能很大，只需要输出方案数mod 100,000,007 的值就可以了。

样例输入：
3
2
3
4

样例输出：
1
1
2

数据范围：
对于10%的数据 N≤5；
对于50%的数据 N≤150；
对于100%的数据T≤5 N≤2,000。

时间限制：
1S
空间限制：
256M

题解

把行列建出二分图，那么二分图就是对应了很多的环。行列变换只是把环上节点的编号换了一下。

所以环的个数或大小不同，对应的矩阵就不同，所以要求的就是类似自然数拆分的方案数。

注意二分图只有偶环，并且这道题里面没有长度为2的环。

#include <cstdio>
 
const int N = 2e3 + 5, Mod = 1e8 + 7;
int T, dp[N], n;
 
int main() {
    dp[0] = 1;
    for (int i = 2; i <= 2000; ++i)
        for (int j = i; j <= 2000; ++j)
            dp[j] = 1LL * (dp[j] + dp[j - i]) % Mod;
    for (scanf("%d", &T); T--; scanf("%d", &n), printf("%d\n", dp[n]));
    return 0;
}

test20190802 夏令营NOIP训练18

原文：https://www.cnblogs.com/autoint/p/11287788.html