hdu 6265 Master of Phi(公式推导)
程序员文章站
2022-04-27 13:17:49
...
这题就是个公式化简,急中生智用搜索去优化时间复杂度
比赛时 我一看是数学题 因为自己数学功底差就交给队友去做,,最后他也没做出来
。。。打铁这个锅应该我背,没有去帮队友一起想 也许最后还能想到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;
}