这是 goodbye2018 的 D 题, 红包赛第一场的 C 题
是我打的第一场 CF
不知道为什么每次一补到这一场我就要强调一遍这是我的第一场 CF......
....
....
真矫情
不过还挺有仪式感的, 嗯嗯~ o(~▽~)o
看题吧
这题是肯定有公式的, 不然这么乱七八糟的真的很难找规律, 而且题目的名字就是 permutation concatenation
这个题目真的很坏, 只给了 n=3 时 ans=9;n=4 时 ans=56;
其实如果知道了 n=5 时, ans=395, 问题就迎刃而解了
我的方法跟官方题解的不一样, 题解用的是分析 next_permutation 的操作原理, 然后给这个题目推出了一个公式
但是对于我们这种, 没法在短短十几分钟内把握整个题目全部操作的人, 肯定很难一口气把公式给推出来
但是, 我们可以打表
打表代码如下:
- #include<bits/stdc++.h>
- using namespace std;
- //#define int long long
- const int N = 1e8;
- int a[N];
- int b[N];
- int ans, cnt,sum,n;
- int32_t main(){
- while(scanf("%d",&n)==1&&n!=-1){
- ans = cnt = sum = 0;
- for (int i = 0; i <n; i++)
- a[i] = i+1;
- do
- {
- for (int i = 0; i < n; i++){
- b[++cnt] = a[i];
- }
- } while (next_permutation(a,a+n));
- for (int i = 1; i<=cnt-n+1;i++){
- sum = 0;
- for (int j = i; j <i+n;j++)
- sum += b[j];
- if(sum==n*(n+1)/2)
- ans++;
- }
- cout << ans<<endl;
- }
- system("pause");
- return 0;
- }
打表的时候有两个地方要提:
1. 不用 mod 的话, 我们开一个 1e8 的数组, 最多可以显示到 n=10 的位置
再多就不行了
2. 打表的结果:
现在来分析怎么得出一个菜鸟也能找出来的规律, 而不是题解里的那种规律
- n=1: ans=1;
- n=2: ans=2;
- n=3; ans=9=3!+3;
- n=4; ans=56=4!+32;
- n=5: ans=395=5!+275;
首先, 为什么提出来一个 i 的阶乘?
因为题目是将 1~n 的数进行全排列, 那么首先全排列的种类就是 n! 的阶乘个
所以最后的答案里面, 肯定有一部分是属于 n! 的阶乘的
即使是傻瓜解法, 也必须把这一步的原理给弄清楚, 才可以继续往下找规律, 不然傻瓜解法也救不了你
所以我们把这个答案给拆开了, 拆成了 n! 和一个不知道是什么的数
接下来跟初中高中找规律是一样的, 我们不从原理出发, 只从式子本身出发, 很容易发现一个规律. 规律就在后面的代码里
不必多说了, 毕竟这个原理我也说不清楚, 只能用我这种笨方法来写
比赛的时候, 如果要打表解决的话, 注意的就是
别打错了... 数组别开小了
其他的没什么好说的
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N = 1e6+100;
- const int mod = 998244353;
- //ll factorial(ll a){
- // ll num=1;
- // for (ll i = 1; i <= a;i++)
- // num =(num * i) % mod;
- // return num;
- //}
- ll a[N];// 这里储存之前的所有值, 神秘递推式
- int main(){
- ll n;
- cin>> n;
- a[1] = 1;
- ll fact = 1;
- for (ll i =2; i <= n;i++){
- fact = fact * i % mod;
- a[i] = (i * (a[i - 1] - 1) + fact) % mod;
- }
- cout << a[n];
- system("pause");
- return 0;
- }
对于这个代码我还有个疑问, 为什么我写的 factorial 函数通过不了呢?
输入 1000000 之后直接 RE 了, 不输出数据
留待以后去解决;
其他的题解实在是看不懂, 大家的思路都跟着官方题解走, 但是又解释不清楚;
整篇题解的思路来自这个博主: hyacinthLJ
感谢!! 万分感谢!!!
来源: http://www.bubuko.com/infodetail-2946188.html