本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。

NC14597-可编程拖拉机比赛

题目链接

https://ac.nowcoder.com/acm/problem/14597

题目描述

“这个比赛，归根结底就是控制一个虚拟的小拖拉机跑完整个赛道。一般一场比赛会有 9 个到 13 个赛道，最后看能跑完多少个赛道。”通常在一场可编程拖拉机比赛中，分别会有实际参赛队伍数 10%、20%、30% 向下取整的队伍获得金、银、铜牌，其余队伍获得荣誉提名，俗称“铁牌”。但是主办方往往会多准备一些奖牌，那么在发奖牌的时候会按照比例向上取整发出的奖牌以减少浪费，就会有一些原本获得银牌的队伍获得了金牌。现在给出一个赛区的规模，也就是这个赛区的实际参赛队伍数，小 Q 同学想知道有多少队伍的奖牌会由银变金、由铜变银、由铁变铜。输入只有一行，包含一个整数 n (10 <= n <= 1000)，表示实际参赛队伍数。输出一行，包含三个由空格分隔的整数，分别表示奖牌会由银变金、由铜变银、由铁变铜的队伍数。

测试样例

输入

115

输出

1 1 2

解题思路

我们首先要知道，当一个金牌人数增加时，那么根据堆积的效应，银牌和铜牌的人数也会加1，当银牌人数增加时，金牌人数不受影响，只是铜牌受影响，而铜牌人数改变不影响任何人数。当前10%不是刚好整数，即n%10不是0时，说明规矩改变后，金牌人数会加1，且最多只会有增多一个人，银牌就是前20%有问题，所以应该是模5不是0时，说明规矩改变后，银牌人数会加1且最多只会增加一个人，同理铜牌是n%（10/3）的时候，会增加一人。

解题代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a = 0, b = 0, c = 0;
    int n;
    cin >> n;
    //当乘10%即模10的时候不是整数，那么所有牌的人数都++
    if (n % 10 != 0)
    {
        a++;
        b++;
        c++;
    }
    //当乘20%即模10/2=5的时候不是整数，那么银、铜人数都++
    if (2 * n % 10 != 0)
    {
        b++;
        c++;
    }
    //当乘30%即模10/3的时候不是整数，那么铜牌人数++
    if (3 * n % 10 != 0)
    {
        c++;
    }
    cout << a << " " << b << " " << c << endl;
    system("pause");
    return 0;
}

NC14599-子序列

题目链接

https://ac.nowcoder.com/acm/problem/14599

题目描述

定一个小写字母字符串T ，求有多少长度为m的小写字母字符串S满足，T是S的一个子序列(不需要连续)。第一行一个字符串T，第二行一个正整数m，输出答案对109+7取模的值。

测试样例

输入

a
2

输出

51

说明

长度为2的里面有a的串有51种

解题思路

逆元+组合数题，自己的没过，但是思路正确，直接看注释吧

解题代码

#include <bits/stdc++.h>
const int maxx = 1e5 + 15;
#define ll long long
//取模提前声明，好习惯
const ll mod = 1e9 + 7;
using namespace std;
string s;

//快速幂取模板子，注意第一个放C底下的数，第二个放C上面的数
ll qmi(int a, int k)
{
    a %= mod;
    //ans是结果值
    int ans = 1;
    //采用的是二进制的计算方法
    while (k)
    {
        //这里k在机器中是二进制表示，与1相与，只有k的最后一位是1才能使得if条件成立
        if (k & 1)
            //此时ans就乘以一个基数a
            ans = ans * a % mod;
        //每一次a都要扩大一倍表示下一位的位权
        a = a * a % mod;
        //k右移一位取最低位
        k >>= 1;
    }
    return ans;
}

//逆元取模的组合数板子
ll C(ll k, ll n)
{
    int num = 1;
    for (int i = 1, j = k; i <= n; i++, j--)
    //一共分子和分母只需要计算n次
    {
        //这里用来计算Ckn
        num = num * j % mod;
        //这里是求n!的逆元，以便能够取模
        num = num * qmi(i, mod - 2) % mod;
    }
    return num;
}

int main()
{
    ll i, m, n;
    cin >> s;
    cin >> m;
    n = s.length();
    //多余出来的位数
    ll ans = 0;
    //i至少有n个，同时还忽悠m-n个多于的位，这里就是在模拟这些位放在哪里
    //如果是插在子序列的左边或中间，那么就只能有25个选择
    //否则子序列右边就是26个选择
    //枚举子序列左边的位数（包括子序列自身）
    //那么i-n是插到子序列左边的多于位数的个数（有25个选择的位数个数）
    //m-i是放到子序列右边即后面的位数个数（有26个选择的位数的个数）
    //实际上模拟取模的二项式定理
    for (i = n; i <= m; i++)
    {
        //注意当长度为4，那么实际上C的底数是3即为n-1,上面就是
        ans += C(n - 1, i - 1) * qmi(25, i - n) % mod * qmi(26, m - i) % mod;
        ans %= mod;
    }
    cout << ans << endl;
    system("pause");
    return 0;
}