1 solutions

  • 0
    @ 2025-4-6 22:16:14

    作为一个既搞数竞,又搞物竞,又搞信竞的人我很清楚这题肯定可以不用数位DP来做

    这其实就是一个简单的数学题,把这个整数转换成B进制,你就会发现一个很神奇的事情:

    B的幂变成(100...0)

    不同的B的幂之和变成了0和1的排列 那么,只需要把[X,Y]中的所有数都写成B进制,然后这些数里面恰好有K个1,其余都是0就行

    搞定!!!

    #include <bits/stdc++.h>
    using namespace std;
    
    string change_M(int x,int m)
    {
    	string ans = "";
    	while(x > 0)
    	{
    		char ch = '0' + x % m;
    		ans = ch + ans;
    		x /= m;
    	}
    	return ans;
    }
    
    int S(string s)
    {
    	int len = s.size(),sum = 0;
    	for(int i = 0;i < len;i++)
    	{
    		if(s[i] > '1') return -1;
    		sum += (s[i] - '0');
    	}
    	return sum;
    }
    
    int main()
    {
    	int s,m,x,y;
    	scanf("%d%d%d%d",&x,&y,&s,&m);
    	int cnt = 0;
    	for(int i = x;i <= y;i++)
    	{
    		if(S(change_M(i,m)) == s) cnt++;
    	}
    	printf("%d",cnt);
    	return 0;
    }
    

    然后...

    TE了。。。

    这题还真的不简单,因为Y最大可是2^31 - 1

    经过一晚上的抢救之后,也是终于做出来了复杂度低一点的办法,代码如下:(把string吃了)

    #include <bits/stdc++.h>
    using namespace std;
     
    const int N = 50;
     
    int h[N];
    int f[N][N];
    int k, x, y, b;
     
    int solve(int x) 
    {
        int top = -1;
        while (x) 
    	{
            int p = x % b;
            x /= b;
            h[++top] = p;
        }
        int tot = 0, ans = 0;
        for (int i = top; i >= 0; --i) 
    	{
            if (h[i] == 1) 
    		{
                ++tot;
                if (tot > k + 1)
                    break;
                if (i > 0)
                    ans += f[i - 1][k - tot + 1];
            } else if (h[i] > 1) 
    		{
                ans += f[i][k - tot];
                return ans;
            }
        }
        if (tot == k)
            ++ans;
        return ans;
    }
     
    int main() 
    {
        scanf("%d%d%d%d", &x, &y, &k, &b);
        f[0][0] = 1;
        f[0][1] = 1;
        for (int i = 1; i <= 31; i++) 
    	{
            f[i][0] = 1;
            for (int j = 1; j <= i + 1; j++) f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
        }
        --x;
        int ans = solve(y) - solve(x);
        printf("%d\n", ans);
        return 0;
    }
    
    • 1

    Information

    ID
    165
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    10
    Tags
    # Submissions
    8
    Accepted
    3
    Uploaded By