真分数的幂级数展开
求2*x/(1-2x+x^2)
相关的系数的差分方程为x^2-2*x+1=0
所以设置a(n)=A*n+B,特解有：
a(0)=B=0
a(1)=A+B=2
Go
A=2
B=0
Go
a(n)=2*n
所以S=2*x/(1-2x+x^2)=2*x+(2*2)*x^2+(2*3)*x^3+...+(2*n)*x^n
S*x=2*x^2+(2*2)*x^3+(2*3)*x^4+...+(2*n)*x^(n+1)
Go
S-S*x=2*x+2*(x^2+x^3+...+x^n)-(2*n)*x^(n+1)
Go
S*(1-x)=2*x+2*{x^2-x^(n+1)}/(1-x) -(2*n)*x^(n+1)
Go
S*(1-x)=2*x+2*{x^2-x^(n+1)}/(1-x) -(2*n)*x^(n+1)
当x<1,而n比较大的时候，x^(n+1)=0，
GO
S*(1-x)=2*x+2*{x^2}/(1-x) 
Go
S=2*x/(1-x)^2得到证明。
从上面也可以看出这种推导方法也是母函数的来历。
下面写程序来证明：
(defun pow (num count)
(if (or (> count 1) (eq  count  1) )
      (* num 
         (pow num 
              (- count 1) ) )
      1))
 
(defun slayer ( count)
(if (or (> count 1) (eq  count  1) )
      (* count 
         (slayer  
              (- count 1) ) )
      1))
 
 
(defun  expr  (n x)
(if  (=   n  0)
      0
     (+  (expr  (1-  n)
                x)
         (*  (*  2.0  
                 n)
             (pow  x
                   n)))))  
 
 
(defun  formula ( x)
(/  (*  2.0  
        x)
    (pow  (-  1  x)
          2)))
 
(defun  test (n)
(if (> n 0)
  (progn 
       (print (expr   n  0.9))
       (print  'compare)
       (print (formula  0.9))       
       (test (- n 1)))
  (print 'over)))
 
(test  50) 
x的值越小，n的值越大，两者的值越吻合。
 
 

sum of powers
题目：已知并且
求最小的正数M，使得ak+1,ak···a0都是整数；
分母求最小公倍数就可以；
注意n^k的系数是C(k+1,1)*b1+(k+1)；
注意最大公约数为负数的情况，强制转化为正数，用分子保存整个分数的正负性，因为题目要求最小的正数M
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=25;
ll c[maxn][maxn];
struct PP
{
    ll a,b;//分子、分母
};
PP b[maxn],ans[maxn];
/*ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}*/
ll gcd(ll a,ll b)
{
    if(a%b==0)
    {
        if(b>0)
        return b;
        return -b;
    }
    return gcd(b,a%b);
}
PP add(PP a,PP b)//模拟两个分数的加法
{
    if(!a.a)//如果有一个为零
        return b;
    if(!b.a)
        return a;
    ll temp=a.b/gcd(a.b,b.b)*b.b;//求出分母的最小公倍数
    PP res;
    res.a=temp/a.b*a.a+temp/b.b*b.a;//分子相加
    res.b=temp;
    if(res.a)//约掉最大公约数
    {
        ll tt=gcd(res.a,res.b);
        res.b/=tt;
        res.a/=tt;
    }
    return res;
}
void init()
{
    memset(c,0,sizeof(c));
    for(int i=0;i<maxn;i++)//预处理组合数
    {
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    b[0].a=1;//求伯努利数
    b[0].b=1;
    for(int i=1;i<=20;i++)//用递推关系求
    {
        PP temp;
        temp.a=0;
        temp.b=0;
        for(int j=0;j<i;j++)
        {
            PP tt=b[j];
            tt.a=tt.a*c[i+1][j];
            if(tt.a)
            {
                ll te=gcd(tt.a,tt.b);
                tt.a/=te;
                tt.b/=te;
            }
            temp=add(temp,tt);
        }
        temp.a=-temp.a;
        temp.b*=c[i+1][i];
        if(temp.a)
        {
            ll te=gcd(temp.a,temp.b);
            temp.a/=te;
            temp.b/=te;
        }
        else
            temp.b=0;
        b[i]=temp;
    }
}
int main()
{
    init();
    int k;
    while(~scanf("%d",&k))
    {
        ll cur=1;
        for(int i=0;i<=k;i++)
        {
            if(i==1)
            {
                ans[i].a=k+1;//b[1]要加上后面多出来的n^k
                ans[i].b=2;
            }
            else
            {
                ans[i]=b[i];
                ans[i].a*=c[k+1][i];
            }
            if(ans[i].a)//约分
            {
                ll temp=gcd(ans[i].a,ans[i].b);
                ans[i].a/=temp;
                ans[i].b/=temp;
            }
            else
                ans[i].b=0;
            if(ans[i].b)//求分母的最小公倍数
                cur=cur/gcd(cur,ans[i].b)*ans[i].b;
        }
        printf("%lld ",cur*(k+1));
        for(int i=0;i<=k;i++)//求出通分后每一项的系数
        {
            if(ans[i].b)
                ans[i].a=cur/ans[i].b*ans[i].a;
        }
        for(int i=0;i<=k;i++)
            printf("%lld ",ans[i].a);
        printf("0\n");//最后一个一定为零
    }
}

Problem Link

Leonardo’s Notebook 

大意：水题判断是否存在一个置换T,  s.t  T2=T′.



Analysis

由置换的性质，若T′可以开方，则它的每一个循环都可以开方，而由于2是质数，如果，循环节是奇数，那么它是一定可以开方的，如果循环节是偶数，由于T2，一定会分裂成两个相等的循环，因此，这个为偶数的相等的循环一定是偶数个。



AC code



Source Code

Problem: 3128       User: taotao
Memory: 704K        Time: 0MS
Language: G++       Result: Accepted
Source Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstring>

using namespace std;
const int maxn = 1111;
int n  = 26;
int a[26];

char s[30];

int num[30];
bool vis[30];

bool  solve()
{
    memset(num,0,sizeof(num));
    memset(vis,false,sizeof(vis));
    int cnt =0;
    for(int i=0 ; i<n ; ++i)
    {
        if(!vis[a[i]])
        {
            cnt  =0;
            int tmp =a[i];
            while(!vis[tmp])
            {
                cnt++;
                vis[tmp] = true;
                tmp = a[tmp];
            }
            num[cnt]++;
        }
    }

    for(int i =0 ; i<=26 ; i+=2)
        if(num[i]&1)return false;
    return true;
}

int main()
{
    //freopen("H:\\c++\\file\\stdin.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s);
        for(int i= 0 ; i<n ; ++i)
            a[i] = s[i]-'A';
        if(solve()){
            cout<<"Yes"<<endl;
        }else cout<<"No"<<endl;
    }
    return 0;
    }

链接：https://ac.nowcoder.com/acm/contest/946/A

筱玛爱地理

题目描述
筱玛是一个热爱地理的好筱玛。最近，在《地理II》作业本上，筱玛学到了“贝塔指数”的概念：
在经济地理学中，交通的联结度表示交通网络的发达程度，通常用贝塔指数来计算与比较。若用VVV表示一个交通网络中结点的数量，用EEE表示边的数量，则贝塔指数的计算方式为：β=EV\beta=\frac{E}{V}β=VE​。
“实践是检验真理的唯一标准”。作为一个热爱地理的好筱玛，她马上就把新学的知识应用到实践当中去。筱玛一口气出了nnn张交通网络规划图，其中第iii张交通网络GiG_iGi​有ViV_iVi​个结点和EiE_iEi​条边。筱玛一眼就看出了哪张图好、哪张图坏。但是作为一个负责任的好筱玛，她必须带领同学们一起进步。因此，她需要你将所有的nnn张图按照贝塔指数排序，并求出它们各自的贝塔指数在模109+710^9+7109+7意义下的值。

输入描述:
第一行一个整数nnn，表示交通网络规划图的数量。
接下来nnn行，每行两个整数ViV_iVi​和EiE_iEi​，分别表示图GiG_iGi​中的结点数量和边的数量。
输出描述:
输出共nnn行，每行一个数，表示贝塔指数第iii大的交通网络的贝塔指数在模109+710^9+7109+7意义下的值。

如果不能整除，输出分数取模后的结果。
示例1

输入

复制
1

1 3
输出

复制
3
说明
显然此时β=EV=3\beta=\frac{E}{V}=3β=VE​=3。
备注:
对于100%的数据，保证1≤n≤2×1051\le n\le 2\times10^51≤n≤2×105，1≤Vi,Ei≤1091\le V_i,E_i\le10^91≤Vi​,Ei​≤109。

必备知识：
费马小定理:

若p是质数，且p与a互质，有等式:

a^(p-1) %p == 1 % p
那么我们在这上面变一下型:

俩边同除a

a^(p-2)%p == a^(-1)%p
那么我们再在俩边同乘b

(b / a)%p == b*a^(p-2)%p
a^-1 mod p = a^p-2 mod p;

（m/a) mod  p = （( m mod p) * ( a^-1 mod p)) mod p

逆元概念引入

(a + b) % p = (a%p + b%p) %p （对）

(a - b) % p = (a%p - b%p) %p （对）

(a * b) % p = (a%p * b%p) %p （对）

(a / b) % p = (a%p / b%p) %p （错）
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod = 1e9 + 7;
const ll N = 2e5 + 10;
struct node
{
    ll x;
    double ra;
    bool operator <(const node &y) const
    {
        return ra > y.ra;
    }
} a[N];
int pow_mod(int a,int n,int m)  //幂取模,运用分治方法
{  //a为底数，n为指数，m为取模数
   if(n==0)  return 1;
   int x=pow_mod(a,n/2,m);
   long long int ans=(long long int)x*x%m;
   if(n%2==1)  ans=ans*a%m;
   return (int)ans;
}

ll ksm(ll a, ll b)
{
    ll ans = 1, base = a;
    while(b)
    {
        if(b&1)
            ans = (ans * base) % mod;
        base = (base * base) % mod;
        b >>= 1;
    }
    return ans;
}
int main()
{
    ll n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int x, y;
        cin >> y >> x;
        a[i].ra = ((x * 1.0) / y);
        if(x % y != 0)
            a[i].x = (x % mod * ksm(y, mod - 2)) % mod;
        else
            a[i].x = int(x / y);
    }
    sort(a, a + n);
    for(int i = 0; i < n; i++) cout << a[i].x << endl;
    return 0;
}