烤面包片

Description:
鸡尾酒最喜欢吃东北的烤面包片了。每次到东北地区的区域赛或者是秦皇岛的wannafly camp，鸡尾酒都会吃很多的烤面包片，即使比赛打铁也觉得不枉此行。

“我想吃烤面包片！！！”这不，半年没吃烤面包片的鸡尾酒看到大家都聚集在秦皇岛参加暑假camp，羡慕地发出了想要的声音。

当鸡尾酒“想要”的时候，他说的话会带三个感叹号来表示非常“想要”。至于有多“想要”，他给了你一个算式让你来体会。

给你两个整数 nn 和 modmod，输出 n!!!n!!! 对 modmod 求余的结果（每个!! 都代表一个阶乘符号）

输入描述

输入共一行包含两个整数依序为 n 和 mod，意义如题面所示。（0≤n≤1e9，1≤mod≤1e9）

输出描述

输出一个小于 mod的非负整数表示答案。

样例输入 1

2 6324

样例输出 1

2

样例输入 2

3 999999999

样例输出 2

731393874

提示

在第一个样例中，由于 2! = 22!=2，所以 2!!! = (((2!)!)!) = ((2!)!) = (2!) = 22!!!=(((2!)!)!)=((2!)!)=(2!)=2。2模了6324还是2！所以答案为2。

Problem solving:
这道题一看就吓着我了，阶乘的阶乘的阶乘，这个数可以很大的。我已开始甚至想到了大数打表，但是那样的话时间复杂度也很不乐观，可是这道题过的人还那么多。

在我的师父——著名acmer——cc的讲解下我知道了这道题的解法。

如果n是1，或者是2，那么他们阶乘的阶乘就是本身。可以直接输出它本身对mod取模。n是0的情况跟n为1是一样的，因为0的阶乘是1嘛。
如果n是3，按照题目中的方式计算即可。
如果n>=4,就会出现一个很nb的现象，4!!!是大于1e9很多的，也就是说此时的答案为0.为什么为0呢，因为n大于1e9，mod最大才是1e9，n的阶乘算的过程中一定会乘到一个跟mod相等的数，相等的数取模为0,0乘任何数都为0，所以答案是0.

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,mod,nn=720;
ll solve()
{
      if(n==0||n==1)    return 1%mod;
      if(n==2)        return 2%mod;
      if(n>3)            return 0;
    ll mid=1;
    for(ll i=1;i<=nn;i++)
    {
        mid*=i;
        mid%=mod;
    }
    return mid;
}
int main()
{
    cin>>n>>mod;
    n=solve();
    cout<<n<<endl;
}

幂次方

Description:
任何一个正整数都可以用2的幂次方表示。例如：
137=2^7+2^3+2^0
同时约定方次用括号来表示，即ab可表示为a（b）。
由此可知，137可表示为：
2（7）+2（3）+2（0）
进一步：7=2^2+2+2^0（2^1用2表示）
3=2+2^0
所以最后137可表示为：
2（2（2）+2+2（0））+2（2+2（0））+2（0）
又如：
1315=2^10+2^8+2^5+2+1
所以1315最后可表示为：
2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）

输入描述:

正整数（n ≤ 20000）

输出描述:

符合约定的n的0，2表示（在表示中不能有空格）

示例1
输入

1315

输出

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

Problem solving:
一开始想着用二进制形式表示，然后通过一些特殊的手段一直找1的位置，可以用bitset来实现，可是没写出来，希望如果有大佬会写的话教一下我，感激不尽。

然后我去百度了一下这道题，就被这道题巧妙地思路给震撼到了。通过递归实现。
思路大概就是先找到小于当前数的最大的2的次方数，然后查找下一个2的次方数，这道题用到了递归，就会很抽象一项（像某fs一样令人脱发。不太好理解，多看看代码吧。
说实话我也没很懂，啧啧啧

Code:

#include<bits/stdc++.h>
using namespace std;
void solve(int n)
{
    if(n>4)
    {
        int t=1;
        while(pow(2,t)<=n)    t++;
        cout<<"2(";
        solve(t-1);
        cout<<")";
        if(n!=pow(2,t-1))    cout<<"+";
        solve(n-pow(2,t-1));
    }
    else
        switch(n)
        {
            case 0:return ;
            case 1:cout<<"2(0)"; break;
            case 2:cout<<"2"; break;
            case 3:cout<<"2+2(0)";break;
            case 4:cout<<"2(2)";
        }
}
int main()
{
    int n;
    cin>>n;
    solve(n);
}
赏