国庆集训 1104

为了使博客短一些，代码有一定压行，看不惯的请自行恢复……

算不出来math

真的很暴力

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 3e6+5;
int a[N], b[N], A[N], B[N], n, cnt;
ll ans;int P(int a) {
     for(; cnt*cnt<=a; cnt++); return --cnt;}int main() {
    scanf("%d", &n);for(int i = 1, ai; i <= n; i++) scanf("%d", &a[i])， A[a[i]]++;for(int i = 1, bi; i <= n; i++) scanf("%d", &b[i])， B[b[i]]++;for(int i = 1; i <= n; i++) {
    cnt = 0; for(int j = 0; j < a[i]; j++) ans += 1LL*P(a[i]-j)*B[j];cnt = 0; for(int j = 0; j < b[i]; j++) ans += 1LL*P(b[i]-j)*A[j];}printf("%lld\n", ans);return 0;
/其实开根取整可以直接用(int)sqrt( )实现,上面的p函数其实并没有什么用，但是可以快一些（见下）
}

优秀的p数组C++自带开根函数

Input 1
4
1 4 3 2

Output 1
3

Input 1
5
9 1 0 0 5

Output 1
8

蒟蒻数组版（思想是一样的，但是没有用数据结构优化，超时）

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e5+5;
int n;
int s[N], A[N], B[N], C[N], D[N];
ll ans;int main() {
    scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &s[i]);for(int i = 1; i <= n; i++) for(int j = i+1; j <= n; j++) {
    if(s[i] < s[j]) A[i]++, B[j]++;//A记录i后面有几个数与i构成顺序对，B是前面if(s[i] > s[j]) C[i]++, D[j]++;//C记录i后面有几个数与i构成逆序对，D是前面}for(int i = 1; i <= n; i++) {
    A[n+1] += A[i];C[n+1] += C[i];}//记录共有的顺序对，逆序对数量ans = 1LL*A[n+1]*C[n+1];//当abcd可以相同时的方案数for(int i = 1; i <= n; i++) ans -= 1LL*(A[i]+B[i])*(C[i]+D[i]);//把上面的式子拆开来//ans -= 1LL*A[i]*C[i]; ac相同的情况//ans -= 1LL*A[i]*D[i]; ad相同的情况//ans -= 1LL*B[i]*C[i]; bc相同的情况//ans -= 1LL*B[i]*D[i]; bd相同的情况printf("%lld\n", ans); return 0;
}

AC代码

思想与上面雷同，就是用树状数组优化，相信大家那么巨，一定能够看明白的。
当然因为数据范围太大，需要用$map$离散化一下， 这个应该难不倒各位$dalao$。

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e5+10;
ll n, ls[N], lb[N], rs[N], rb[N], c[N], cnt = 0;
ll a[N], b[N], cnt1, cnt2;
ll ans = 0;map <int, int> mp;
inline int lowbit(int x){
    return x&-x;}
inline void add(int x, int y){
    while(x<=cnt) c[x]+=y, x+=lowbit(x);}
inline int ask(int x){
    int y = 0;while(x) y+=c[x], x-=lowbit(x); return y;}
inline void add1(int x, int y){
    while(x) c[x]+=y, x-=lowbit(x);}
inline int ask1(int x){
    int y = 0;while(x<=cnt) y+=c[x], x+=lowbit(x); return y;}int main() {
    scanf("%d", &n);for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);b[i] = a[i];}sort(b + 1, b + 1 + n);for (int i = 1; i <= n; i++)if (!mp[b[i]]) mp[b[i]] = ++cnt;//离散化for (int i = 1; i <= n; i++) {
    cnt1 += ls[i] = ask(mp[a[i]] - 1);add(mp[a[i]], 1);}//处理顺序对，以i为后memset(c, 0, sizeof c);for (int i = 1; i <= n; i++) {
    lb[i] = ask1(mp[a[i]] + 1);add1(mp[a[i]], 1);}//处理逆序对，以i为后memset(c, 0, sizeof c);for (int i = n; i >= 1; i--) {
    cnt2 += rs[i] = ask(mp[a[i]] - 1);add(mp[a[i]], 1);}//处理逆序对，以i为前memset(c, 0, sizeof c);for (int i = n; i >= 1; i--) {
    rb[i] = ask1(mp[a[i]] + 1);add1(mp[a[i]], 1);}//处理顺序对，以i为前ans = cnt1 * cnt2;//总的方案数for (int i = 1; i <= n; i++) ans -= (lb[i]+rs[i])*(ls[i]+rb[i]);//减去不合法printf("%lld\n", ans);return 0;
}

Input 1
2
z?
?a

Output 1
0

Input 1
2
a?
?a

Output 1
650

#include<bits/stdc++.h>
#define ll long long
using namespace std;const ll mod = 990804011;
char ch[52][25];
int n, len, a[52][25];
ll ans, f[52][52][25][30];
//f[i][j][p][c]表示第i行到第j行前p-1个数都相等，填上c及c以上的方案数 inline ll M(ll a){
    return a%mod;}
inline ll add(ll a, ll b){
    return M(a+b);}
inline ll sub(ll a, ll b){
    return M(a-b+mod);}
inline ll mul(ll a, ll b){
    return M(a*b);}
//这个是取模题必备套餐inline ll dfs(int l, int r, int p, int c) {
    if(f[l][r][p][c] != -1) return f[l][r][p][c];//记忆化if(l > r) return 1;//如果满足所有条件，l为r+1的话，这种方案就会产生贡献（这是2号会导致的）if(p == len+1) return l==r;//如果一行到底了，如果l==r就会产生贡献（这是1号会导致的）//如果l<r，说明字典序不严格（这是1号会导致的，如果在1号处a[i][p]一直为空，就会一直下去，但是无贡献）if(c == 27)  return 0;//如果所有的字母都已经填过了，但是在上面却没有被退出，则不能产生贡献f[l][r][p][c] = dfs(l, r, p, c+1);//能在填c+1的情况下产生的方案，填c时必然成立for(int i = l; i <= r; i++) if(a[i][p] == c || a[i][p] == 27 && c) //如果本身就是要填的c，或者是问号，就往里面填a——zf[l][r][p][c] = add(f[l][r][p][c], mul(dfs(l, i, p+1, 0), dfs(i+1, r, p, c+1)));//后面满足的情况（1号），下面满足的情况（2号），两者互不影响，乘法原理得到else break;//如果不满足，就不会再往里面加贡献return f[l][r][p][c];//返回值
}int main() {
    scanf("%d", &n);for(int i = 1; i <= n; i++) {
    scanf("%s", ch[i]+1);len = max(len, (int)strlen(ch[i]+1));}  for(int i = 1; i <= n; i++)for(int j = 1; j <= len; j++) {
    if(ch[i][j] == '?') a[i][j] = 27;else if(ch[i][j]>='a' && ch[i][j]<='z') a[i][j] = ch[i][j]-'a'+1;else ch[i][j] = 0;}//强制对齐的数列操作，字母转换成数字，空为0，？为27memset(f, -1, sizeof(f));printf("%lld\n", dfs(1, n, 1, 0));//要求所有行前0位相同，？处填上任意字母的方案数return 0;
}