noip25

T1

经过一波大力推式子，发现答案是 \(\frac{n^{2}-1}{9}\) 。

式子回头再补，可能会

Code

#include<cstdio>

#define re register

#define int long long

namespace OMA

{

   int t,n;

   const int p = 998244353;

   inline int read()

   {

     int s=0,w=1; char ch=getchar();

     while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }

     while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }

     return s*w;

   }

   inline int quickpow(int a,int b)

   {

     int ans = 1;

     while(b)

     {

       if(b&1)

       { ans = ans*a%p; }

       a = a*a%p;

       b >>= 1;

     }

     return ans;

   }

   signed main()

   {

     t = read();

     int inv = quickpow(3,p-2);

     while(t--)

     {

       int n = read()%p,ans = 0;

       /*for(re int i=1; i<=n; i++)

       {

         (ans += i*(i-1)%p*inv%p) %= p;

       }*/

       printf("%lld\n",(n%p*n%p-1)%p*quickpow(9,p-2)%p);

     }

     return 0;

   }

}

signed main()

{ return OMA::main(); }

T2

考场想到了之前的noip14T3，当时xin用的vector 骗分...所以，我也....

好吧，是要加俩剪枝的，

当前枚举长度超过原串，直接break，换集合中的下一个串去接，
如果当前接出来的串对答案无贡献，那也break，因为在一个没出现过的串上加字符，怎么加也不会再产生贡献。不加第二个只能拿20pts

用了个vector和map。

我也不知道为什么我要这么认真的讲暴力，_{大概因为只会写暴力吧QAQ}

40pts

#include<map>

#include<vector>

#include<cstdio>

#include<cstring>

#define MAX 10010

#define re register

namespace OMA

{

   int n,len[MAX];

   long long ans;

   char s[MAX],ch[MAX][MAX];

   std::map<std::vector<char>,int>vis;

   signed main()

   {

     //freopen("my.out","w",stdout);

     scanf("%s%d",s+1,&n);

     len[0] = strlen(s+1);

     //printf("\n");

     for(re int i=1; i<=len[0]; i++)

     {

       for(re int j=i+1; j<=len[0]; j++)

       {

         std::vector<char>str;

         for(re int k=i; k<=j; k++)

         { str.push_back(s[k]); }

         vis[str]++;

         //for(re int k=0; k<str.size(); k++)

         //{ printf("%c",str[k]); }

         //printf("\n");

         //printf("%d\n",vis[str]);

       }

     }

     for(re int i=1; i<=n; i++)

     { scanf("%s",ch[i]+1); len[i] = strlen(ch[i]+1); }

     for(re int i=1; i<=n; i++)

     {

       for(re int j=len[i]; j>=1; j--)

       {

         for(re int k=1; k<=n; k++)

         {

           for(re int l=1; l<=len[k]; l++)

           {

             if(l+len[i]-j+1>len[0])

             { break ; }

             std::vector<char>str;

             for(re int x=j; x<=len[i]; x++)

             { str.push_back(ch[i][x]); }

             for(re int x=1; x<=l; x++)

             { str.push_back(ch[k][x]); }

             if(!vis[str])

             { break ; }

             //printf("back:%d front:%d: ",i,k);

             //for(re int x=0; x<str.size(); x++)

             //{ printf("%c",str[x]); }

             //if(vis[str])

             //{ printf(" true %d",vis[str]); }

             //printf("\n");

             ans += vis[str];

           }

         }

       }

     }

     printf("%lld\n",ans);

     return 0;

   }

}

signed main()

{ return OMA::main(); }

正解还没改出来，所以先咕了。

T3

考场上推出了\(k=2\),但没想到也是\(k>5\) 的时候，加上当时脑抽，一心去推\(k=3\)的，式子没推出来，其他式子还码错了。不过竟然能过样例

正解就是推式子。

原式子不想写了，直接看代码。

80pts

#include<cstdio>

#define MAX 300030

#define re register

#define int long long

namespace OMA

{

   int c[MAX],inv[MAX];

   int t,n[MAX],m[MAX],k[MAX];

   const int p = 3e5+7;

   inline int read()

   {

     int s=0,w=1; char ch=getchar();

     while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }

     while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }

     return s*w;

   }

   inline int quickpow(int a,int b)

   {

     int ans = 1;

     while(b)

     {

       if(b&1)

       { ans = ans*a%p; }

       a = a*a%p;

       b >>= 1;

     }

     return ans;

   }

   inline int min(int a,int b)

   { return a<b?a:b; }

   inline int max(int a,int b)

   { return a>b?a:b; }

   inline int abs(int a)

   { return a>=0?a:0; }

   inline int C(int n,int m)

   { return m>n?0:c[n]*inv[n-m]%p*inv[m]%p; }

   inline int lucas(int n,int m)

   { return !m?1:C(n%p,m%p)*lucas(n/p,m/p)%p; }

   int ans;

   inline int sum1(int n)

   { return (n%p*(n%p+1))>>1; }

   inline int sum2(int n)

   { return (n%p-1)*n%p*(n%p+1)%p; }

   #define n n[i]

   #define m m[i]

   #define k k[i]

   inline void task0(int i)

   {

     ans = 0;

     for(re int a=1; a<=n; a++)

     {

       for(re int b=1; b<=m; b++)

       { (ans += lucas(min(a,b)-1,k-1)) %= p; }

     }

     ans = ans*2%p;

     (ans += lucas(n,k)*m%p+lucas(m,k)*n%p) %= p;

   } // OK

   inline void task1(int i)

   { ans = (n%p)*(m%p)%p; } // OK

   inline void task3(int i)

   {

     for(re int len=2; len<=m; len++)

     { (ans += 4*(n-len+1)%p*(m-len+1)%p) %= p; }

     for(re int len=1; len<=n/2; len++)

     { (ans += 2*abs(n-len)%p*abs(m-len-len)%p+2*abs(m-len)%p*abs(n-len-len)%p) %= p; }

   }

   inline void task4(int i)

   {

     for(re int len=2; len<=m; len++)

     { (ans += (n-len+1)%p*(m-len+1)%p)%= p ; }

     for(re int len=3; len<=m; len+=2)

     { (ans += 4*(n-len+1)%p*(m-len+1)%p) %= p; }

     for(re int len=1; len<=m/2; len++)

     { (ans += abs(n-len-len)%p*abs(m-len-len)%p) %= p; }

     for(re int len=1; len<=n/2; len++)

     { (ans += 2*abs(n-len)%p*abs(m-len-len)%p+2*abs(m-len)%p*abs(n-len-len)%p) %= p; }

   }

   inline void task5(int i)

   {

     for(re int len=3; len<=m; len+=2)

     { (ans += (n-len+1)%p*(m-len+1)%p) %= p; }

     for(re int len=1; len<=m/2; len++)

     { (ans += abs(n-len-len)%p*abs(m-len-len)%p) %= p; }

   }

   inline void swap(int &a,int &b)

   { int t=a; a=b; b=t; }

   signed main()

   {

     t = read();

     for(re int i=1; i<=t; i++)

     { n = read(),m = read(),k = read(); }

     int top = p-1;

     c[0] = inv[0] = 1;

     for(re int i=1; i<=top; i++)

     { c[i] = i*c[i-1]%p; }

     inv[top] = quickpow(c[top],p-2);

     for(re int i=top-1; i; i--)

     { inv[i] = (i+1)*inv[i+1]%p; }

     for(re int i=1; i<=t; i++)

     {

       if(n<m)

       { swap(n,m); }

       task0(i);

       if(k==1)

       { task1(i); }

       else if(k==2)

       { ; }

       else if(k==3)

       { task3(i); }

       else if(k==4)

       { task4(i); }

       else if(k==5)

       { task5(i); }

       else

       { ; }

       printf("%lld\n",ans);

     }

     return 0;

   }

}

signed main()

{ return OMA::main(); }

然而这过不了后两个点，会T，考虑将式子中的循环拆开。

目前正在化\(k=5\)，等回头化出来，再补上吧。

巴特西

noip25

T1

T2

T3

最新文章

热门文章