注意到题目里得分的构造方式，我们可以发现只要答案给错了得分一定比较少，因此我们必须每次给出正确的答案。 然后，我们观察得分的形式：由于 2 n 2^n 2n的乘数因子是固定的，因此我们可以把它提出来，问题等价于只要求方案数即可。由一些组合数最基本的定义得到第 i i i个路口的答案一定是 C n i C^i_n Cni。最终答案应该是 ∑ i = 0 n C n i \sum\limits_{i=0}^{n}C^i_n i=0∑nCni。然后把它摆在杨辉三角形里相当于求杨辉三角形整行的和，因此我们由组合恒等式 ∑ i = 0 n C n i = 2 n \sum\limits_{i=0}^{n}C^i_n=2^{n} i=0∑nCni=2n即可将问题转化为求 2 2 n % 998244353 = 4 n % 998244353 2^{2n}\%998244353=4^{n}\%998244353 22n%998244353=4n%998244353的结果。 注意到 998244353 998244353 998244353是个质数，我们由费马小定理知道 4 998244352 % 998244353 = 1 4^{998244352}\%998244353=1 4998244352%998244353=1，所以我们只需要将 n n n对 998244353 998244353 998244353取模然后快速幂计算结果即可。
然而考虑到这个 n n n实在是太大了，所以我们必须要采用如下的方式来解决： 输入文件总计 10 M B 10MB 10MB左右，换算之： 10 ∗ 1024 ∗ 1024 ≈ 1 0 7 10*1024*1024\approx10^7 10∗1024∗1024≈107，大约是 1 0 7 10^7 107个数字。我们有如下的解决方案：
1.对于 C + + C++ C++选手你可以考虑在快速读入时做这样的改变。 这是原本的快速读入：
#define Fermat 998244352 #define mod 998244353 inline int read() { int n=0,k=1; char c=getchar(); while(c>'9'||c<'0') c=getchar(); while(c>='0'&&c<='9') n=(n<<1)+(n<<3)+(c^48),c=getchar(); return n; }如果我们加费马小定理优先取模，可以这么做：
#define Fermat 998244352 #define mod 998244353 inline int read() { int n=0,k=1; char c=getchar(); while(c>'9'||c<'0') c=getchar(); while(c>='0'&&c<='9') n=(n<<1)+(n<<3)+(c^48),n%=Fermat,c=getchar(); return n; }主程序中调用
int n=read();这样可以直接得到对 998244352 998244352 998244352取模过后的 n n n 当然你想直接字符串读进来写个高精对单精取模也是可以的。
2.对于Pascal选手，你没有可以这么做的快速读入，但你仍然可以这么做
while not eof do begin read(c); n:=n*10+odd(c)-48; n:=n mod 998244352; end;（我没有卡语言，我很良心）
3.对于Python,Java等语言的选手：你们可以使用BigInt，当然只要你不怕TLE
另外，如果你们注意到Pascal，Python和Java（如果有）等语言的程序始终因为TLE而无法通过，你可以将运行时间限制调整到 2 s 2s 2s
