欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu 6265 Master of Phi(公式推导)

程序员文章站 2022-04-27 13:17:49
...

hdu 6265 Master of Phi(公式推导)
hdu 6265 Master of Phi(公式推导)

这题就是个公式化简,急中生智用搜索去优化时间复杂度
比赛时 我一看是数学题 因为自己数学功底差就交给队友去做,,最后他也没做出来
。。。打铁这个锅应该我背,没有去帮队友一起想 也许最后还能想到dfs。。。
只顾着自己想题 个人意识太强,没有团体意识。。。毫无大局观念,特在此反思自己的过错 希望以后能够将自己的眼光格局放大一点

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <bits/stdc++.h>
typedef long long LL;
const int N =1e6+100;
using namespace std;
typedef long long LL;
const LL mod =  998244353;
LL a[N], b[N], c[N], d[N];
LL quick1(LL x,LL n)
{
    LL r=1;
    while(n)
    {
        if(n&1)r=r*x%mod;
        n>>=1;
        x=x*x%mod;
    }
    return r%mod;
}
LL sum;
LL n;
void dfs(int p,LL s1)
{
    if(p<=n+1)
    {
        if(p==n+1)
        {
            sum=(sum+s1)%mod;
            return ;
        }
        dfs(p+1,s1);
        s1=s1*(a[p]-1)%mod;
        s1=s1*d[p]%mod;
        s1=s1*b[p]%mod;
        dfs(p+1,s1);
    }
    return ;
}


int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld", &n);
        LL s=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld %lld", &a[i], &b[i]);
//            if(b[i]==1)c[i]=1;
//            else c[i]=(a[i]*(quick1(a[i],b[i])-1+mod)%mod)*quick1(a[i]-1,mod-2)%mod;
            d[i]=quick1(a[i],mod-2);
            s=s*quick1(a[i],b[i])%mod;
        }
        //cout<<s<<endl;
        sum=0;
        dfs(1,s);
        printf("%lld\n",sum);
    }
    return 0;
}