问题进入

k进制数的数位交换问题，就是给出一个k进制的数，求出其中任意两个数位交换后的大小

我们先以十进制数123为例，假如交换第一位和第二位变成213。那么这两个数之间存在什么关系呢，我们注意到百位上本来是1，变成了2之后原数就要增加(2-1)*100；十位上本来是2，变成1之后原数就要增加(1-2)*10。那么再考虑交换前左边的数小于右边的数，就变成了减的较多。总之，拿每一位变化后的数减去变化前的数再乘以该位的权值，不必去考虑谁大谁小，二者相加即是原数变化的值

我们得出了，假如一个k进制数n（n是转换为十进制的大小）的第i位和第j位(i在j左边)交换，其数位对应权值分别为a[i]和a[j]。那么交换后的十进制m=(i-j)*a[j]+(j-i)*a[j]

其中数位权值数组这样初始化：

int a[maxn];
int P; //对P取模，因为每一位可能很大 void init(string s,int k){
     //k进制的字符串s
    int m=s.size();
    a[m-1]=1;
    for(int i=m-2;i>=0;i--){
   
        a[i]=(a[i+1]*k)%P;
    }

}

1
2
3
4
5
6
7
8
9

例题解析

题目链接

有一个长度为 L 的字符串，每个字符是大写字母。如果我们把 A 看做 0 ，BB 看做 1 ，C 看做 2 … Z 看做 25，那么我们就得到了一个 26 进制的数字串。我们可以对这个字符串做一个操作：将两个位置的字母进行交换。这样得到了一个新的数字串。现在有一个十进制整数 M ，请判断是否可以通过做至多一次（可以不做）操作，使得得到的字符串是 M 的倍数

输入格式
第一行一个只包含大写字母的字符串
第二行一个整数 M

输出格式
如果初始串就可以，那么输出 “0 0”（不加引号）。如果通过一次操作可以，请输出交换的两个位置的标号（标号小的在前，从 1 开始）。如果有多解，输出字典序最小的。如果做不到，那么输出 “-1 -1”（不加引号）

数据范围
字符串长度为 L
对于 30% 的数据：1≤L≤10,1≤M≤100
对于 50% 的数据：除前面 30% 外， 1≤L≤500,M=5 或 25 或 26
对于 100% 的数据：1≤L≤2,000,1≤M≤200,000

#include<iostream>
#include<cstdio>
using namespace std;
const int N=2010;
int a[N];
 int n;
    string s; void init()
{
   
    int m=s.size();
    a[m-1]=1;
    for(int i=m-1;i>=1;i--)
    {
   
        a[i-1]=(a[i]*26)%n;
	}
}
int main()
{
   
    cin>>s;
    cin>>n;
    init();
    bool flag=0;
    int tmp=0;
    for(int i=0;i<s.size();i++)
        tmp=(tmp*26+s[i]-'A')%n; if(tmp==0)	
    {
   
        printf("0 0\n");
        return 0;
    }
    else
    {
   
    for(int i=0;i<s.size();i++)
       {
    for(int j=i+1;j<s.size();j++)
         {
      int res=(s[j]-s[i])*a[i]+(s[i]-s[j])*a[j]; if((res+tmp+n)%n==0)
            {
   
				flag=1;
                printf("%d %d\n",i+1,j+1);
                break;
            }
	         }
       if(flag)	break;
       }
         }  
    if(!flag)	
        printf("-1 -1\n");
    return 0;
}