题目链接

送分题，菜到考场上没 $A$。

$sort$ $+$ $set$ 无脑组合。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
using namespace std;

const int maxn = 1e4 + 10;
int n; string str;
set<string> s;

int main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    scanf("%d",&n);
    for (int i = 1; i <= n; i++){
        cin >> str; sort(str.begin(),str.end()); 
        s.insert(str);
    }
    cout << s.size() << endl;
    return 0;
}

T2

这时题目变成了给定一个数($sum_{i=1}^{x}p_i$)，求用一些数之和($p_1,p_2,…,p_x$)表示的方案数有多少。(类似于洛谷 P1025)

下面是考场代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int n,ans;

inline bool check(int a, int b, int c){
    return a+b>c && a+c>b && b+c>a && n%(a+b+c) == 0;
}

int gcd(int a, int b){
    return !b ? a : gcd(b,a%b);
}

int poww(int base, int k){
    if (k == 0) return 1;
    if (k == 1) return base;
    int p = poww(1ll*base*base%mod,k>>1);
    if (k&1) return p * base % mod;
    else return p % mod;
}

int main(){
    scanf("%d",&n);
    for (int a = 1; a <= n; a++)
    for (int b = a; b <= n; b++)
    for (int c = b; c <= n; c++){
        if (a + b + c > n || !check(a,b,c)) continue;
        int p = gcd(a,b); if (gcd(p,c) > 1) continue;
        ans += poww(2,n/(a+b+c)-1);
        if (ans > mod) ans %= mod;
    }
    printf("%dn",ans);
    return 0;
}

不出所料，得到了 $60pts$。

回家后参照着网上的题解进行优化。

不妨设 $a leq b leq c$，用 $f[i]$ 表示相似比之和为 $i$ 的不同组合有几个。

考虑转移，可以分开两种情况计算：

• $a leq b = c$。显然这时 $b,c$ 是有上下界的，不难得出 $lceil frac{i}{3} rceil leq b,c leq lfloor frac{i-1}{2} rfloor$。
• $a leq b lt c to a leq b leq c-1$。不难发现这时就是 $f[i-1]$。当然，事情没有这么简单。若我们原本的 $a + b = c$，这时构不成三角形，但若转移到 $a leq b leq c-1$，就满足了 $a + b = c > c-1$。换句话说，我们转移过去的时候，把本来构不成三角形的 $a+b=c$ 的情况算了进去。根据容斥原理，现在我们要再减下去。当 $a+b=c$ 时，$i = a+b+c = 2 times (a+b)$，由此可得 $a in [1,frac{i}{4}]$。同时可以注意到，只有当 $i$ 为偶数时才会出现这种情况。

另外，不要忘记把 $f[i]$ 中所有计算过的三角形削去。而这些三角形的数量，正是 $sum f[p] : : (p mid i)$。

下面是正解代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;

const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int n,i,f[maxn],m[maxn]; ll ans;

int quickPow(int base, int k){
    if (k == 0) return 1;
    if (k == 1) return base;
    int p = quickPow(1ll*base*base%mod,k>>1);
    if (k&1) return 1ll * p * base % mod;
    else return p % mod;
}

int main(){
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    scanf("%d",&n); f[3] = 1;

    for (i = 4; i <= n; i++){
        f[i] = f[i-1] + ((i-1)>>1) - ceil(i/3.0) + 1;
        if (!(i&1)) f[i] -= (i>>2);
        if (f[i] >= mod) f[i] %= mod;
        if (f[i] < 0) f[i] += mod;
    }
    for (i = 2; i <= n; i++)
        for (int j = 2; i*j <= n; j++){
            f[i*j] -= f[i];
            if (f[i*j] < 0)
                f[i*j] += mod;
        } 

    for (i = 1; i*i < n; i++){
        if (n % i) continue; 
        ans += 1ll * f[i] * quickPow(2,n/i-1);
        if (ans >= mod) ans %= mod;
        ans += 1ll * f[n/i] * quickPow(2,i-1);
        if (ans >= mod) ans %= mod;
    }
    if (i*i == n) 
        ans += 1ll * f[i] * quickPow(2,i-1);
    printf("%lldn",ans%mod);
    return 0;
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 [email protected]。