这段代码如何运行得这么快i/o？

Question

我无法理解此函数如何在 C++ 中产生更快的 i/o。请帮帮我！！

#include <iostream>
#include <cstring>

#define FOR(A,B,C) for(int A=B;A<C;A++)
#define EFOR(A,B,C) for(int A=B;A<=C;A++)
#define RFOR(A,B,C) for(int A=B;A>=C;A--)

using namespace std;

inline void Input(int &N)
{
int ch;
N=0;

while((ch<'0'||ch>'9')&&ch!='-'&&ch!=EOF)
    ch=getchar();

do
    N=(N<<3)+(N<<1)+(ch-'0');
while( (ch=getchar())>='0' && ch<='9');

return;
}

int main()
{
unsigned int fn[100005],gn[100005];
fn[0]=1,gn[0]=1,fn[1]=1,gn[1]=0;
int MOD=100000;

EFOR(fill,2,100001){
    fn[fill]=(fn[fill-1]+fn[fill-2]+2*gn[fill-1])%MOD;
    gn[fill]=(fn[fill-2]+gn[fill-1])%MOD;
}

int T;
Input(T);
while(T--){
    int N;
    Input(N);
    printf("%u\n",fn[N]%10000);
}

return 0;
}

这段没有内联函数的代码得到的是 TLE，但是有了它，它得到的是 AC 如果我只使用 cin 或 scanf 来获取输入，我会得到一个 TLE

Answer 1

假设第一行是：int ch = getchar();

while((ch<'0'||ch>'9')&&ch!='-'&&ch!=EOF)
    ch=getchar();

这些行跳过所有不是数字的字符。虽然你应该正确使用-。

(N<<3)+(N<<1) 等同于 N * 8 + N * 2 或 N * 10.

(ch-'0') 会将字符 ch 从可打印字符转换为数字。

添加到先前的结果10 * N会将新读取的字符附加到 N.

它可能比使用 cin 或 printf("%d", &N) 的格式化输入更快，原因如下：

读取原始输入而不是格式化。
使用移位的乘法

Answer 2

代码跳过所有非数字字符，然后读取所有数字并将它们累加成一个数字。

N=(N<<3)+(N<<1)+(ch-'0');

是

的优化

N = N*10+(ch-'0')

这在大多数编译器/平台上是完全没有必要的。

错误和可移植性问题：

ch 未初始化
输入“-”以 N=0 结束输入。这可能不是故意的

这段代码如何运行得这么快i/o？

How does this piece of code function as fast i/o?

c++

io