【推式子or打表】牛客小白月赛E 最值区间计数

梦里梦外; 2024-03-30 13:24 46阅读 0赞

[E-最值区间计数\_牛客小白月赛63 (nowcoder.com)][E-_63 _nowcoder.com]

题意：

![89d4d998ca27438a9bf6e560bc4d2564.png][]

思路：

法一：推式子

对于区间确定的情况，去算一算组合数：

**两层sigma是可以嗯推的**

![4d540b5af9a3430c830787c920335226.jpeg][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mod=998244353,mxn=1e6+10;
    int n;
    int fac[mxn];
    void solve(){
        cin>>n;
        if(n==1){
            cout<<1<<'\n';
            return;
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            ans+=(i*n*(n-i)+(n-i)*i-i*(i+1+n)*(n-i)/2ll)%mod;
            ans%=mod;
        }
        ans=(((ans*2)%mod)*fac[n-2])%mod;
        cout<<ans%mod<<'\n';
    }
    void init(){
        fac[0]=1;
        for(int i=1;i<mxn;i++) fac[i]=(fac[i-1]*i)%mod;
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

法二：打表

遇到不会的题显然只有打表吧qwq

打表之后找规律

不难发现相邻两项之间的差的关系

Code：

#include<bits/stdc++.h>
    #define int long long
    #define PII pair<int,int>
    #define x first
    #define y second
    
    using namespace std;
    const int N = 2e5 + 9, P = 998244353;
    int T, n, m, a[N];
    
    int f(int n = 1) {
    	//	if (n > 13) return;
    	for (int i = 1; i <= n; i++) a[i] = i;
    	int ans = 0;
    	do {
    		for (int i = 1; i <= n; i++) {
    			for (int j = i; j <= n; j++) {
    				int res = 0;
    				for (int k = i; k <= j; k++) {
    					res += a[k] == 1;
    					res += a[k] == n;
    				}
    				ans += res == 2;
    			}
    		}
    	} while (next_permutation(a + 1, a + n + 1));
    	return ans;
    	//	cout << n << " " << ans << " \n";
    	//	f(n + 1);
    }
    signed main() {
    	ios::sync_with_stdio(false);
    	cin >> n;
    	if (n < 10) {
    		cout << f(n);
    		return 0;
    	}
    	int ans = 10, d = 6;
    	for (int i = 4; i <= n; i++) {
    		ans = ans * d % P;
    		d++;
    	}
    	cout << ans;
    	return 0;
    }

**总结：**

**如果发现我们能暴力解决问题，那就去试试打表找规律**

**组合计数的推式子，两层sigma是可以化简简化复杂度的**

[E-_63 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/49030/E
[89d4d998ca27438a9bf6e560bc4d2564.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a2b9be34f53f4fb4b11baf4bddc87af1.png
[4d540b5af9a3430c830787c920335226.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/61d654da1b504d5cb607a606136a633c.jpeg