《牛客IOI周赛17-普及组》

D：
手动打表
递推式
dp[i][j]表示以i结尾长度为j.
dp[i][j] = dp[i-1][j]+dp[i][j-1].
20分做法：直接N^2循环。
100分：
写出部分表
X/L:1 2 3 4 5 6 7
1 1 1 1 1 1 1 1
2 1 2 3 4 5 6 7
3 1 3 6 10 15 21 28
4 1 4 10 20 35 56
5 1 5 15 35 70 126
6 1 6 21 56 126 .
观察后从上往下看就是杨辉三角的那个图.
杨辉三角的值有C(i-1,j-1)的求法.
那么对于向下一个位置就是改变i,j不变.
那么就有下一个位置为C(i-1+1,j-1)的公式.
所以只需要列举下找下第一个值.
显然每一列就是从C(i+j-2,1)开始.
那么显然对于x,L,答案就是C(X-L+2,L-1)
Code:

LL f[N];
void init()
{
    f[0] = 1;for(int i=1;i<N;++i) f[i] = (f[i-1]*i)%Mod;
}
LL quick_mi(LL a,LL b)
{
    LL re = 1;
    while(b)
    {
        if(b&1) re = (re*a)%Mod;
        a = (a*a)%Mod;
        b >>= 1;
    }
    return re;
}
LL inv(LL x)
{
    return quick_mi(x,Mod-2)%Mod;
}
LL C(LL n,LL m)
{
    return f[n]*inv(f[m])%Mod*inv(f[n-m])%Mod;
}
void slove()
{
    init();
    int t;sd(t);
    while(t--)
    {
        int L,x;sdd(L,x);
        LL ans = C(L+x-2,L-1);
        plr(ans);
    }
}  
int main()
{
    slove();
    //system("pause");
    return 0;
}

B:
第几小很容易计算。
求第几小可以看成5进制数。
对于每个位置的数用10进制/和取模的思路去求数。
vector存每一位然后倒着输出.
Code:

LL f[105];
int a[5];
void init()
{
    a[0] = 1,a[1] = 2,a[2] = 3,a[3] = 5,a[4] = 9;
    f[0] = 1;for(int i=1;i<105;++i) f[i] = (f[i-1]*i)%Mod;
}
LL quick_mi(LL a,LL b)
{
    LL re = 1;
    while(b)
    {
        if(b&1) re = (re*a)%Mod;
        a = (a*a)%Mod;
        b >>= 1;
    }
    return re;
}
LL inv(LL x)
{
    return quick_mi(x,Mod-2)%Mod;
}
LL C(LL n,LL m)
{
    return f[n]*inv(f[m])%Mod*inv(f[n-m])%Mod;
}
void slove()
{
    init();
    int t;sd(t);
    while(t--)
    {
        int n,m;sdd(n,m);
        LL ma = C(n,m)%Mod;
        vector<int> G;
        while(ma)
        {
            ma--;//第一个是1即a[0],所以--,第6个是11。枚举几个数可以发现这样的--是必要的.
            G.pb(a[ma%5]);
            ma /= 5;
        }
        for(int i=G.size()-1;i>=0;--i) printf("%d",G[i]);
        printf("\n");
    }
}  
int main()
{
    slove();
   // system("pause");
    return 0;
}