codeforces educational round86 solution

标题

C题：
给定a，b。q次询问，问l-r区间内满足x%a%b != x%b%a 的x的个数
首先证明[1,ab]区间内的个数和[ab+1, 2a*b]内的x的个数相同，十分显然，因为(x+ab)%a%b = (x)%a%b
所以预处理[1，ab]种所有，满足条件的x的个数，再用前缀和的思想。

#include 
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector VI;
typedef long long ll;
typedef pair PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
//int T;
const int N = 2e5 + 50;
ll s[N];
ll a, b, q;
ll work(ll x){
    return x/(a*b) * s[a*b] + s[x % (a*b)];
}
int main()
{
    int t; cin >> t;
    while(t --){
        cin >> a >> b >> q;
        rep(i, 1, a*b + 1){
            s[i] = s[i - 1] + (i % a % b != i % b % a);
        }
        while (q --){
            ll l, r; cin >> l >> r;
            cout << work(r) - work(l - 1) << ' ';
        }
        cout << '\n';
    }
    return 0;
}

D题：
要求将一个数组分成几部分。
并且对每个值有次数限制。lim数组
其实很简单。对于每一个数a，sum[a]++存在一个桶里面，从后往前扫限制的数组，ans=max(ans,sum(后缀和)/lim[i]的上取整)
构造就比较容易得到。

#include 
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector VI;
typedef long long ll;
typedef pair PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N = 2e5 + 50;
int n, k; 
int sum[N], lim[N], a[N];
int main()
{
    cin >> n >> k;
    rep(i, 1, n + 1) {cin >> a[i], sum[a[i]] ++;}
    rep(i, 1, k + 1)  cin >> lim[i];
    int ans = 0, s = 0;
    per(i, 1, k + 1) {
        s += sum[i];
        ans = max(ans, (s % lim[i]) ? s / lim[i] + 1 : s / lim[i]);
    }
    sort(a + 1, a + n + 1);
    cout << ans << '\n';
    rep(i, 1, ans + 1){
        int cnt = 0;
        for (int j = i; j <= n; j += ans)
            cnt ++;
        cout << cnt << " ";
        for (int j = i; j <= n; j += ans)
            cout << a[j] << " ";
        cout << '\n';
    }
    return 0;
}

E. 赛后学习了一下第二类斯特林数。
先说一下第一类斯特林数：s(n,k)

第一类斯特林数

组合意义

s(n,k)表示把n个数分成k组，每组是一个环，求分成的方案数。
也就是一个轮子，怎么转都是一样的，如：1,2,3,4 和 4,1,2,3 只算一种方案。

递推式

即要么自成一个环，要么加入其它k个环，可以插入n−1个位置。（每两个数之间）
当然边界条件[0,0]=1
性质：1.
2.
3.

第二类斯特林数

组合意义

组合意义：S(n,k)表示吧n个数分成k组，组内无序，每组没有区别。

递推式

通项公式

E题的意思就是将车摆满n*n的棋盘，且恰好有k对车能够相互攻击，问有多少种摆放方式？

要么每一行摆一个车，要么每一列摆一个车，不妨考虑一种，最后2
先假设所有车在不同列，那么每次挪动一个车都会增加一对贡献。反之，假设原来的k对车能相互攻击，那么也能够还原到n列。所以一定最后剩余n-k列有车。
所以答案就是s(n,n-k)p(n,n-k)*2
代码疯狂