题解 CF1202D 【Print a 1337-string...】

· · 题解

构造题
首先如果不考虑长度限制 很容易想到这样一种构造方式: 

13377...7

前面133的选择是确定的 所以有多少个7就代表有多少种方法取出1337
相当于每一个7会对方案数产生1的贡献

但是这样不满足长度限制
所以我们要让3选择的余地多一点 使得3不仅仅有两个
于是构造出来这样一个式子: 

133...3377...7

这里假设有n个3和m个7
选取1的方式有1种
选取3的方式有C_n^2=\frac{n(n-1)}{2}种
选取7的方式有m种

都是任意取 所以乘法原理乘起来是\frac{mn(n-1)}{2}
相当于每一个7会对方案数产生\frac{n(n-1)}{2}的贡献

但是题目中给定的数不一定能表示成这样 所以考虑把上面两种想法结合起来
首先在133确定的情况下加上k个7 然后加上n-2个3 最后加上m个7 

133 77...77 33...33 77...77

这样前面的7每一个会对答案产生1的贡献 后面的7每一个会对答案产生\frac{n(n-1)}{2}的贡献

方案数为 m\times \frac{n(n-1)}{2}+k
令这里0\leq k < \frac{n(n-1)}{2}

这样已经可以表示所有正整数了

为了保证10^5的长度限制 这里要合理选取n的大小

假设N=\frac{n(n-1)}{2}
这里直接考虑最劣情况 令k=N-1 M = \frac{10^9}{N}
所以N+n-1+\frac{10^9}{N}\leq 10^5

这里N取一个30000左右的数就可以了 实际上它的取值范围还挺广的 只要算出来对 答案随你取了

我这里n选择了300 这样N是45150 是可行的

讲得差不多了把...上代码了
code: 

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;

LL n,m,k,T;
LL cac = 0;
LL a[500005] = {0};

int main(){
    ios::sync_with_stdio(false);
    cin >> T;
    LL K = 300; // K 就是上文的 n
    while(T --){
        cin >> n;
        LL t1 = K * (K + 1) / 2,t;
        // t1是上文的 N
        t = n / t1;
        LL tmp = n - t1 * t;
        // tmp是上文的 k

        cout << "133";
        for(LL i = 1;i <= tmp;i ++) cout << '7';
        for(LL i = 1;i < K;i ++) cout << '3';
        for(LL i = 1;i <= t;i ++) cout << '7';
        // 构造过程

        cout << endl;
    }
    return 0;
}