下面两份代码,第一份使用 getchar() 读入,第二份使用 scanf() 读入一整行字符串,在本地运行的结果是相同的,但交上去第一份会全 WA,测试点信息表明是在第一行第一列输出了 0。
有没有人知道这是为什么?
第一份代码:
#include<bits/stdc++.h>
#define ll long long
#define fswap(x,y) x ^= y, y ^= x, x ^= y
using namespace std;
const ll P = 998244353,G = 3,Gi = 332748118;
int n,m,lim = 1,len,r[2100005];
ll a[2100005],b[2100005];
int read()
{
int x = 0,f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')x = (x << 1) + (x << 3) + ch - 48,ch = getchar();
return x * f;
}
ll ksm(ll x,ll y)
{
ll ret = 1;
while(y)
{
if(y & 1)
ret = ret * x % P;
x = x * x % P,y >>= 1;
}
return ret;
}
void NTT(ll *d,int tag)
{
for(int i = 0;i < lim;i++)
if(i < r[i])
fswap(d[i],d[r[i]]);
for(int i = 1;i < lim;i <<= 1)
{
ll wn = ksm(tag == 1 ? G : Gi,(P - 1) / (i << 1));
for(int j = 0;j < lim;j += (i << 1))
{
ll w = 1;
for(int k = 0;k < i;k++,w = w * wn % P)
{
int tx = d[j + k],ty = w * d[i + j + k] % P;
d[j + k] = (tx + ty) % P,d[i + j + k] = (tx - ty + P) % P;
}
}
}
}
int main()
{
char ch = getchar();
while(ch >= '0' && ch <= '9')
a[n++] = ch - 48,ch = getchar();
n--,ch = getchar();
while(ch >= '0' && ch <= '9')
b[m++] = ch - 48,ch = getchar();
m--;
for(int i = 0;i < n - i;i++)
fswap(a[i],a[n - i]);
for(int i = 0;i < m - i;i++)
fswap(b[i],b[m - i]);
while(lim <= n + m)
lim <<= 1,len++;
for(int i = 0;i < lim;i++)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (len - 1));
NTT(a,1),NTT(b,1);
for(int i = 0;i <= lim;i++)
a[i] = a[i] * b[i] % P;
NTT(a,-1);
ll inv = ksm(lim,P - 2);
for(int i = 0;i <= n + m;i++)
a[i] = a[i] * inv % P;
for(int i = 0;i <= n + m;i++)
a[i + 1] += a[i] / 10,a[i] %= 10;
if(a[n + m + 1])
printf("%lld",a[n + m + 1]);
for(int i = n + m;i >= 0;i--)
printf("%lld",a[i]);
return 0;
}
第二份代码:
#include<bits/stdc++.h>
#define ll long long
#define fswap(x,y) x ^= y, y ^= x, x ^= y
using namespace std;
const ll P = 998244353,G = 3,Gi = 332748118;
int n,m,lim = 1,len,r[2100005];
ll a[2100005],b[2100005];
int read()
{
int x = 0,f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')x = (x << 1) + (x << 3) + ch - 48,ch = getchar();
return x * f;
}
ll ksm(ll x,ll y)
{
ll ret = 1;
while(y)
{
if(y & 1)
ret = ret * x % P;
x = x * x % P,y >>= 1;
}
return ret;
}
void NTT(ll *d,int tag)
{
for(int i = 0;i < lim;i++)
if(i < r[i])
fswap(d[i],d[r[i]]);
for(int i = 1;i < lim;i <<= 1)
{
ll wn = ksm(tag == 1 ? G : Gi,(P - 1) / (i << 1));
for(int j = 0;j < lim;j += (i << 1))
{
ll w = 1;
for(int k = 0;k < i;k++,w = w * wn % P)
{
int tx = d[j + k],ty = w * d[i + j + k] % P;
d[j + k] = (tx + ty) % P,d[i + j + k] = (tx - ty + P) % P;
}
}
}
}
char c1[1000005],c2[1000005];
int main()
{
scanf("%s",c1),n = strlen(c1) - 1;
scanf("%s",c2),m = strlen(c2) - 1;
for(int i = 0;i <= n;i++)
a[n - i] = c1[i] - '0';
for(int i = 0;i <= m;i++)
b[m - i] = c2[i] - '0';
while(lim <= n + m)
lim <<= 1,len++;
for(int i = 0;i < lim;i++)
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (len - 1));
NTT(a,1),NTT(b,1);
for(int i = 0;i <= lim;i++)
a[i] = a[i] * b[i] % P;
NTT(a,-1);
ll inv = ksm(lim,P - 2);
for(int i = 0;i <= n + m + 1;i++)
a[i] = a[i] * inv % P;
for(int i = 0;i <= n + m + 1;i++)
a[i + 1] += a[i] / 10,a[i] %= 10;
int anslen = n + m + 1;
while(a[anslen] == 0 && anslen > 0)
anslen--;
for(int i = anslen;i >= 0;i--)
printf("%lld",a[i]);
return 0;
}