打开/关闭菜单
打开/关闭外观设置菜单
打开/关闭个人菜单
未登录
未登录用户的IP地址会在进行任意编辑后公开展示。

目前wiki关闭了自行注册账号的功能,如需注册账号,请查阅Help:注册账号

用户:HermitOvO:修订间差异

39次编辑加入
HermitOvO留言 | 贡献
无编辑摘要
HermitOvO留言 | 贡献
无编辑摘要
第25行: 第25行:
* '''<big>记不住的东西:</big>'''
* '''<big>记不住的东西:</big>'''


算法知识点:<code>#include</code>
算法知识点:
{| class="mw-collapsible mw-collapsed wikitable"  
{| class="mw-collapsible mw-collapsed wikitable"  
|-
|-

2022年8月23日 (二) 23:31的版本

这里是慕斯sama!(一直想改名为musesama,但是因为hermit的名称已经在各大论坛上了索性就用这个了)

会点中式建筑,有点红石技艺,浅尝辄止pvp,正在被带领学习中世纪建筑(

不善交际的美少女一枚捏(大概

  • 出没地点:

bilibili

zth-ria

洛谷

codeforce

AtCoder

Acwing

吾爱论坛

各大群聊

  • 记不住的东西:

算法知识点:

FFT 前方检测到核聚变打击,请谨慎打开!
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 300000; const double PI = acos(-1);

struct Complex {

   double x, y;
   Complex operator+ (const Complex& t) const
   {
       return {x + t.x, y + t.y};
   }
   Complex operator- (const Complex& t) const
   {
       return {x - t.x, y - t.y};
   }
   Complex operator* (const Complex& t) const
   {
       return {x * t.x - y * t.y, x * t.y + y * t.x};
   }

}a[N], b[N]; char s1[N], s2[N]; int res[N]; int rev[N], bit, tot;

void fft(Complex a[], int inv) {

   for (int i = 0; i < tot; i ++ )
       if (i < rev[i])
           swap(a[i], a[rev[i]]);
   for (int mid = 1; mid < tot; mid *= 2)
   {
       auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)});
       for (int i = 0; i < tot; i += mid * 2)
       {
           auto wk = Complex({1, 0});
           for (int j = 0; j < mid; j ++, wk = wk * w1)
           {
               auto x = a[i + j], y = wk * a[i + j + mid];
               a[i + j] = x + y, a[i + j + mid] = x - y;
           }
       }
   }

}

int main() {

   scanf("%s%s", s1, s2);
   int n = strlen(s1) - 1, m = strlen(s2) - 1;
   for (int i = 0; i <= n; i ++ ) a[i].x = s1[n - i] - '0';
   for (int i = 0; i <= m; i ++ ) b[i].x = s2[m - i] - '0';
   while ((1 << bit) < n + m + 1) bit ++ ;
   tot = 1 << bit;
   for (int i = 0; i < tot; i ++ )
       rev[i] = ((rev[i >> 1] >> 1)) | ((i & 1) << (bit - 1));
   fft(a, 1), fft(b, 1);
   for (int i = 0; i < tot; i ++ ) a[i] = a[i] * b[i];
   fft(a, -1);
   int k = 0;
   for (int i = 0, t = 0; i < tot || t; i ++ )
   {
       t += a[i].x / tot + 0.5;
       res[k ++ ] = t % 10;
       t /= 10;
   }
   while (k > 1 && !res[k - 1]) k -- ;
   for (int i = k - 1; i >= 0; i -- ) printf("%d", res[i]);
   return 0;

}