来星星的祝福(容斥+排列组合)

自星星的祝福

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K
(Java/Others)
Total Submission(s): 102 Accepted Submission(s): 9

直接本着字符的各种编码方式懵懵懂懂,什么ANSI、UNICODE、UTF-8、GB2312、GBK、DBCS、UCS……是休是看的特别晕,假如你细的翻阅本文乃势必可以清晰的亮她们。Let’s
go!
         
   
很漫长很久以前,有同等居多人,他们控制就此8只可开合的结晶管来组合成不同之状态,以象征世界上之万物。他们视8单开关状态是好之,于是他们将及时称之为”字节约”。

Problem Description

每当一个马拉松的山区中,流传着一个传说,一个确的好女婿,需要负来自M个不同星座的丫头的赞美–“你是单老实人”,才会找到真爱。
一定,yyf就是这般的好爱人。他费尽千辛万苦,找到了瞎子算命师ZJiaQ,ZJiaQ告诉他:你这辈会面临n个女孩子的夸赞。
这就是说,请问yyf找到真爱的票房价值有多少?
若是每个女孩子是M个星座中任一个底票房价值相等。

   
再后来,他们而召开了有的足拍卖这些字节的机器,机器开动了,可以就此字节来组成出不少状态,状态开始变来变去。他们看到这么是好的,于是它就是及时机器称为”计算机”。
   
开始计算机只于美国之所以。八员的字节一共可以构成出256(2的8次方)种不同之状态。
   
他们把其中的号子从0开始之32种植状态分别规定了超常规的用途,一但终端、打印机遇上预定好的这些字节被传染过来时,就如召开片预定的动作。遇上00×10,
终端就换行,遇上0x07, 终端就为人们嘟嘟叫,例如遇上0x1b,
打印机就打印反白的字,或者极端就用彩色显示字母。他们看到如此好好,于是便拿这些0x20之下的字节状态叫做”控制码”。
   
他们又把具备的空格、标点符号、数字、大小写字母分别用连续的字节状态表示,一直编到了第127如泣如诉,这样计算机就足以用不同字节来囤英语的亲笔了。大家
看到如此,都感到十分好,于是大家都拿这方案叫做 ANSI
的”Ascii”编码(American Standard Code for Information
Interchange,美国信息交互换标准代码)。当时世界上具有的微机都为此同一的ASCII方案来保存英文字。
         
   
后来,就比如打巴比伦塔同等,世界各地的都起来利用微机,但是洋洋国度之所以底未是英文,他们之假名里发出成百上千凡ASCII里没有的,为了好以处理器保存他
们的亲笔,他们决定以127号之后的空位来代表这些新的字母、符号,还投入了成百上千打表格时欲用生至的横线、竖线、交叉等相,一直把序号编到了最后一
个状态255。从128至255随即同一页的字符集被如”扩展字符集”。从此之后,贪婪的人类还无初的状态好就此了,美帝国主义可能没想到还有第三世界国
家之人们为希望可以为此到计算机吧!

Input

首先履行一个数T(T<=10),表示数据组数。(T可输入多次)
联网下每组数据中,输入n与m(n<=1000000000000000000(18单七零八落),m<=100)。

   
等中华人们得到计算机时,已经没有得以应用的字节状态来表示汉字,况且有6000基本上个常因此汉字需要保留也。但是就难休倒智慧之华夏布衣,我们不客气地管那些127声泪俱下后的奇异符号们一直注销掉,
   
规定:一个低于127底字符的含义以及原来同,但点滴单盖127之字符连在一起时,就象征一个字,前面的一个字节(他号称高字节)从0xA1为此到
0xF7,后面一个字节(低字节)从0xA1至0xFE,这样我们即便可以构成出约7000基本上只简体汉字了。在这些编码里,我们还管数学符号、罗马希腊底
字母、日文的字母们还编上了,连于 ASCII
里当就部分数字、标点、字母都备重新编了零星个字节长的编码,这便是时常说之”全角”字符,而本来在127声泪俱下以下的那些不畏受”半竞赛”字符了。
      中国平民看到如此好不利,于是便拿这种汉字方案叫做 “GB2312″。GB2312
是针对 ASCII 的华语扩展。
     
但是中国底字太多矣,我们飞速即不怕发现发生过多人口之人名没有主意于这边从出来,特别是某些老会烦人家的国家领导人。于是我们只能继续把
GB2312 没有下的码位找出来老实不谦虚地用上。
     
后来要么不够用,于是干脆不再要求没有字节一定是127如泣如诉以后的内码,只要第一个字节是高于127即一定表示马上是一个汉字之启幕,不管后面和的凡休是扩张字
符集里之始末。结果扩展之后的编码方案被称呼 GBK 标准,GBK 包括了 GB2312
的保有内容,同时还要充实了临近20000个新的汉字(包括繁体字)和符号。
     
后来少数民族也要就此微机了,于是我们再扩大,又加了几千只新的少数民族的配,GBK
扩成了GB18030。从此后,中华民族之知就足以在计算机时代中继承了。
      中国的程序员们盼这同样多元汉字编码的标准是好之,于是通称他们叫做
“DBCS”(Double Byte Charecter Set
双字节字符集)。在DBCS系列正式里,最老的表征是零星许节长的方块字字符和同字节长的英文字符并存于同同效仿编码方案里,因此他们写的先后为支持中文处
理,必须使顾字串里的各一个字节的值,如果此价是凌驾127的,那么尽管当一个双字节字符集里的字符出现了。那时候是被过加持,会编程的微机僧侣
们都使每天念下面这咒语数百全副:

Output

输出概率的比重,并且不欲输出小数点后的数字。

      “一个汉字毕竟少单英文字符!一个中国字毕竟少只英文字符……”
         
     
因为当时逐一国家都如华这么抓来同样效自己之编码标准,结果相互之间孰吗不了解谁的编码,谁呢非支持别人的编码,连大陆和台湾如此光隔了150海里,使用
着同一种植语言的哥们儿地区,也分头采取了不同之 DBCS
编码方案——当时的华人数怀念被电脑显示汉字,就非得作及一个”汉字系统”,专门就此来拍卖汉字之展示、输入的题材,但是非常台湾之无知封建人士形容的算命程序
就务须加装另一样模拟支持 BIG5 
编码的啊”倚天汉字系统”才足以为此,装错了字符系统,显示就见面乱了法!这怎么收拾?而且世界民族之林中还有那些一时就此非达标电脑的老少边穷百姓,他们的文又怎么
么办?

Sample Input

2
1 1
2 2

      真是计算机的巴比伦塔命题啊!
      正于这,大天使加百列及时出现了——一个给
ISO(国际标谁化组织)的国际组织决定下手解决者问题。他们利用的方式很简单:废了有的地区性编码方案,重新弄一个席卷了球上存有知识、所有字母
和标记的编码!他们打算于其”Universal Multiple-Octet Coded Character
Set”,简称 UCS, 俗称 “UNICODE”。
      UNICODE
开始制定时,计算机的存储器容量极大地发展了,空间又为未化问题了。于是
ISO
就直接规定必须用半只字节,也就算是16各来归并意味着拥有的字符,对于ascii里之那些“半比”字符,UNICODE
包持其原编码不更换,只是以那个长度由本的8号扩展为16各类,而别知识及言语的字符则整个重新联合编码。由于”半竞技”英文符号只待为此到低8个,所以该高
8员永远是0,因此这种大气的方案于保留英文文本时会见多浪费一倍的空间。

Sample Output

%100
%50

     
这时候,从老社会里活动过来的程序员开始发现一个意料之外之景象:他们之strlen函数靠不歇了,一个汉字不再是一定给简单个字符了,而是一个!是的,从
UNICODE
开始,无论是半角的英文字母,还是全角的方块字,它们还是联的”一个字符”!同时,也都是统一的”两单字节”,请小心”字符”和”字节约”两独术语的非
同,“字节约”是一个8员之情理存贮单元,而“字符”则是一个文化有关的符号。在UNICODE
中,一个字符就是个别个字节。一个中国字毕竟少单英文字符的一世已经急匆匆过去了。
         
     
从前出头字符集存在时时,那些做多语言软件之商家被上过非常充分累,他们为了当不同之国销售一律模拟软件,就只好在区域化软件时也加持那个双字节字符集咒
语,不仅要处处小心不要闹错,还要管软件受到的字在不同之字符集中转来改去。UNICODE
对于他们来说是一个良好之宏观解决方案,于是由 Windows NT 开始,MS
趁机将它的操作系统改了一致全勤,把所有的中心代码都改变化了为此 UNICODE
方式行事之版,从这儿开始,WINDOWS
系统终于任需要加装各种本土语言体系,就足以来得全世界上独具知识之字符了。
    但是,UNICODE
在制订时没考虑和另外一样种植现有的编码方案保持相当,这令 GBK 与UNICODE
在汉字的内码编排上完全是不均等的,没有一样栽简单的算术方法可把公文内容由UNICODE编码和其余一样种编码进行换,这种转移必须透过查表来拓展。
    如前所述,UNICODE
是因此单薄单字节来表示也一个字符,他一起可整合产生65535差的字符,这大概就好挂世界上具有知识的标志。如果还不够啊并未干,ISO已经准备
了UCS-4方案,说简单了便是四个字节来代表一个字符,这样我们即便得结合产生21亿单不等之字符出来(最高位生另外用途),这大概可以就此到银河联邦成立
那同样龙吧!
    UNICODE 来到时,一起过来之还有电脑网络的勃兴,UNICODE
如何当网及传也是一个得考虑的题材,于是面向传输的很多 UTF(UCS
Transfer
Format)标准出现了,顾名思义,UTF8就是每次8独各类传输数据,而UTF16就是是历次16个各,只不过为了传输时的可靠性,从UNICODE到
UTF时并无是直的呼应,而是如过局部算法和规则来转换。

分析

起点儿栽思路
1.套之所以容斥定理,我们好博得如下公式
\[1+\sum_{i=m-1}^{1}(-1)^{m-i}(\frac{i}{m})^nC_m^i\]
带走计算即可
2.令f[i]意味着n个人恰好有i单星座的概率,那么f[i]=(m个星座选指定的i个的票房价值)^n-(i个人选了j个星座的概率)*(j单星座的排列组合
取而代之入计算即可

   
受到了网编程加持的微处理器僧侣们还清楚,在网络里传递信息时有一个万分重要的问题,就是对此数据高低位的解读道,一些电脑是使低先发送的法,例
如我辈PC机采用的 INTEL
架构,而其他一对凡采取高位先发送的措施,在网被交换数据时,为了审批双方对于高低位的认是否是相同的,采用了扳平栽颇省心的方式,就是在文本流的发端时
向对方发送一个标志符——如果后的文本是高位在位,那就发送”FEFF”,反之,则发送”FFFE”。不迷信你得据此二进制方式打开一个UTF-X格式的
文件,看看开头两独字节是无是即时有限个字节?
    讲到这边,我们还顺便说说一个坏知名的不测现象:当你当 windows
的记事本里新建一个文件,输入”联通”两个字后,保存,关闭,然后重新打开,你会意识及时简单独字既熄灭了,代之的凡几乎单乱码!呵呵,有人说马上就是联通之所以拼不过移动的由。

trick

1.可能出现ans小于0,此时ans变成0

    其实就是因GB2312编码和UTF8编码产生了编码冲撞的原因。
    从网上引来一截从UNICODE到UTF8的转换规则:
        Unicode
        UTF-8
        0000 – 007F
        0xxxxxxx
        0080 – 07FF
        110xxxxx 10xxxxxx
        0800 – FFFF
        1110xxxx 10xxxxxx 10xxxxxx
   
例如”汉”字之Unicode编码是6C49。6C49以0800-FFFF之间,所以一旦为此3字节模板:1110xxxx
10xxxxxx 10xxxxxx。将6C49勾成二进制是:0110 1100 0100
1001,将这个比特流按三字节模板的支行方法分为0110 110001
001001,依次代替模板被的x,得到:1110-0110 10-110001 10-001001,即E6 B1
89,这便是那个UTF8的编码。
   
而当您新建一个文本文件时,记事本的编码默认是ANSI,如果您于ANSI的编码输入汉字,那么他实在就是是GB系列的编码方式,在这种编码下,”联通”的内码是:
            c1 1100 0001
            aa 1010 1010
            cd 1100 1101
            a8 1010 1000
         
   
注意到了吧?第一次之单字节、第三季只字节的胚胎部分的还是”110″和”10″,正好与UTF8规则里之两字节模板是一律的,于是又打开记事本时,记事
本就误认为这是一个UTF8编码的文本,让咱们管第一独字节的110与第二个字节的10错过丢,我们即便获取了”00001
101010″,再管各位对共同,补上引导的0,就取了”0000 0000 0110
1010″,不好意思,这是UNICODE的006A,也就是是不怎么写的假名”j”,而从此的蝇头配节用UTF8解码之后是0368,这个字符什么也未是。这就算
是只有”联通”两只字之文本没有章程在记事本里正常显示的缘由。

代码

//思路1
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define F(i,a,b) for(int i=a;i<=b;++i)
#define R(i,a,b) for(int i=a;i<b;++i)
#define mem(a,b) memset(a,b,sizeof(a))
#pragma comment(linker, "/STACK:102400000,102400000")
inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

double f[101];
int t;
ll n,m;
double work(double x,ll n,ll z)
{
    double ret=f[m]/f[z]/f[m-z];
    for(;n;n>>=1,x*=x) if(n&1) ret*=x;
        return ret;
}
int main()
{
    f[0]=1;
    for(ll i=1;i<=100;++i) f[i]=f[i-1]*i; 
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            scanf("%lld %lld",&n,&m);
            if(n<m) {printf("%%0\n");continue;}
            double ans=1;
            for(int i=m-1;i;--i)
            {
                double ret=work(1.0*i/m,n,i);
                ans+=(((m-i)&1)?-1:1)*ret;
            }
            if(ans<0) ans=0;
            putchar('%');
            printf("%.f\n",ans*100);
        }
    }
    return 0;
}

//思路2
#include<bits/stdc++.h>
using namespace std;
typedef __int64 ll;

long double c[105][105];
ll n,m;
long double f[105];
long double kp(long double x,ll n)
{
    long double ret=1;
    while(n)
    {
        if (n%2==1) ret*=x;
        n/=2;
        x*=x;
    }
    return ret;
}
int main()
{
    c[0][0]=1;
    for (int i=1;i<=10;i++)
    {
        c[i][0]=1;
        for (int j=1;j<=i;j++)
            c[i][j]=c[i-1][j-1]+c[i-1][j];
    }
    int t;

    while(~scanf("%d",&t))
    {

        while(t--)
        {
            scanf("%I64d%I64d",&n,&m);
            if (n<m) {printf("%%0\n"); continue;}
            for (int i=1;i<=m;i++)
            {
                f[i]=kp(1.0*i/m,n);
                for (int j=1;j<i;j++) f[i]-=f[j]*c[i][j];
            }
            if (f[m]<0) f[m]=0;
            printf("%%%.0f\n",(double)f[m]*100);
        }
    }
}

   
而要你当”联通”之后多输入几个字,其他的字的编码不见得又恰好是110以及10开始的字节,这样更打开时,记事本就未会见坚持这是一个utf8编码的文件,而会用ANSI的计解读的,这时乱码又非出新了。
         
   
好了,终于得回NICO的题材了,在数据库里,有n前缀的字串类型就是UNICODE类型,这种类型受到,固定用半单字节来代表一个字符,无论这字符是汉字还是英文字母,或是别的什么。

   
如果你若测试”abc汉字”这个串的长短,在无n前缀的数据类型里,这个字串是7单字符的长度,因为一个字相当给个别独字符。而当发出n前缀的数据类型里,同样的测试串长的函数将见面告诉你是5只字符,因为一个汉字就是是一个字符。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图