B:2018-div-matrix

题意：

Bobo 想统计满足下面条件的矩阵 A 的数量。

1. 矩阵 A 有 n 行 m 列，每个元素都是正整数。第 i 行第 j 列的元素用Aij 表示。

2. A1,1 = 2018

3. 对于所有的2<=i<=n,1<=j<=m,Ai,j是Ai-1,j的约数

4. 对于所有的1<=i<=n,2<=j<=m,Ai,j是Ai,j-1的约数

因为满足条件的矩阵 A 数量很多，Bobo 只想统计满足条件的矩阵数量除以(10^9+7)的余数

题解：

听说这是catalan数，百度一下这是个排列组合的数，反正打表就出来了

结果是(C(n+m,n)-1)×(C(n+m,m)-1)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9+7;
const int maxx = 4010;
ll pow_mod(ll a,ll b)
{
    ll ans = 1;
    while(b){
        if(b&1)
           ans = ans*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return ans;
}
ll a[maxx],b[maxx];
void solve()
{
    a[0] = 1;
    for(ll i=1;i<=4005;i++){
        a[i] = (a[i-1]*i)%mod;
        b[i] = pow_mod(a[i],mod-2);
    }
}
ll C(ll x,ll y)
{
    return a[x]*b[y]%mod*b[x-y]%mod;
}
int main()
{
    solve();
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        printf("%lld\n",(C(n+m,n)-1)*(C(n+m,m)-1)%mod );
    }
    return 0;
}

J：买一送一

题意：

给出一个有向图，可以说是一棵树，每个节点相当于一个商店，每个商店有一个商品的类型，Bobo 从商店 1 出发前往商店 i。他要在两个不同的商店购买商品（包括商店 1 和 i）。设他先购买的商品类型是 x，后购买的商品类型是 y，他用 fi表示不同的有序对<x,y> 的数量。问你f2，f3....fn

题解:

深搜，当前节点的fi = 前一个节点的fi + 以当前节点为第二个商品的有序对的个数 - 之前以当前节点为第二个商品的有序对的个数

#include <bits/stdc++.h>
using namespace std;
#define  ll unsigned long long

const int maxx = 100005;
vector<int> v[maxx];
int b[maxx],sign[maxx];
ll f[maxx],pre[maxx];
int cnt = 0;
void dfs(int x)
{
    for(int i=0;i<v[x].size();i++)
    {
        int k = v[x][i];
        f[k] = f[x] + cnt - pre[b[k]];//gengxin
        int now = pre[b[k]];
        pre[b[k]] = cnt;
        int flag = 0;
        if(!sign[b[k]]){
            cnt++,flag = 1;
        }
        sign[b[k]]++;

        dfs(k);

        pre[b[k]] = now;
        if(flag)
            cnt--;
        sign[b[k]]--;
    }
}
int main()
{
    int n,x;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++) {
            v[i].clear();
            f[i] = 0,pre[i] = 0,sign[i] = 0;
        }
        for(int i=2;i<=n;i++){
            scanf("%d",&x);
            v[x].push_back(i);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
        }
        cnt = 1,sign[b[1]] = 1;
        dfs(1);
        for(int i=2;i<=n;i++){
            printf("%lld\n",f[i]);
        }
    }
    return 0;
}

K：Use FFT

题意：

给出俩个多项式P(x)=a0 + a1x + … + anx^n 和 Q(x)=b0 + b1x + … + bmx^m.

P(x)⋅Q(x)=c0 + c1x + … + cn+mx^(n+m),输出(cL + c(L+1) + … + cR) modulo(10^9 + 7)for given L and R.

题解：

先求出bi的前缀和，循环一遍min(r,n),每次前缀和--

#include <bits/stdc++.h>
using namespace std;
#define  ll unsigned long long
const int maxx = 1000005;
ll a[maxx],b[maxx],pre[maxx*2];
const ll mod = 1e9+7;
int main()
{
    ll n,m,l,r;
    while(~scanf("%lld%lld%lld%lld",&n,&m,&l,&r))
    {
        for(int i=0;i<=n;i++)
            scanf("%lld",&a[i]);
        for(int i=0;i<=m;i++){
            scanf("%lld",&b[i]);
            if(i == 0)
                pre[i] = b[i];
            else{
                pre[i] = pre[i-1] + b[i];
            }
            pre[i] %= mod;
        }
        ll ans = 0;
        for(int i=m+1;i<=r;i++)
            pre[i] = pre[i-1];

        for(int i=0;i<=min(r,n);i++){
            if(l-i-1 >=0)
                ans += a[i]*((pre[r-i]-pre[l-i-1]+mod)%mod);
            else
                ans += a[i]*pre[r-i];
            //cout<<ans<<endl;
            ans %= mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}