MHCSUF @ 2019-05-08 20:31:10
using namespace std;
int a[4010];
string s1,s2;
inline void addd(string s1,string s2) {
int a1 = s1.size(), a2 = s2.size();
for(ri i = 0; i < a1; ++ i)
for(ri j = 0; j < a2; ++ j)
a[a1 - i + a2 - j - 1] +=
(s1[i] -'0') * (s2[j] - '0');
for(ri i = 1; i <= a1 + a2; ++ i) {
a[i + 1] += a[i] / 10;
a[i] %= 10;
}
a[0] = a1 + a2;
while(a[a[0]] == 0 && a[0] > 1) a[0]--;} int main() {
//freopen("mul.in","r",stdin);
//freopen("mul.out","w",stdout);
getline(cin,s1);
getline(cin,s2);
memset(a,0,sizeof(a));
addd(s1,s2);
for (ri i = a[0]; i >= 1; -- i) cout<<a[i];
cout<<endl;
return 0;}
by aminoas @ 2019-05-08 20:32:33
希望更丰富的展现？使用Mark♂down
by NaCly_Fish @ 2019-05-08 20:34:43
可以看看这个。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define reg register
#define p 998244353
#define N 2000003
using namespace std;
int rev[N];
inline int power(int a,int t){
int res = 1;
while(t){
if(t&1) res = (ll)res*a%p;
a = (ll)a*a%p;
t >>= 1;
}
return res;
}
struct bigint{
int a[N];
int t;
};
inline void NTT(bigint& f,int type,int lim){
for(reg int i=1;i<=lim;++i){
if(i>=rev[i]) continue;
swap(f.a[i],f.a[rev[i]]);
}
reg int w,rt,x,y,r,idx;
for(reg int mid=1;mid<lim;mid<<=1){
r = mid<<1;
rt = power(3,(p-1)/r);
if(type==-1) rt = power(rt,p-2);
for(reg int j=0;j<lim;j+=r){
w = 1;
for(reg int k=0;k<mid;++k){
idx = j+k;
x = f.a[idx];
y = (ll)w*f.a[idx+mid]%p;
f.a[idx] = x+y;
if(f.a[idx]>=p) f.a[idx] -= p;
f.a[idx+mid] = x-y+p;
if(f.a[idx+mid]>=p) f.a[idx+mid] -= p;
w = (ll)w*rt%p;
}
}
}
}
inline bigint multiply(bigint f,bigint g){
int lim = 1,l = -1,n = f.t,m = g.t,inv;
while(lim<=n+m){
lim <<= 1;
++l;
}
inv = power(lim,p-2);
for(reg int i=1;i<=lim;++i)
rev[i] = (rev[i>>1]>>1)|((i&1)<<l);
NTT(f,1,lim),NTT(g,1,lim);
for(reg int i=0;i<=lim;++i)
f.a[i] = (ll)f.a[i]*g.a[i]%p;
NTT(f,-1,lim);
f.t = n+m;
for(reg int i=0;i<=f.t;++i)
f.a[i] = (ll)f.a[i]*inv%p;
for(reg int i=0;i<=f.t;++i){
if(f.a[i]<10) continue;
f.a[i+1] += f.a[i]/10;
f.a[i] %= 10;
}
while(f.a[f.t+1]) ++f.t;
return f;
}
inline void read(bigint &f){
int b[N];
int len = 0;
char c = getchar();
while(c<'0'||c>'9') c = getchar();
while(c>='0'&&c<='9'){
b[len++] = c-'0';
c = getchar();
}
f.t = len-1;
for(reg int i=0;i<=f.t;++i)
f.a[i] = b[f.t-i];
}
inline void print(bigint f){
for(reg int i=f.t;i>=0;--i)
putchar(f.a[i]+'0');
putchar('\n');
}
bigint f,g;
int main(){
read(f),read(g);
print(multiply(f,g));
return 0;
} by aminoas @ 2019-05-08 20:36:08
wtf?!
NTT ...
美食九连
by wxwoo @ 2019-05-08 20:38:26
多项式全家桶
by MHCSUF @ 2019-05-08 20:58:53
@NaCly_Fish
谢谢大佬
虽然我看不懂
而且高精不用这么麻烦吧
话说NTT不是数论变换吗?
by NaCly_Fish @ 2019-05-08 21:03:51
@柯云超 按多项式乘法来做高精乘，复杂度降到n log n
by MHCSUF @ 2019-05-08 21:07:34
这是最小生成树，不想再发帖了， 那个“Markdown”好像挺好用的emmm
依然是样例过，测评全炸
我脸好黑啊...
模板都过不了....
#include<bits/stdc++.h>
#define ll long long
#define ri register int
using namespace std;
const int INF=0x7fffffff;
int n, m, dis[5010], e[5010][5010];
bool vis[5010];
void init(int k) {
for(int i = 1; i<=k; i++) {
for(int j = 1; j<=k; j++)
e[i][j] = INF;
dis[i] = INF;
}
}
int prim() {
int sum = 0;
dis[1] = 0;
for(ri i = 1; i<=n; i++) {
int minn = INF, cmin;
for(ri j = 1; j <= n; j++) {
if(!vis[j] && minn > dis[j])
minn = dis[j],
cmin = j;
}
vis[cmin] = 1;
sum += minn;
for(ri j = 1; j <= n; j++) {
if(!vis[j] && e[cmin][j] < dis[j])
dis[j] = e[cmin][j];
}
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
init(n);
for(ri i = 1; i <= m; ++ i) {
ri x, y, val;
cin >> x >> y >> val;
e[x][y] = e[y][x] = val;
}
cout << prim() << endl;
return 0;
}by MHCSUF @ 2019-05-08 21:08:21
@NaCly_Fish
时间变快了
空间好像变大了吧...
by MHCSUF @ 2019-05-08 21:15:34
此贴转移至
https://www.luogu.org/discuss/show/113368