第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛 H 数羊

思考

看了半天的题目发现不知道怎么化简或者说有什么规律，于是抱着试试看看的思想，把2<= n <= 6,0<= m <= 2这部分的结果打印出来看能不能找到规律，结果还真有规律，先上图

通过上面的表格不难发现，除了A(1,0)以外

• 当n >= 2,m = 0时，A(n,m) = n + 1
• 当n >= 1,m = 1时，A(n,m) = 2 * n
• 当n >= 1,m = 2时，A(n,m) = 2ⁿ

有了上面的规律就好办了，A(1,0)特判，m = 0或者m = 1直接使用公式；m = 2这种情况使用快速幂，不然多半会超时
代码如下：

#include<iostream>
#include<cstdio>
typedef long long ll;
ll mod = 998244353;
ll quick(ll k)
{
    ll ret = 2;
    ll now = 1;
    while(k)
    {
        if(k % 2 == 1)
        {
            now = ret * now % mod;
        }
        ret = ret * ret % mod;
        k >>= 1;
    }
    return now;
}
int main()
{
    int T;
    scanf("%d",&T); 
    ll n,m;
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        if(n == 1)
        {
            printf("2\n");
        }
        else if(m == 0)
        {
            printf("%lld\n",(n + 2) % mod);
        }
        else if(m == 1)
        {
            printf("%lld\n",2 * n % mod);
        }
        else
        {
            printf("%lld\n",quick(n));
        }
    } 
    return 0;
}

QAQ快速幂太久没打都快忘了