【题目记录】——2021“MINIEYE杯”中国大学生算法设计超级联赛（2）

Love The Way You Lie 2022-08-31 12:27 94阅读 0赞

### 文章目录 ###

*  题目集地址
 *  1005 I Love string 思维
 *   *  题意
     *  思路
     *  AC代码
 *  1001 I Love Cube 数学
 *   *  题意
     *  AC代码
 *  1010 I Love permutation 数学 思维
 *   *  题意
     *  思路
     *  AC代码

# 题目集地址 #

[2021“MINIEYE杯”中国大学生算法设计超级联赛（2）][2021_MINIEYE_2]  
题目集原地址[2021“MINIEYE杯”中国大学生算法设计超级联赛（2）][2021_MINIEYE_2 1]  
这次题目集我们做出了1005和1012两个签到题

# 1005 I Love string 思维 #

[1005][]  
难度 简单

## 题意 ##

按照给出的序列的顺序放字符，每次可以将字符放在已有字符串的前面或者后面，要使最终的字符串字典序最小，问有多少中放字符的方法。

## 思路 ##

已有给定的字符顺序，要使得到的字典序最小，最终得到的字符串只能是唯一的，也就是说最开始放的几个相同的字符前后位置都可以放，后面的字符只有一个位置可以放，我们只需要判断最前面的字符放法即可，假设前几个相同字符个数为n，那么方法就是 2 ( n − 1 ) 2^(n-1) 2(n−1),于是题目的关键就是解决2的大数次幂。

## AC代码 ##

#include <iostream>
    #include <bits/stdc++.h>
    
    using namespace std;
    
    long long qpow(int n){ 
        long long ans = 1;
        long long a = 2;
        while(n){ 
            if(n&1)
                ans *= a;
    
            a *= a;
            a %= 1000000007;
            ans %= 1000000007;
            n >>= 1;
        }
        return ans;
    }
    
    int main()
    { 
        int n;
        cin >> n;
    // cout << qpow(n) << endl;
        while(n--)
        { 
            int num = 0;
            int m;
            string str;
            cin >> m >> str;
            if(str.size()==1)
            { 
                cout << 1 << endl;
                return 0;
            }
            else{ 
                for(int i = 1;i < int(str.size());i++)
                { 
                    if(str[i] == str[i - 1])
                    { 
                        num++;
                    }
                    else
                    { 
                        break;
                    }
                }
                cout << qpow(num) << endl;
            }
        }
        return 0;
    }

# 1001 I Love Cube 数学 #

[1001][]  
难度 简单

## 题意 ##

一个数学题，最后推得公式。。

## AC代码 ##

#include <iostream>
    #include <bits/stdc++.h>
    typedef long long ll;
    #define mod 1000000007
    using namespace std;
    
    int main()
    { 
        int t;
        cin >> t;
        while(t--)
        { 
            ll n;
            cin >> n;
            n--;
            if(n==-1)
            { 
                cout<<"0"<<endl;
            }
            else
            { 
                ll res=(((n%mod)*(n%mod)%mod)*(((n+1)%mod)*((n+1)%mod)%mod)*2)%mod;
                cout<<res<<endl;
            }
        }
        return 0;
    }

# 1010 I Love permutation 数学 思维 #

[1010][]  
难度 中等

## 题意 ##

给一个正整数a和奇素数P，a<P,创建一个长度为P-1的序列 b x = a x ( m o d    P ) ( 1 ≤ x ≤ P − 1 ) b\_x = a\_x(\\mod P)(1 \\le x \\le P-1) bx=ax(modP)(1≤x≤P−1),找出在这个序列中有多少对逆序数对，结果对2取模。

## 思路 ##

得到的数列显然是一个长度为P-1的排列，求排列的逆序对数对2取模的值，相当于求这个排列的奇偶性。  
令这个排列为 π \\pi π ,排列的第 i个数为 π ( i ) \\pi(i) π(i) ,排列的逆序对数为n( π \\pi π),sgn( π \\pi π)= − 1 n ( π ) -1^\{n(\\pi)\} −1n(π)可转换为： ∏ 0 < i < j < p b i − b j i − j \\prod\_\{0<i<j<p\}\\frac\{b\_i-b\_j\}\{i-j\} ∏0<i<j<pi−jbi−bj  
根据这个的答案来判断，如果等于1逆序对为偶数对，如果答案为−1，则逆序对为奇数对,-1对p取模得p-1。  
化简式子：  
 ∏ 0 < i < j < p b i − b j i − j = ∏ 0 < i < j < p a ∗ i % p − a ∗ j % p i − j = ∏ 0 < i < j < p a % p = a p ∗ ( p − 1 ) 2 % p = a ( p − 1 ) 2 % p \\prod\_\{0<i<j<p\}\\frac\{b\_i-b\_j\}\{i-j\}=\\prod\_\{0<i<j<p\}\\frac\{a\*i\\%p-a\*j\\%p\}\{i-j\}=\\prod\_\{0<i<j<p\}a\\%p=a^\{\\frac\{p\*(p-1)\}\{2\}\}\\%p=a^\{\\frac\{(p-1)\}\{2\}\}\\%p ∏0<i<j<pi−jbi−bj=∏0<i<j<pi−ja∗i%p−a∗j%p=∏0<i<j<pa%p=a2p∗(p−1)%p=a2(p−1)%p  
注意快速幂部分数值要大一些，我之前用unsigned long long 不行，因为a\*p的值可能到10^36位，或者用大数运算的方法算。

## AC代码 ##

#include <bits/stdc++.h>
    
    using namespace std;
    
    __int128 qpow(__int128 a, __int128 n,__int128 m){ 
    	__int128 ans = 1;
    	while(n){ 
    		if(n&1)
    		{ 
    			ans = a * ans % m;
    		}
    		a = a * a % m;
    		n >>= 1;
    	}
    	return ans;
    }
    
    int main()
    { 
        cin.sync_with_stdio(0);
        cin.tie(0);
        int t;
        cin >> t;
        while(t--)
        { 
            unsigned long long a, p, b;
            cin >> a >> p;
            b = qpow(a, (p-1)/2, p);
            if(b == 1)
            { 
                cout << 0 << endl;
            }
            else
            { 
                cout << 1 << endl;
            }
        }
        return 0;
    }

[2021_MINIEYE_2]: https://acm.hdu.edu.cn/search.php?field=problem&key=2021%A1%B0MINIEYE%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A82%A3%A9&source=1&searchmode=source
[2021_MINIEYE_2 1]: https://acm.hdu.edu.cn/userloginex.php?cid=985
[1005]: https://acm.hdu.edu.cn/showproblem.php?pid=6965
[1001]: https://acm.hdu.edu.cn/showproblem.php?pid=6961
[1010]: https://acm.hdu.edu.cn/showproblem.php?pid=6970