NowCoder--Protoss and Zerg

题目

链接：https://ac.nowcoder.com/acm/contest/303/H
来源：牛客网

1v1，是星际争霸(StarCraft)中最常见的竞技模式。

tokitsukaze进行了n场1v1。在每一场的1v1中，她都有星灵(Protoss)和异虫(Zerg)两个种族可以选择，分别有a个单位和b个单位。因为tokitsukaze不太擅长玩人类(Terran)，所以她肯定不会选择人类。

对于每一场1v1，玩家只能控制己方单位。也就是说，如果选择虫族，那么只能控制虫族单位，如果玩家选择星灵，那么只能控制星灵单位。

在n场1v1中，假设第i场，有ai个虫族单位，和bi个星灵单位。tokitsukaze可以在一场1v1中，任选一种种族进行游戏。如果选择了虫族，那么在这场游戏中，可以选择出兵1到ai个单位。那么同理，如果选择了星灵，那么在这场游戏中，可以选择出兵1到bi个单位。

假设所有异虫单位互不相同，所有星灵单位也互不相同，那么请问tokitsukaze打完这n场1v1，出兵的总方案数是多少，由于答案很大，所以输出答案mod 998244353 后的结果。

注意：若两个方案，有其中一个单位不同，即视为不相同。

输入描述

第一行包含一个T(T≤10)，表示T组数据。
对于每组数据：
第一行包含一个正整数n(1≤n≤100000)。
接下来n行，第i行包含两个整数ai,bi(1≤ai,bi≤10^9)，表示第i场1v1，有ai个异虫单位，和bi个星灵单位。

输出描述

对于每组数据，输出一行，表示mod 998244353后的答案。

示例1

输入

1
2
1 2
2 1

输出

16

说明

链接：https://ac.nowcoder.com/acm/contest/303/H
来源：牛客网

第一组样例：

对于第一场对局，tokitsukaze可以选择的虫族兵种有一个，并且将其编号为1，tokitsukaze可以选择的星灵兵种有两个，将其编号为1,2。所以tokitsukaze有四种可供选择的游戏方案：

1、选择虫族，并且派出虫族1号兵种。
2、选择星灵族，并且派出星灵族1号兵种。
3、选择星灵族，并且派出星灵族2号兵种。
4、选择星灵族，并且派出星灵族1，2号兵种。

对于第二场对局，tokitsukaze可以选择的虫族兵种有两个，并且将其编号为1,2，tokitsukaze可以选择的星灵兵种有一个，将其编号为1。所以tokitsukaze有四种可供选择的游戏方案：
1、选择虫族，并且派出虫族1号兵种。
2、选择虫族，并且派出虫族2号兵种。
3、选择虫族，并且派出虫族1，2号兵种。
4、选择星灵族，并且派出星灵族1号兵种。

两场对局是相互独立的事件，所以两轮游戏的出兵方案总数为4*4(mod 998244353)=16种。

解题思路：组合数+快速幂

AC-Code

import java.util.Scanner;

public class ProtossandZerg {
	static int mod=998244353;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while(t-->0)
		{
			int n = sc.nextInt();
			long ans = 1L;
			for(int i =0;i<n;i++)
			{
				int a = sc.nextInt();
				int b = sc.nextInt();
				long f1=quick_mod(2,a,mod)-1;
                long f2=quick_mod(2,b,mod)-1;
                ans = ans*(f1+f2)%mod;
			}
			System.out.println(ans);
		}
		sc.close();
	}
	public static long quick_mod(long a, long b, int mod) {
		long ans=1;
        while(b!=0){
            if((b&1)!=0){
                ans=ans*a%mod;
            }
            a=a*a%mod;
            b>>=1;
        }
        return ans;
	}
}